做題做到 QuickSelect，結(jié)果感覺已經(jīng)有點(diǎn)記不清 QS 了……在此用力復(fù)習(xí)一下 QS私植。
本文解答所有關(guān)于 QS 的疑難雜癥威根。
首先上代碼，來自 Sedgewick 的 Algorithm：
public class Quick
{
public static void sort(Comparable[] a)
{
StdRandom.shuffle(a); // Eliminate dependence on input.
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); // Partition (see page 291).
sort(a, lo, j - 1); // Sort left part a[lo .. j-1].
sort(a, j + 1, hi); // Sort right part a[j+1 .. hi].
}
private static int partition(Comparable[] a, int lo, int hi)
{ // Partition into a[lo..i-1], a[i], a[i+1..hi].
int i = lo, j = hi + 1; // left and right scan indices
Comparable v = a[lo]; // partitioning item
while (true)
{ // Scan right, scan left, check for scan complete, and exchange.
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j); // Put v = a[j] into position
return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}
}
1. QuickSort 的總體思路：
在要排序的序列中選定一個(gè) pivot（這里選最左邊的元素）针炉，將序列進(jìn)行 partition，使得所有位于pivot 左邊的元素都小于 pivot扳抽，位于右邊的元素都大于 pivot篡帕，但此時(shí)左右兩部分被視為無序狀態(tài)：
[……（無序的左邊部分）……]，[（pivot）]贸呢，[……（無序的右邊部分）……]
這樣還不足以排序, 但我們發(fā)現(xiàn)镰烧，只要分別 sort 一下左邊和右邊部分，整個(gè)序列就有序了：
function sort(a[])
{
partition(a[]);
sort(a[]左邊部分);
sort(a[]右邊部分)楞陷；
}
到此QuickSort 已經(jīng)結(jié)束了怔鳖，EOF
——“然鵝，sort 左邊部分和右邊部分不還是要 sort 嗎固蛾？我們還是沒有實(shí)現(xiàn) sort 敖嶂础度陆！”
不過可能你已經(jīng)發(fā)現(xiàn)了，上面那個(gè) function sort(a[]) 是一個(gè)遞歸函數(shù)献幔！也就是說坚芜，每次我們分成左右兩個(gè)子序列，都要進(jìn)行 parttition斜姥，直到這個(gè)子序列只有一個(gè)元素！這樣僅靠 partition沧竟，我們就完成了排序铸敏，sort()函數(shù)作為遞歸體，不斷調(diào)用 partition()來處理子序列悟泵。
2. partition()
到此杈笔，我們已經(jīng)知道 partition 要達(dá)到什么目的，只需要再實(shí)現(xiàn) partition 的功能：首先先要選取一個(gè) pivot糕非，關(guān)于 pivot 的選取至關(guān)重要蒙具，因?yàn)闀?huì)極大地影響復(fù)雜度，稍后詳細(xì)分析時(shí)間復(fù)雜度朽肥。
public class QuickSort
{
public static int partition(int[] a, int low, int high)
{
int pivot = int[low];
int i = low, j = high + 1;
while(true)
{
while(a[++ i] < pivot) // pointer i keeps going if pointed element is less than pivot
{
if(i >= high) break;
}
while(a[-- j] > pivot) // pointer j keeps going if pointed element is larger than pivot
{
if(j <= low) break;
}
if(i >= j) // if two pointer cross
break;
swap(a, i , j);
}
swap(a, low, j); // put pivot between two partitions
return j; // return the index of pivot
}
public static void sort(int[] a, int low, int high)
{
int pivotIndex = partition(a, low, high);
sort(a, low, pivot - 1);
sort(a, pivot + 1, high);
}
}
*為什么與 pivot 比較的時(shí)候是“<”禁筏、">"？為什么還要交換兩個(gè)相同的元素衡招？
理想狀態(tài)下我們希望每次切分都得到兩個(gè)規(guī)模相同的子序列篱昔，也就是說 i，j 兩個(gè)指針能停下來的時(shí)候就停下來始腾，從而使最后 Pivot 的位置保持一個(gè)比較靠中間的位置州刽。否則，pivot 最終的 index 過于偏向一邊浪箭，就會(huì)增大遞歸的深度（best case是logN穗椅，而 worst case 則是 N）。
3. 3-way-partition
如果元素大量重復(fù)奶栖，上述辦法則還有可以提高的空間匹表，因?yàn)槲覀兘粨Q了大量重復(fù)的元素，還可以壓榨這部分的復(fù)雜度：
對(duì)于每次切分：從數(shù)組的左邊到右邊遍歷一次框冀，維護(hù)三個(gè)指針流椒，其中l(wèi)t指針使得元素（arr[0]-arr[lt-1]）的值均小于切分元素；gt指針使得元素（arr[gt+1]-arr[N-1]）的值均大于切分元素明也；i指針使得元素（arr[lt]-arr[i-1]）的值均等于切分元素宣虾，（arr[i]-arr[gt]）的元素還沒被掃描惯裕，切分算法執(zhí)行到i>gt為止。每次切分之后绣硝，位于gt指針和lt指針之間的元素的位置都已經(jīng)被排定蜻势，不需要再去處理了。之后將（lo,lt-1）,（gt+1,hi）分別作為處理左子數(shù)組和右子數(shù)組的遞歸函數(shù)的參數(shù)傳入鹉胖，遞歸結(jié)束握玛，整個(gè)算法也就結(jié)束。
public class Quick3way
{
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int lt = lo, i = lo+1, gt = hi;
Comparable v = a[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++;
} // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}
這里就沒有一個(gè)單獨(dú)的 partition()甫菠，而是將其整合進(jìn)了 sort() 里面挠铲。
4. pivot 的選取
pivot 的選取至關(guān)重要，理想狀態(tài)是每次都取到位于中間的 pivot寂诱，這樣就能保證遞歸深度為 LogN拂苹。如果對(duì)一個(gè)一定程度上有序的序列使用這種快排，復(fù)雜度則是 O（n）痰洒。
改進(jìn)：雖然我們每次都取最左邊的當(dāng) pivot瓢棒，但只要在取之前對(duì) array 進(jìn)行 shuffle，將有序性去除丘喻，就能很好的避免掉進(jìn) O（N）遞歸深度的坑里脯宿。
至于 shuffle 的方式有好幾種，比如 kunth-shuffle 等等泉粉，another story嗅绰。我們也可以直接用 API。
5. 復(fù)雜度分析
（鴿）
