快速排序

发表于 | 更新于 | 分类于 ，

一、原理

1、排序

快速排序采用了分治的思想：

1、对一个数组排序，可以分别对该数组的两个子数组进行排序。
2、两个子数组各自有序后，如果一个子数组中的所有元素都小于另一个子数组中的所有元素，那该多好，因为这意味着原素组已经有序了。
3、否则，我们还要把两个子数组合并为一个有序的数组。（成为归并排序）。
4、在对子数组排序前，使一个子数组中的所有元素都小于另一个子数组中的所有元素。（成为快速排序）。

2、切分

在排序前，使一个子数组中的所有元素都小于另一个子数组中的所有元素，这个操作，称为切分。

那该如何实现呢？

假设有数组a，还没有排序，起始位置为start，结束位置为end。
如果有一个元素a[j]，满足：a[start]到a[j-1]的所有元素都不大于a[j]，a[j+1]到a[end]的所有元素都不小于a[j]，那么可以说a[j]已经排定。

注：之所以说a[j]已经排定，是因为，a[j]现在所处的位置，正是在数组a排完序后，应该在的位置，即：a[start]到a[j-1]的所有元素都不大于a[j]，a[j+1]到a[end]的所有元素都不小于a[j]。在排序前与排序后，a[j]的位置是一样的，所以说a[j]已经排定。

现在，将a[j]左边所有的元素放到一个数组中，再把a[j]右边所有的元素放到一个数组中，这两个数组正好满足：一个子数组中的所有元素都小于另一个子数组中的所有元素。对两个子数组分别排序后，可以确定，数组a以及有序了。

我们不一定能找到一个已经排定的元素a[j]，但我们可以选择一个元素，再排定它。

2.1 单向切分

2.2 双向切分

1
2
3
4
5
6
7
8
9
10
11
12
13
// <<算法 第四版>>中的写法
public static int partition(Comparable[] a, int lo, int hi){
        Comparable part = a[lo];
        int i = lo, j = hi+1;  
        while (true){ 
            while (less(a[++i], part))  	if (i == hi) break;
            while (less(part, a[--j]))  	if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 我自己写的，会在下方改进
public int partition(Comparable[] a, int lo, int hi) {
        Comparable p = a[lo];             
        int l = lo + 1;   
        int r = hi;
        while (true) {
            while (l <= r && !less(p, a[l]))	l++;
            while (r >= l && !less(a[r], p))  	r--;
            if (r <= l) break;
            exch(a, l++, r--);
        }
        exch(a, lo, --l); 
        return l;    
}

二、优化

0、保持随机性

1、重复元素

假如在遇到和切分元素重复的元素时，我们继续扫描而不是停下来，证明使用这种方法的快排在处理只有若干种元素值得数组时，运行时间是平方级。

一种极端情况下的简单证法：

如果数组中只有一种重复值，不停下而继续扫描，首元素会到最后，则数组分成了大小为N-1的和大小为1的子数组，对两个子数组排序的比较代价分别为CN-1和1。

有：

CN = N + CN-1

CN = N + (N -1) + (N -2) + … + 2 + 1

CN ~ (1/2)N2

遇到和切分元素重复的元素时，停下，尽管会增多交换次数，但却能避免算法的运行时间变为平方级。

1
2
3
4
5
6
7
8
9
10
// 原：
while (l <= r && !less(p, a[l]))	
    l++;
while (r >= l && !less(a[r], p))  	
    r--;
// 改进为：
while (l <= r && less(a[l], p)) 
    l++;
while (r >= l && less(p, a[r])) 
    r--;

2、不越界

如果切分元素是数组中最小或最大的那个元素，就要小心数组越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 原：
while (l <= r && less(a[l], p)) 
while (r >= l && less(p, a[r])) 
// 上方条件可以保证数组不越界，但可以改进
    
// while (r >= l && less(a[r], p)) 
// 用于防止越过数组左边界，但 r == lo 时，less(a[r], p)不会成立，所以不会越过左边界
// 改进为：
while (less(p, a[r])) 
    
// while (l <= r && less(a[l], p)) 
// 用于防止越过数组左边界  
// 在《算法 第四版》中，将hi作为哨兵，其实左右指针本身也可以作为哨兵
// 不怎么好改进  
// 在三取样切分中，如果将最大元素放到子数组末尾，可以作为哨兵

3、 终止循环

当左右两个索引相遇时，就要退出循环。要考虑数组中与切分元素的值相同的元素。

1
if (r <= l) break;

4、交换元素

5、从右边开始扫描

6、使用 插入排序

M取5~15

7、三取样切分

8、三向切分

三、性能与比较

1、归并排序与快速三向切分对于重复元素的性能比较 P.189

0%