1.基本算法快速排序是一種分治的排序算法。它將一個數(shù)組分成兩個子數(shù)組，再對這兩個數(shù)組獨立地排序。快速排序的大致過程如下圖所示: 
整個算法分為三步: 選擇一個元素作為樞軸(pivot) 掃描并交換數(shù)組元素，使得小于樞軸的元素處于左邊，大于樞軸的元素處于右邊，這個過程稱為切分(partition) 對樞軸左邊部分和右邊部分的元素遞歸調(diào)用快速排序算法
1.1 快速排序的代碼實現(xiàn) public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int low, int high) {
if (high <= low) return;
// 切分（請見“快速排序的切分”）
int j = partition(a, low, high);
// 將左半部分a[low .. j-1]排序
sort(a, low, j - 1);
// 將右半部分a[j 1 .. high]排序
sort(a, j 1, high);
}
1.2 切分實現(xiàn)1.2.1 從兩邊向中間掃描選擇第一個元素作為樞軸 循環(huán)：指針i向右掃描，指針j向左掃描 指針i從第二個元素開始向右掃描找到比樞軸大的元素； 指針j從最后一個元素開始向左掃描找到比樞軸小的元素； 交換i和j的元素使得a[low..i]<=a[j..high] 交換樞軸與與指針j的元素,因為指針j的元素在退出循環(huán)后必然小于等于樞軸 達成a[low..j-1] <= a[j] <= a[j 1..high]
代碼實現(xiàn)如下: // 將數(shù)組切分為a[low..i-1], a[i], a[i 1..high]
static int partition(Comparable[] a, int low, int high) {
// 指針i向右掃描，指針j向左掃描
int i = low, j = high 1;
// 切分元素
Comparable key = a[low];
while (true) {
// 掃描左右，檢查掃描是否結(jié)束并交換元素
while (less(a[ i], key)) if (i == high) break;
while (less(key, a[--j])) if (j == low) break;
if (i >= j) break;
swap(a, i, j);
}
// 將key = a[j]放入正確的位置
swap(a, low, j);
// a[low..j-1] <= a[j] <= a[j 1..high] 達成
return j;
}
1.2.2 從左向右掃描選擇第一個元素作為樞軸 循環(huán)：指針i和j同時從第二個元素開始向右掃描 交換樞軸與與指針i的元素,因為指針i的元素在退出循環(huán)后必然小于等于樞軸 達成a[low..i-1] <= a[i] <= a[i 1..high]
代碼實現(xiàn)如下: // 將數(shù)組切分為a[low..i-1], a[i], a[i 1..high]
static int partition2(Comparable[] a, int low, int high) {
// 兩個指針均向右掃描
int i = low 1;
// 切分元素
Comparable key = a[low];
for (int j = i 1; j <= high; j ) {
//指針j向右掃描找到小于樞軸的元素
if (less(a[j], key)) {
//交換指針i和j的元素，確保指針i左邊的元素小于等于樞軸
swap(a,i,j);
//指針i只有交換元素時才移動
i=i 1;
}
}
// 將key = a[i]放入正確的位置
swap(a, low, i);
// a[low..i-1] <= a[i] <= a[i 1..high] 達成
return i;
}
1.3 單鏈表排序單鏈表的快排思路與數(shù)組的快排一致，但是由于單鏈表的指針移動只能單向移動，因此只能選擇從左向右掃描的切分方法。 1.3.1 鏈表的快排 static class Node {
int val;
Node next;
}
void quickSortList(Node head){
quickSortList(head,null);
}
void quickSortList(Node head,Node tail){
if(head==null||head==tail){
return;
}
Node pivot = partitionList(head, tail);
quickSortList(head,pivot);
quickSortList(pivot.next,tail);
}
1.3.2 鏈表的切分與1.2.2的從左向右掃描思路一致 static Node partitionList(Node head, Node tail) {
if (head == null || head.next == null) {
return head;
}
int key = head.val;
Node i = head.next;
for (Node j = i.next; j != tail; j = j.next) {
if (j.val < key) {
swap(i, j);
i = i.next;
}
}
swap(head, i);
return i;
}
static void swap(Node i, Node j) {
int temp = i.val;
i.val = j.val;
j.val = temp;
}
2. 提高性能2.1 切換到插入排序因此在排序小數(shù)組時應(yīng)該切到插入排序。將1.1的sort實現(xiàn)中的語句: if (high <= low) return;
替換成: if (high <= low M) {Insertion.sort(a, low, high); return;}
M為一個常數(shù)，最佳數(shù)值與系統(tǒng)相關(guān)，一般選擇5~15都可以得到令人滿意的結(jié)果。 2.2 精選樞軸樞軸的選取非常關(guān)鍵，如果每次切分時，樞軸都選用了最小的那個元素，快速排序就退化為冒泡排序了。解決辦法是使用數(shù)組的一小部分元素的中位數(shù)作為樞軸來切分?jǐn)?shù)組，但是代價是需要計算中位數(shù)。人們發(fā)現(xiàn)取樣3個數(shù)并選擇中位數(shù)作為樞軸，效果最好。 2.3 處理相同元素一個元素全部相同的子數(shù)組是不需要排序的，但是基礎(chǔ)的快速排序算法還是會將它切分為更小的數(shù)組并遞歸調(diào)用排序。 一個簡單的辦法是將數(shù)組切分為三部分，分別對應(yīng)小于、等于和大于樞軸的數(shù)組元素 2.3.1 三向切分從左到右遍歷數(shù)組一次，維護一個指針lt使得a[low..lt]中的元素都小于key，一個指針gt使得a[gt 1..high]中的元素都大于key，一個指針i使得a[lt..i]中的元素都等于key，a[i..gt]中的元素還未確定，如下圖所示: 
代碼實現(xiàn)如下: public class Quick3Way {
private static void sort(Comparable[] a, int lo, int hi) {
//調(diào)用此方法的公有方法sort() 請見算法2 .5 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) swap(a, lt , i );
else if (cmp > 0) swap(a, i, gt--);
else i ;
}
//現(xiàn)在 a[ lo..lt - 1] <v = a[lt..gt] <a[gt 1..hi] 成立
sort(a, lo, lt - 1);
sort(a, gt 1, hi);
}
private static void swap(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
2.4 JDK的快速排序優(yōu)化Arrays.sort()的排序只有在數(shù)組小于286才使用快速排序，更大的數(shù)組則使用更穩(wěn)定的自底向上的歸并排序。 快速排序使用了上述三種優(yōu)化方法。 2.4.1 小數(shù)組插入排序
2.4.2 計算中位數(shù)使用五值取中法找到中位數(shù)： 
2.4.3 三向切分這是三向切分可讀性更差的版本，原理與2.3.1相同： 
來源：https://www./content-4-283901.html
|
