swift&C双语版算法之快速排序

快速排序

快速排序的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
快速排序的复杂度为O(N*logN)。

C

<pre>
//快速排序
void quick_sort(int num[],int left,int right)
{
if ((left > right)) {
return ;
}

//设置基数值
int i = left,j = right,temp = num[left],t;
while (i != j) {
    //从右往左寻找比基数值小的数
    while ((i < j) && (num[j] >= temp)) {
        j--;
    }
    //从左往右寻找比基数值大的数
    while ((i < j) && (num[i] <= temp)) {
        i++;
    }
    
    //i,j未相遇前，如果找到的话进行交换
    if (i < j) {
        t = num[i];
        num[i] = num[j];
        num[j] = t;
    }
}

//一个基数值归位
if (left < i) {
    t = num[left];
    num[left] = num[i];
    num[i] = t;
}

//二分递归
quick_sort(num, left, i-1);
quick_sort(num, i+1, right);

}

//结果
int num[] = {15,3,45,7,17,99,25,25,14,75,48,14,2,3,7,17};
quick_sort(num, 0, count -1);
//2,3,3,7,7,14,14,15,17,17,25,25,45,48,75,99,Program ended with exit code: 0
</pre>

Swift

<pre>
//快速排序
func quickSort(array: inout [Int],left:Int ,right:Int) {

if array.isEmpty || array.count == 1 || left > right {
    return
}

//设置基数值
let temp = array[left]
var i = left, j = right
while i != j {
    
    //从右往左查找比基数小的值
    while (i<j) && (array[j]>=temp) {
        j -= 1
    }
    
    //从左往右查找比基数大的值
    while (i<j) && (array[i]<=temp) {
        i += 1
    }
    
    //i,j未相遇前，如果找到的话进行交换
    if i<j  {
        swap(&array[i], &array[j])
    }
}

//一个基数值归位
if left < i {
    swap(&array[left], &array[i])
}

//二分 递归
quickSort(array: &array, left: left, right: (i-1))
quickSort(array: &array, left: (i+1), right: right)

}

var originNum :[Int] = [15,3,45,7,17,99,25,25,14,75,48,14,2,3,7,17]
quickSort(array: &originNum, left: originNum.startIndex, right: originNum.index(before: originNum.endIndex))
print(originNum) //[2, 3, 3, 7, 7, 14, 14, 15, 17, 17, 25, 25, 45, 48, 75, 99]

<pre>