普林斯顿算法中级笔记6(快速排序)

快速排序

---

快速排序被誉为20世纪科学与工程十大算法之一

算法原理

1. 随机打乱数组
2. 任意取索引j,确保j的左侧都比j大，j的右侧都比j小,我们将此成为一次分区
3. 递归的对j的两侧进行上面步骤

分区步骤：

1. 取数组第一个元素lo为参照，从左到右遍历数组，直到得到元素i大于lo，于此同时从右向左遍历，知道元素j小于lo，交换i,j.而后继续遍历直到i==j.
2. 交换i,lo.至此完成一次分区.

代码实现

public class Quick {
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        while (true) {
            while (less(a[++i], a[lo]))
                if (i == hi) break;
            while (less(a[lo], a[--j]))
                if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    private static int partition(Comparable[] a, int lo, int hi) { /* see previous slide */ }
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
}

算法复杂度分析

最好情况下的算法复杂度：
假设partition每次都将数组恰好分为等长的两段，那么我们可以认为共进行了logN次比较，那么每次递归需要比较的次数为：N-1,N-2,N-3,...,N-logN～NlogN

屏幕快照 2018-08-10 下午5.46.13.png
最差情况下的算法复杂度：
每次分割，数组都被极端的分成了一边空，一边满的情况，那么算法复杂度就是N-1+N-2+...1~1/2N².
屏幕快照 2018-08-10 下午9.49.47.png
平均算法复杂度：
快速排序拥有在所有NlogN的算法中最低的平均算法复杂度，这也是它成名的原因。
我们用C_N 代表一个长度为N的数组在快速排序时需要的平均比较次数，那么第一次分区的分割点平均为任一元素的概率为1/N。则：
C_N = (N + 1) + (C₀ + C_N-1)/N + (C₁ + C_N-2)/N +....+ (C_N-1 + C₀)/N
其中(N+1)为第一次分区进行的比较次数，其余项为在概率1/N下的各种可能性的算法复杂度。
NC_N =N(N+1) + (C₀ + C_N-1) + (C₁ + C_N-2) + ... + (C_N-1 + C₀)
NC_N =N(N+1) + 2C₀ + ... +2C_N-1 -- 等式1
以N-1带入上面等式得到：
(N-1)C_N-1 = (N-1)N + 2C₀+...+2C_N-1 --等式2
等式1减去等式2
NC_N - (N-1)C_N-1 = 2N + 2C_N-1
C_N/(N+1) = C_N-1/N + 2/(N-1) = 2/3+2/4 +...+2/(N+1)
C_N = 2(N+1)(1/3+1/4+...+2/(N+1))
进行积分拟合后得到：
C_N = 2(N + 1) ln N ～1.39Nlg N

算法复杂度总结：

• 在最坏情况下的算法复杂度很高1/N²,但是出现这种情况的概率在实际中很小，除非你的初始数组本身就是有序的。
• 拥有最小的平均算法复杂度
• 在排序前先随机排列下初始数组，这样可以避免遇到最坏的情况。
• 什么情况下不适合？ 数组本身是有序的，或者有很对重复的值。(关于重复这一点后面会讲到)

快速排序的特点

• 快速排序的空间复杂度很小，需要利用的额外空间很小
• 快速排序是不稳定的

快速选择

这是由快速排序引申出的一个选择算法，用来在一组数中选择出第K大(如第一大就是最大，第二大等等...)的元素。
还记得快速排序的分区策略，即是选择出子数组中最大或最小的那个值，如果我们需要第三大的元素，那么就进行三次分区，第一次分区后，对右边子数组分区，再对右边子数组分区，即可取到我们要的元素。

算法实现：

public static Comparable select(Comparable[] a, int k)
{
 StdRandom.shuffle(a);
 int lo = 0, hi = a.length - 1;
 while (hi > lo)
 {
 int j = partition(a, lo, hi);
 if (j < k) lo = j + 1;
 else if (j > k) hi = j - 1;
 else return a[k];
 }
 return a[k];
}

平均地，快速选择具有线性的算法复杂度

快速排序中的重复元素问题

重复元素对迭代的影响分为两种：

• 当比较到重复元素时，若进行交换，则跟正常排序复杂度无差别，只是交换了重复元素
• 当比较到重复元素时，若不进行交换，则会导致子数组在切分时，左右不均匀，从而影响算法复杂度，若是对一个元素全部都相同的数组进行快速排序，那么它的复杂度会是1/2N².

对重复元素的优化处理

关于这个有个经典问题：荷兰国旗问题
我们使用Dijkstra 三元划分来算法来解决这个问题

• 将每一次分区被比较的元素称作v
• 从左到右扫描，i,lt初始指向0，gt初始指向数组末尾。
  • 若a[i]<v，则交换lt i,并且lt++,i++
  • 若a[i]>v，则交换gt,i并且gt--,i++
  • 若a[i]==v，则i++

算法实现

private static void sort(Comparable[] a, int lo, int hi)
{
 if (hi <= lo) return;
 int lt = lo, gt = hi;
 Comparable v = a[lo];
 int i = lo;
 while (i <= gt)
 {
 int cmp = a[i].compareTo(v);
 if (cmp < 0) exch(a, lt++, i++);
 else if (cmp > 0) exch(a, i, gt--);
 else i++;
 }
 sort(a, lo, lt - 1);
 sort(a, gt + 1, hi);
} 

排序算法复杂度总结

屏幕快照 2018-08-13 下午8.13.33.png