首先挑选基准值;然后分割数组,把小于基准值的元素放到基准值前面,大于基准值的元素放到基准值后面;最后递归地对小于基准值的子序列和大于基准值的子序列进行排序。如果用函数定义快速排序 f(),那么首先给这个函数签名为 f(arr, low, high)。其中,arr 表示传入的数组对象,low 表示需要排序的开始下标,high 表示需要排序的结束下标,那么这个函数可以完整地表示为。

1
2
3
4
5
f(arr, low, high) = 
if low < high
pivot = partition(arr, low, high)
f(arr, low, pivot - 1)
f(arr, pivot + 1, high)

总结起来就是,选基,分组,递归。分组函数 partition(arr, low, high) 的作用是把小于基准值的放在前面,大于基准值的放在后面,最后输出分组之后基准值所在的位置。做分组最经典的做法是用 lomuto 或者 hoare 分组法。
lomuto 分组法
选中第一为个 pivot,利用两个游标 i 和 j 把数组划分成

1
2
3
4
arr[pivot] | arr[(pivot+1)..(j)] | arr[(j + 1)..(i-1)] | arr[i..high]
pivot | 比 pivot 小 | 比 pivot 大 | 未处理
在划分结束之后,交换 pivot 和 j
lomuto 分割法里面,pivot 的选取会决定数组的分组方式
1
2
3
4
5
6
7
8
9
10
11
int partition(int[] array, int low, int high) {
int pivot = array[low], index = low;
for (int i = low; i <= high; i++) {
if (array[i] < pivot) {
index++;
swap(array, i, index);
}
}
swap(array, index, low);
return index;
}

hoare 分组法
选中任意一个作为 pivot,利用两个游标 i 和 j,做数组的左右往里面扫描。i 扫过的区域一定要比 pivot 小,j 扫过的区域一定比 pivot 大。当遇到不满足条件的时候,交换 i, j 指向的内容。

1
2
3
4
5
6
7
8
9
10
11
int partition(int[] array, int low, int high) {
int p = array[low];
int i = low, j = high;
while(i < j) {
while (i < j && array[j] > p) j--;
if(i < j) swap(array, i, j);
while (i < j && array[i] <= p) i++;
if(i < j) swap(array, i, j);
}
return i;
}

ps:

  • hoare 分组法会比 lomuto 分组法有平均少 3 倍的 swap 次数。参考
  • hoare 和 lomuto 都是不稳定的,并且在元素全部有序的情况下复杂度都是 O(n^2)
  • 完整代码和测试用例
  • 发明者 Tony Hoare