快速排序
快速排序被誉为20世纪科学与工程十大算法之一
算法原理
- 随机打乱数组
- 任意取索引j,确保j的左侧都比j大，j的右侧都比j小,我们将此成为一次分区
- 递归的对j的两侧进行上面步骤
分区步骤：
- 取数组第一个元素lo为参照，从左到右遍历数组，直到得到元素i大于lo，于此同时从右向左遍历，知道元素j小于lo，交换i,j.而后继续遍历直到i==j.
- 交换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/2N2.
屏幕快照 2018-08-10 下午9.49.47.png
平均算法复杂度：
快速排序拥有在所有NlogN的算法中最低的平均算法复杂度，这也是它成名的原因。
我们用CN 代表一个长度为N的数组在快速排序时需要的平均比较次数，那么第一次分区的分割点平均为任一元素的概率为1/N。则：
CN = (N + 1) + (C0 + CN-1)/N + (C1 + CN-2)/N +....+ (CN-1 + C0)/N
其中(N+1)为第一次分区进行的比较次数，其余项为在概率1/N下的各种可能性的算法复杂度。
NCN =N(N+1) + (C0 + CN-1) + (C1 + CN-2) + ... + (CN-1 + C0)
NCN =N(N+1) + 2C0 + ... +2CN-1 -- 等式1
以N-1带入上面等式得到：
(N-1)CN-1 = (N-1)N + 2C0+...+2CN-1 --等式2
等式1减去等式2
NCN - (N-1)CN-1 = 2N + 2CN-1
CN/(N+1) = CN-1/N + 2/(N-1) = 2/3+2/4 +...+2/(N+1)
CN = 2(N+1)(1/3+1/4+...+2/(N+1))
进行积分拟合后得到：
CN = 2(N + 1) ln N ～1.39Nlg N
算法复杂度总结：
- 在最坏情况下的算法复杂度很高1/N2,但是出现这种情况的概率在实际中很小，除非你的初始数组本身就是有序的。
- 拥有最小的平均算法复杂度
- 在排序前先随机排列下初始数组，这样可以避免遇到最坏的情况。
- 什么情况下不适合？ 数组本身是有序的，或者有很对重复的值。(关于重复这一点后面会讲到)
快速排序的特点
- 快速排序的空间复杂度很小，需要利用的额外空间很小
- 快速排序是不稳定的
快速选择
这是由快速排序引申出的一个选择算法，用来在一组数中选择出第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/2N2.
对重复元素的优化处理
关于这个有个经典问题：荷兰国旗问题
我们使用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
