快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。通常明显比其>他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
主要思想
是一种分治的思想。它将一个数组分成两个子数组，两部分独立的排序。
原数据：
1
| [5] [8] [9] [7] [1] [3] [9]
|
假定第一个元素[5]为哨兵，标记哨兵为x，使用临时变量temp存放哨兵的值，则原数据如下：
1
| [x] [8] [9] [7] [1] [3] [9]
|
1
2
3
| temp = [5]
left = 1
right = 6
|
第一步：，从数组尾部开始扫描，如果当前元素c[right]大于哨兵的值，则索引right减1，继续扫描，如果当前元素c[right]小于哨兵的值，则交换哨兵与当前元素的值。因为[3]小于[9]，因此交换[3]和哨兵[x]，得到如下结果。
1
| [3] [8] [9] [7] [1] [x] [9]
|
1
2
3
| temp = [5]
left = 1
right = 5
|
第二步，从数组头部开始扫描，如果当前元素c[left]小于哨兵的值，则索引left加1，继续扫描，如果当前元素c[left]大于哨兵的值，则交换哨兵与当前元素的值。因为[8]大于[5]，因此交换[8]和哨兵[x]，得到如下结果。
1
| [3] [x] [9] [7] [1] [8] [9]
|
1
2
3
| temp = [9]
left = 1
right = 5
|
第三步，继续从right-1处继续扫描，重复步骤一，得到结果如下。
1
| [3] [1] [9] [7] [x] [8] [9]
|
1
2
3
| temp = [9]
left = 1
right = 4
|
第四步，继续从left+1处继续扫描，重复步骤二，得到结果如下。
1
| [3] [1] [x] [7] [9] [8] [9]
|
1
2
3
| temp = [9]
left = 2
right = 4
|
一直重复上面的步骤直到，left大于等于right结束扫描，最后把临时变量temp的值存入[x]处，第一轮快速排序结束。可以得到第一轮结果如下，可以很明显看到小于[5]的值全在左边，大于[5]的值全在右边。
1
| [3] [1] [5] [7] [9] [8] [9]
|
1
2
3
| temp = [9]
left = 2
right = 2
|
第二轮，把第一轮的结果看成如下两个数组，对每个数组，重复第一轮的排序方法，直到左右数组均有序。
最终可以得到有序数组。
1
| [1] [3] [5] [7] [8] [9] [9]
|
时间与空间复杂度
快速排序是不稳定的排序算法，其时间复杂度计算公式如下，可以看到快速排序最好情况下时间复杂度为O(nlogn)，最坏情况下时间复杂度为2^n，平均时间复杂度为O(nlogn)。
$$
待补充
$$
代码实现
less函数与exch函数参见文章排序算法序言。
1
2
3
| public static void quick(Comparable[] c){
sort(c, 0, c.length-1);
}
|
1
2
3
4
5
6
7
8
| private static void sort(Comparable[] c, int start, int end) {
if (end <= start) {
return;
}
int j = partition(c, start, end);
sort(c, start, j - 1);
sort(c, j+1, end);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private static int partition(Comparable[] c, int start, int end){
int i = start, j = end + 1;
Comparable v = c[start];
while (true){
while (less(c[++i], v)){
if(i == end){
break;
}
}
while (less(v, c[--j])){
if(j == start){
break;
}
}
if(i >= j){
break;
}
exch(c, i, j);
}
exch(c, start, j);
return j;
}
|