快速排序
快速排序被譽(yù)為20世紀(jì)科學(xué)與工程十大算法之一
算法原理
- 隨機(jī)打亂數(shù)組
- 任意取索引j,確保j的左側(cè)都比j大俯邓，j的右側(cè)都比j小,我們將此成為一次分區(qū)
- 遞歸的對j的兩側(cè)進(jìn)行上面步驟
分區(qū)步驟：
- 取數(shù)組第一個元素lo為參照惫东，從左到右遍歷數(shù)組，直到得到元素i大于lo励翼，于此同時從右向左遍歷徒坡，知道元素j小于lo羞酗，交換i,j.而后繼續(xù)遍歷直到i==j.
- 交換i,lo.至此完成一次分區(qū).
代碼實現(xiàn)
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);
}
}
算法復(fù)雜度分析
最好情況下的算法復(fù)雜度：
假設(shè)partition每次都將數(shù)組恰好分為等長的兩段，那么我們可以認(rèn)為共進(jìn)行了logN次比較无蜂，那么每次遞歸需要比較的次數(shù)為：N-1,N-2,N-3,...,N-logN～NlogN
屏幕快照 2018-08-10 下午5.46.13.png
最差情況下的算法復(fù)雜度：
每次分割伺糠，數(shù)組都被極端的分成了一邊空，一邊滿的情況酱讶，那么算法復(fù)雜度就是N-1+N-2+...1~1/2N2.
屏幕快照 2018-08-10 下午9.49.47.png
平均算法復(fù)雜度：
快速排序擁有在所有NlogN的算法中最低的平均算法復(fù)雜度退盯，這也是它成名的原因。
我們用CN 代表一個長度為N的數(shù)組在快速排序時需要的平均比較次數(shù)，那么第一次分區(qū)的分割點(diǎn)平均為任一元素的概率為1/N渊迁。則：
CN = (N + 1) + (C0 + CN-1)/N + (C1 + CN-2)/N +....+ (CN-1 + C0)/N
其中(N+1)為第一次分區(qū)進(jìn)行的比較次數(shù)慰照，其余項為在概率1/N下的各種可能性的算法復(fù)雜度。
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))
進(jìn)行積分?jǐn)M合后得到：
CN = 2(N + 1) ln N ～1.39Nlg N
算法復(fù)雜度總結(jié)：
- 在最壞情況下的算法復(fù)雜度很高1/N2,但是出現(xiàn)這種情況的概率在實際中很小琉朽，除非你的初始數(shù)組本身就是有序的毒租。
- 擁有最小的平均算法復(fù)雜度
- 在排序前先隨機(jī)排列下初始數(shù)組，這樣可以避免遇到最壞的情況箱叁。
- 什么情況下不適合墅垮？ 數(shù)組本身是有序的，或者有很對重復(fù)的值耕漱。(關(guān)于重復(fù)這一點(diǎn)后面會講到)
快速排序的特點(diǎn)
- 快速排序的空間復(fù)雜度很小算色，需要利用的額外空間很小
- 快速排序是不穩(wěn)定的
快速選擇
這是由快速排序引申出的一個選擇算法，用來在一組數(shù)中選擇出第K大(如第一大就是最大螟够，第二大等等...)的元素灾梦。
還記得快速排序的分區(qū)策略，即是選擇出子數(shù)組中最大或最小的那個值妓笙，如果我們需要第三大的元素若河，那么就進(jìn)行三次分區(qū)，第一次分區(qū)后寞宫，對右邊子數(shù)組分區(qū)萧福，再對右邊子數(shù)組分區(qū)，即可取到我們要的元素辈赋。
算法實現(xiàn)：
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];
}
平均地鲫忍，快速選擇具有線性的算法復(fù)雜度
快速排序中的重復(fù)元素問題
重復(fù)元素對迭代的影響分為兩種：
- 當(dāng)比較到重復(fù)元素時，若進(jìn)行交換炭庙，則跟正常排序復(fù)雜度無差別饲窿，只是交換了重復(fù)元素
- 當(dāng)比較到重復(fù)元素時，若不進(jìn)行交換焕蹄，則會導(dǎo)致子數(shù)組在切分時，左右不均勻阀溶，從而影響算法復(fù)雜度腻脏，若是對一個元素全部都相同的數(shù)組進(jìn)行快速排序，那么它的復(fù)雜度會是1/2N2.
對重復(fù)元素的優(yōu)化處理
關(guān)于這個有個經(jīng)典問題：荷蘭國旗問題
我們使用Dijkstra 三元劃分來算法來解決這個問題
- 將每一次分區(qū)被比較的元素稱作v
- 從左到右掃描银锻，i,lt初始指向0永品，gt初始指向數(shù)組末尾。
- 若a[i]<v击纬，則交換lt i,并且lt++,i++
- 若a[i]>v鼎姐，則交換gt,i并且gt--,i++
- 若a[i]==v，則i++
算法實現(xiàn)
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);
}
排序算法復(fù)雜度總結(jié)
屏幕快照 2018-08-13 下午8.13.33.png
