思路
- 先从数列中取出一个数作为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)。
