1 快速排序的特点
快速排序的优点在于:原地排序，且将N元素排序所需时间和NlgN成正比。 缺点在于：比较脆弱，要非常小心才可以避免低劣的性能。
2 快速排序的原理
快速排序是一种divide-and-conquer的分治算法。首先将数组进行切分，然后在对切分的两部分分别进行排序。 算法的关键是切分过程，切分过程完成后会使得数组满足下面三个条件: 1. 对于某个j，a[j]已经排定 2. a[lo] 到 a[j-1]中的所有元素都不大于a[j] 3. a[j+1] 到 a[hi]中的所有元素都不小于a[j] 切分过程可以确定一个元素在数组中的最终位置。在一趟过程中，首先随机的选择a[lo]作为切分元素，然后从数组的左端开始扫描直到找到一个大于(或等于)a[lo]的元素，在从数组的右端向左边扫描直到找到一个小于(或等于)a[lo]的元素，此时将这两个元素交换，这样小于等于a[lo]的元素就换到了左边,大于等于a[lo]的元素就换到了右边。直到当两个指针相遇时，我们将a[lo]和左子数组最右端的元素a[j]交换然后返回j即可。
3 基本的快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public void quickSort(int[] a){
if(a == null || a.length < 1) return;
int hi = a.length - 1;
quickSort(a,0,hi);
}
public void quickSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int j = partition(a,lo,hi);
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}
public int partition(int[] a,int lo,int hi){
int i = lo;
int j = hi+1;
while(true){
while(less(a,++i,lo)) if(i == hi) break;
while(less(a,lo,--j)) if(j == lo) break;
if(i >= j) break;
swap(a,i,j);
}
swap(a,lo,j);
return j;
}
public void swap(int[] a, int i, int j){
if(i == j) return;
if(a[i] == a[j]) return;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public boolean less(int[] a,int i,int j){
return a[i] < a[j];
}
最关键的是partition函数，在两重的while循环中，有些判断是没有必要的，这里可以采用'哨兵'来减少这种判断。 '哨兵'其实是为了避免数组越界的判断而设置的，在partition的内层循环中，指针i从左向右扫描，直到遇到一个大于等于切分元素(枢纽元)才停止，假如a[lo]也就是切分元素是待切分数组最大的元素，则会在由于while(less(a,++i,lo))；这句会在hi处溢出，为了解决这个问题，可以首先将数组中最大的元素提前交换到a[hi]位置处，这样可以在所有包含它的子数组中成为哨兵，而在内部子数组时，右子数组最左侧的元素可以作为左子数组右边界的哨兵。这样指针i不会溢出。 对于指针j来说，从右向左扫描，因为最左侧的元素就是切分元素，所以当j==lo时，内层的while循环肯定会停止，不会溢出。 通过以上处理，我们就可以循环中的判断去掉。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void quickSort(int[] a){
if(a == null || a.length < 1) return;
int hi = a.length - 1;
int max = 0;
for(int i = 0; i <= hi; i++){
if(a[i] > a[max]) max = i;
}
swap(a, max, hi);
quickSort(a,0,hi);
}
public void quickSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int j = partition(a,lo,hi);
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}
public int partition(int[] a,int lo,int hi){
int i = lo;
int j = hi+1;
while(true){
while(less(a,++i,lo));
while(less(a,lo,--j));
if(i >= j) break;
swap(a,i,j);
}
swap(a,lo,j);
return j;
}
4 快速排序算法的改进
4.1切换到插入排序
在小数组的情况下，插入排序比快速排序要快，所以我们可以在排序小数组时切换到插入排序。 只需要在public void quickSort(int[] a,int lo,int hi)中将
if(lo >= hi) return;
改为
if(lo+M >= hi) {Insertion.sort(a,lo,hi);return;}
M的取值在5~15之间都是可以接受的，Mark Weiss提到比较好的是取M=10。
4.2三取样切分
三取样切分可以解决两个问题，第一个是切分元素的选取问题；同时也会顺便解决partition函数中的数组越界问题。 我们知道，如果每次切分元素都是数组中值的话，每次都会将数组二等分，从而获得最优的时间复杂度。因此切分元素的选择很重要，一种简单的方法是随机选择，较好的方法是对a[lo],a[mid],a[hi]排序、交换，最终得到a[lo] < a[mid] < a[hi],这样可以交换完成后，a[lo]和a[hi]就就已经放到了最后的位置上。而且也解决了数组越界的问题。最终代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public void quickSort(int[] a, int lo, int hi) {
if (lo + 3 >= hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j - 1 >= 0 && a[j - 1] > a[j]; j--) {
swap(a, j - 1, j);
}
}
return;
}
int j = partition(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
public int median(int[] a, int lo, int hi) {
int mid = (lo + hi) / 2;
if (a[lo] > a[mid])
swap(a, lo, mid);
if (a[lo] > a[hi])
swap(a, lo, hi);
if (a[mid] > a[hi])
swap(a, mid, hi);
swap(a, mid, hi - 1);
return a[hi - 1];
}
public int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi - 1;
int pivot = median(a, lo, hi);
while (true) {
while (a[++i] < pivot);
while (pivot < a[--j]);
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, hi - 1);
return i;
}
需要注意的是，当数组长度小时，必须切换到插入排序或其他排序，因为由于median方法的存在，使得数组中至少存在3个元素，否则会在partition函数中出现数组越界的情况。
4.3熵最优算法（三向切分）
Dijkstra的三向切分方法特别简洁，基本思想就是将数组分成三段，a[lo..lt-1]<pivot,a[lt,i-1]=pivot,a[gt+1,hi]>pivot,a[i,gt]中的元素还未确定，当i>gt时退出循环。这种方法存在的问题在于如果数组中重复元素不多时，比标准排序多了很多次交换，后来又有大神解决了这个问题，下次再补上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void quickSort(int[] a){
if(a == null || a.length < 1) return;
int hi = a.length - 1;
threeWaySort(a,0,hi);
}
public void threeWaySort(int[] a,int lo,int hi){
if(lo >= hi) return;
int lt = lo,i = lo + 1,gt = hi;
int pivot = a[lo];
while(i <= gt){
if(a[i] < pivot) swap(a,lt++,i++);
else if(a[i] > pivot) swap(a,gt--,i);
else i++;
}
threeWaySort(a,lo,lt-1);
threeWaySort(a,gt+1,hi);
}
5 算法应用实例
5.1 寻找第k小的数字
快速排序有一个很常见的应用，寻找第k小的数字。这个有点类似二分法寻找某个数字，先看中间的是不是，不是的话，如果小，那就在左半边找，如果大了就在右半边找。
1
2
3
4
5
6
7
8
9
10
11
public int kth(int[] a,int k){
int lo = 0, hi = a.length - 1;
while(hi > lo){
int i = partition(a,lo,hi);
if (i > k) hi = i - 1;
else if (i < k) lo = i + 1;
else return a[i];
}
return a[lo];
}
5.2 螺丝和螺帽
Nuts and bolts. (G. J. E. Rawlins). You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger. But it is not possible to directly compare two nuts or two bolts. Given an efficient method for solving the problem. Hint: customize quicksort to the problem. Side note: only a very complicated deterministic O(N log N) algorithm is known for this problem.
假如可以比较的话，分别对螺丝、螺帽进行排序即可，这道题的关键之处就是螺丝之间不能比较，螺帽之间不能比较，但使用快排肯定需要比较，那么应该比较什么呢？题中条件提到，螺丝和螺帽之间是可以比较的，因为他们之间是一一对应的，存在大小关系，因此应该从这进行比较。下面使用大写字母代表螺帽，小写字母代表螺丝，比如有下面的一堆螺丝螺帽:
a[] S D F G H J K L b[] h g j k l s d f
既然螺丝和螺帽可以比较，那么不妨可以用b[0]作为pivot元素，将a[]进行 三向切分 ，切分完成后可以得到:
a[] D F G H J K L S
然后依据H在对b进行 三向切分 ,可以得到：
b[] g f d h s l k j
然后递归的进行。
Best case. Write a program QuickBest.java that produces a best-case array (with no duplicates) for Quick.sort(): an array of N distinct keys with the property that every partition will produce subarrays that differ in size by at most 1 (the same subarray sizes that would happen for an array of N equal keys). For the purposes of this exercise, ignore the initial shuffle.
题目意思是生成一个数组，使得基本的sort()方法在对其快速排序时效果最好，即每次都基本是平均二分。
这是一个快速排序的逆算法，比如下面的:
b a c
就是一个最好的序列(pivot元素取第一个),
a b c d e >> c a b d e
对于一个排好序的数组来说，第一步首先计算a[lo...mid-1]的最佳情况，然后计算a[mid+1,hi]的最佳情况，最后把 a[o] 与 a[mid]进行交换即可。整个是一个递归的过程。
当快速排序时，首先根据a[lo]对数组进行切分，从而a[lo]交换到a[mid]的位置，然后在递归的对左右两部分进行切分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void QuickBest(int n){
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = i;
}
QuickBest(nums,0,nums.length - 1);
System.err.println(Arrays.toString(nums));
}
private void QuickBest(int[] nums,int lo, int hi){
if(lo >= hi) return;
int mid = lo +(hi - lo)/2;
QuickBest(nums,lo,mid-1);
QuickBest(nums,mid+1,hi);
swap(nums,lo,mid);
}
K&R中提到一种最简单的快速排序的方法，首先将a[mid]与a[lo]交换，作为pivot元素，然后从左向右遍历数组，将比pivot小的放到数组左侧，a[lo..last]表示小于pivot元素。最后交换a[lo] 与 a[last]。
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi) {
if (hi <= lo) return;
swap(a, lo, (lo + hi) / 2); // use middle element as partition
int last = lo;
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[lo])) swap(a, ++last, i);
swap(a, lo, last);
sort(a, lo, last-1);
sort(a, last+1, hi);
}