快速排序
- 快速實作
- 優化
-
- 小數組使用插入排序
- 三取樣切分
- 熵最佳排序
-
- 三向切分
- 快速三向切分
快速實作
package com.concurency.sort;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
// 快速排序
public class Quick {
public static void sort(Comparable[] a){
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a,int low,int high){
// 如果出現越界，比如上層 j 為 high,j為low的情況，
// 如果上層j為high,一次正常,二次sort low = high + 1,high = high, 此處可以屏蔽
// 如果上層j為low,一次sort low = low,high = low - 1,此處也可以屏蔽
if(high <= low ){ // filter
return;
}
// 分區，以j為分界點，左邊都比a[j]小，右邊都比a[j]大
// 如果j 為 high?如何處理？如果j為low,如何處理 ----> filter
int j = partition(a,low,high);
// 将左邊再次分區
sort(a,low,j-1);
// 将右邊再次分區
sort(a,j+1,high);
}
private static int partition(Comparable[] a, int low, int high) {
int i = low;
// 由于 -- j必須是最後索引值，是以+1防止越界
int j = high + 1;
// 以此分區
Comparable v = a[low];
while (true){
// 準備交換材料
// 從 low + 1 開始一直找到比v大的數
// 這裡不能使用i++,
// 原因是i參與後面的運算，如果使用i++,比較的是i,而後面參與運算的是i++,這樣直接會産生錯誤,i必須使用最終值
// 如果a[i]>=v，說明目前值不符合預期，需要交換，如果a[i]<v，說明此值位置正常，不需要交換，繼續向後方推進
while (less(a[++i],v)){
if(i == high){
break;
}
}
// 從 high 開始一直找到比j小的數
// 為什麼j=high,這裡使用j--會不行？
// 這裡不能使用j--,
// 原因是j參與後面的運算，如果使用j--,比較的是j,而後面參與運算的是j--,這樣直接會産生錯誤,j必須使用最終值
// 如果<=v，說明目前值不符合預期，需要交換,如果v<a[j] ,說明此值符合預期，不需要交換，繼續向前方推進
while (less(v,a[--j])){
if(j == low){
break;
}
}
// 最合适的位置可能比v大，也可能比v小，也可能等于v，
// 如果向後方推進的位置i>=j,說明i,j位置發生了交錯，錯過了最合适的位置，在交換已經變得毫無意義。
if(i >= j)
break;
// 将比v大的和比v小的交換位置
exchange(a,j,i);
}
// 最終彙聚的位置是v最合适的位置
// 為什麼取j,不取i????是什麼決定的v最合适的位置
// 解答：左邊小，右邊大，v的位置沒有變，把小的換到左邊，把大的換到右邊，
// 因為從low開始，如果和i交換，左邊會呈現亂序
/*
* 原序:3 4 5 1 2
*
* 假設已經拍好了，等待放入合适位置
* 理想狀态: v = 3 ,交換後 3 2 1 5 4 此時 i = 3,j = 2
* 如果此時 選 i，即 5 2 1 3 4 ，很明顯，依然是亂序
* 如果此時 選 j，即 1 2 3 5 4 ,完全符合預期
*
*
* 另一種設想，如果v選high
*
* v = 2,代碼會有所不同，比如向前推進變為high - 1 開始，而向後推進變為low開始
*
* 交換後: 1 4 5 3 2 i = 1,j=0
*
* 選 i 交換 1 2 5 3 4,完全符合預期、
* 選 j 交換 2 4 5 3 1,不符合預期。
*
* 是以，選i,還是選j,取決于v的取值
*
*
* */
exchange(a,j,low);
return j;
}
private static boolean less(Comparable a,Comparable b){
return a.compareTo(b) < 0;
}
private static void exchange(Comparable[] a,int i,int j){
Comparable old = a[i];
a[i] = a[j];
a[j] = old;
}
protected static void show(Comparable[] a){
for (Comparable tComparable : a) {
StdOut.println(tComparable + "");
}
StdOut.println();
}
public static void main(String[] args) {
int n = 10;
Double[] a = new Double[n];
for (int i = 0; i < n; i++)
a[i] = StdRandom.uniform(0.0, 1.0);
sort(a);
show(a);
}
}
優化
小數組使用插入排序
public static void sort(Comparable[] a,int low,int high){
// 如果出現越界，比如上層 j 為 high,j為low的情況，
// 如果上層j為high,一次正常,二次sort low = high + 1,high = high, 此處可以屏蔽
// 如果上層j為low,一次sort low = low,high = low - 1,此處也可以屏蔽
int num = high - low + 1;
if(num <= 1)
return;
if(num < 10) {
insert(a, low, high);
return;
}
// 分區，以j為分界點，左邊都比a[j]小，右邊都比a[j]大
// 如果j 為 high?如何處理？如果j為low,如何處理 ----> filter
int j = partition(a,low,high);
// 将左邊再次分區
sort(a,low,j-1);
// 将右邊再次分區
sort(a,j+1,high);
}
// 插入排序實作
private static void insert(Comparable[] a, int low, int high){
for(int i = low;i<=high;i++){
for (int j = i ;j > low && less(a[j],a[j-1]);j--){
exchange(a,j,j-1);
}
}
}
三取樣切分
private static int median3(Comparable[] a, int i, int j, int k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}
public static void sort(Comparable[] a,int low,int high){
// 如果出現越界，比如上層 j 為 high,j為low的情況，
// 如果上層j為high,一次正常,二次sort low = high + 1,high = high, 此處可以屏蔽
// 如果上層j為low,一次sort low = low,high = low - 1,此處也可以屏蔽
if(high <= low){
return;
}
int m = median3(a,low,low + (high - low + 1)/2,high);
exchange(a,low,m);
// 分區，以j為分界點，左邊都比a[j]小，右邊都比a[j]大
// 如果j 為 high?如何處理？如果j為low,如何處理 ----> filter
int j = partition(a,low,high);
// 将左邊再次分區
sort(a,low,j-1);
// 将右邊再次分區
sort(a,j+1,high);
}
熵最佳排序
三向切分
// 将整個數組分為3個部分，
// lo-lt-1 是小于v的本分，
// lt-i-1 是等于v的部分，
// i-gt的部分不确定，保持移動，
// gt+1-hi的部分是大于v的部分
private static void sort2(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
// lt -1 為小于v的結束邊界
int lt = lo;
// gt + 1 為大于v開始的邊界
int gt = hi;
// 取值v
Comparable v = a[lo];
int i = lo + 1;
// 當i觸碰到>v的邊界時，就可以結束了
while (i <= gt) {
// 目前值 和 v進行比較
int cmp = a[i].compareTo(v);
if (cmp < 0) {
// 如果 a[i] < v,那麼值符合 lo-lt-1的預期，和lt值交換，lt向後推進，i向後推進
// lt 終究是v
exchange(a, lt++, i++);
} else if (cmp > 0) {
// 如果 a[i] > v,那麼值符合 gt + 1-hi的預期，和gt 交換，gt向前方推進
exchange(a, i, gt--);
} else {
// 相等
i++;
}
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1);
sort(a, gt+1, hi);
}
快速三向切分
更加完善的的切分方式，和針對重複值的優化
// does v == w ?
private static boolean eq(Comparable v, Comparable w) {
if (v == w) return true; // optimization when reference equal
return v.compareTo(w) == 0;
}
// 分為4個區域，新增變量 p,q,i,j lo-p等于v,p+1-i小于v,
private static void sort3(Comparable[] a, int lo, int hi) {
int n = hi - lo + 1;
// 小數量使用插入排序
if (n <= 15) {
insert(a, lo, hi);
return;
}
// 中等數量計算一次中位數，三分取樣
else if (n <= 40) {
int m = median3(a, lo, lo + n/2, hi);
exchange(a, m, lo);
}
// 大量資料，中位數中取中位數，再次三分取樣
else {
int eps = n/8;
int mid = lo + n/2;
int m1 = median3(a, lo, lo + eps, lo + eps + eps);
int m2 = median3(a, mid - eps, mid, mid + eps);
int m3 = median3(a, hi - eps - eps, hi - eps, hi);
int ninther = median3(a, m1, m2, m3);
exchange(a, ninther, lo);
}
// Bentley-McIlroy 3-way partitioning
// 排序的時候： lo-p 位置等于v,p + 1 - i 位置<v,i-j中間亂序,j-p-1 位置 <v,p - hi 等于v
//
int i = lo, j = hi+1;
int p = lo, q = hi+1;
Comparable v = a[lo];
while (true) {
// 等于 和 大于一樣不成立
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;
// 如果最合适的位置的值和v相等，那麼放左邊，除了相等的值，剛好湊成有序
if (i == j && eq(a[i], v))
exchange(a, ++p, i);
if (i >= j) break;
exchange(a, i, j);
// 如果相等，移至左邊
if (eq(a[i], v)) exchange(a, ++p, i);
// 如果相等，移至右邊
if (eq(a[j], v)) exchange(a, --q, j);
}
i = j + 1;
// 歸位
for (int k = lo; k <= p; k++)
exchange(a, k, j--);
for (int k = hi; k >= q; k--)
exchange(a, k, i++);
sort3(a, lo, j);
sort3(a, i, hi);
}
![為什麼普通人難以掌握資訊學奧林匹克競賽的知識？·由于資訊學奧賽涉及抽象的概念和算法，需要運用數學思維和邏輯推理能力來解決[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)