快速排序

 

思路

  • 先从数列中取出一个数作为key值。
  • 将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边。
  • 对左右两个小数列重复第二步,直至各区间只有1个数。

平均时间复杂度:O(N*logN)

实现

void quick_sort(const int* a, int l, int r){
    while(l < r){
        int i = sort(a, l, r);
        quick_sort(a, l, i-1);
        quick_sort(a, i+1, r);
    }
}

int sort(const int* a, int l, int r){
    int k = a[l];
    while(l < r){
        while(l < r && a[l] < k) l++;
        while(l < r && a[r] > k) r--;
        swap(a[l], a[r]);
    }
    a[l] = k;
    return l;
}

关键点注释

快排是递归的。递归的一般结构为:

fun() {
    if(停止条件) return;
    递归体
    fun();
}

参数l是子数组的首项的索引,r是子数组的末项的索引。

停止条件为l>=r,即子数组只有1个元素。

用2个指针分别从两头开始向中间挤,直到2指针相遇。即while(i < j)。