在介紹排序之前肮街，首先來介紹幾個在每個排序算法中都需要使用的方法，我將它們單獨寫在了一個類中，它們分別是 less(), exchange(), isSort() 方法敦间，less() 方法用于判斷兩個元素的大小炸渡， exchange() 用于交換兩個元素的位置娜亿，isSort() 方法用于判斷當前數(shù)組是否有序，它們的實現(xiàn)如下所示
package com.sort;
@SuppressWarnings("rawtypes")
public class Sort {
@SuppressWarnings("unchecked")
public static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void exchange(Comparable[] a, int i, int j) {
if (i == j)
return;
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
}
這里之所以將數(shù)據(jù)類型設(shè)置為 Comparable 是為了兼容更多種類型的數(shù)據(jù)蚌堵，比如這樣寫买决，我們可以對任何實現(xiàn)了 Comparable 接口的數(shù)據(jù)進行操作，比如系統(tǒng)系統(tǒng)的 Integer吼畏，Double督赤，String 等。如果我們想要對自定義的數(shù)據(jù)進行操作泻蚊，那么就實現(xiàn) Comparable 接口并且重寫 compareTo() 方法躲舌，定義自己的判斷規(guī)則即可。
選擇排序
這種排序是最簡單的排序算法之一性雄，另一個是下面將要介紹的插入排序没卸。選擇排序的基本思想是：首先找到數(shù)組中最小的那個元素，其次秒旋，將它和數(shù)組的第一個元素交換位置约计。再次，在剩下的元素中找到最小的元素滩褥，將它和第二個元素交換位置病蛉。如此往復(fù)，直到整個數(shù)組排序。
對于一個長度為 N 的數(shù)組铺然，選擇排序需要大約 N^2/2 次比較 和 N 次交換俗孝，所以說它的執(zhí)行時間總是和 N^2 成正比的。
這種算法有兩個特點
- 運行時間和輸入無關(guān)魄健。也就是說我們?yōu)榱苏页鲎钚〉哪莻€元素而遍歷一遍數(shù)組并沒有為下次掃描提供任何有用的信息赋铝。這也就意味著，一個已經(jīng)有序的數(shù)組或者主鍵全部相等的數(shù)組和一個元素隨機排列的數(shù)組所用的排序時間竟然一樣長沽瘦。
- 數(shù)據(jù)的移動是最少的革骨。因為我們每次交換都會改變兩個元素的值，所以選擇排序只會進行 N 次交換析恋，交換次數(shù)和數(shù)組的大小呈現(xiàn)線性關(guān)系良哲，這個特征是選擇排序獨有的，其他排序算法都不具備此特性助隧。
下面來看看選擇排序的實現(xiàn)
public final class SelectionSort {
@SuppressWarnings("rawtypes")
public static void sort(Comparable[] a) {
if (Sort.isSorted(a)) {
return;
}
int length = a.length;
for (int i = 0; i < length; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (Sort.less(a[j], a[min])) {
min = j;
}
}
if (min != i) {
Sort.exchange(a, i, min);
}
}
}
}
插入排序
插入排序和選擇排序的共同點是筑凫，當前索引的左邊的所有元素都是有序的，但是不同的是插入排序只對當前索引左邊的值進行操作并村，而選擇排序是對索引右邊的數(shù)進行操作巍实。
在性能上，插入排序所需要的時間取決于輸入元素的初始順序哩牍，如果一個很大而且其中的元素已經(jīng)基本有序的數(shù)組棚潦，插入排序所需的時間會非常短。在以下幾種情況下膝昆，插入排序是一個非常高效的算法
- 數(shù)組中每個元素距離它的最終位置都不遠
- 一個有序的大數(shù)組接一個小數(shù)組
- 數(shù)組中只有那么幾個元素位置不正確
關(guān)于選擇排序和插入排序丸边，如果是針對一個隨機的數(shù)組，那么這兩種排序算法所需要的時間之比是一個很小的常數(shù)外潜，如果是針對部分有序的數(shù)組原环，差距將會更加明顯。
插入排序的實現(xiàn)
package com.sort;
public class InsertSort {
@SuppressWarnings("rawtypes")
public static void sort(Comparable[] a) {
int length = a.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0 && Sort.less(a[j], a[j - 1]); j--) {
Sort.exchange(a, j, j - 1);
}
}
}
}
希爾排序
希爾排序是基于插入排序的处窥，它是一種快速的插入排序嘱吗。想象一下，對于一個很大的數(shù)組滔驾，最小的元素在數(shù)組的末尾谒麦，如果使用插入排序，它將一步步的移動到數(shù)組的開頭哆致，這是十分消耗時間的绕德。所以希爾排序主張將數(shù)組中任意間隔為 h 的元素排成有序，稱之為 h 有序數(shù)組摊阀，換言之就是將所有間隔為 h 的元素組成一個小的數(shù)組耻蛇，如果 h 很大踪蹬，那么我們一次就可以把較小的元素移動到很遠的地方，而不是一步步的移動臣咖。
希爾排序高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性跃捣。當然希爾排序的性能還與 h 有關(guān)，對于不同的 h 表現(xiàn)出不同的速度夺蛇，但是無法確定哪一種是最好的赵抢，所以這里選取 h 從 N/3 遞減至 1.
希爾排序的運行時間是達不到 平方級別的铸磅，它在最壞的情況下 和 N^3/2 成正比缚够。
希爾排序的實現(xiàn)
package com.sort;
public class ShellSort {
@SuppressWarnings("rawtypes")
public static void sort(Comparable[] a) {
int length = a.length;
int h = 1;
while (h < length / 3)
h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && Sort.less(a[j], a[j - h]); j -= h) {
Sort.exchange(a, j, j - h);
}
}
h = h / 3;
}
}
}
歸并排序
實際上煮剧，當問題的規(guī)模到達一定的程度，上面的算法就已經(jīng)無能為力了甚脉，尤其是 插入排序和選擇排序丸升，所以下面來介紹歸并排序。
歸并排序的主要思想是將一個數(shù)組分割成兩部分牺氨，分別進行排序发钝，然后將結(jié)果歸并起來.
歸并排序的優(yōu)點是能夠保證將任意長度為 N 的數(shù)組排序時間和 NlogN 成正比，缺點是他所需的 額外空間和 N 成正比波闹，也就是說排序需要借助于輔助空間。
下面來看看代碼
package com.sort;
public class MergeSort {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int low, int high) {
if (high <= low)
return;
int mid = low + (high - low) / 2;
sort(a, low, mid);
sort(a, mid + 1, high);
merge(a, low, mid, high);
}
private static void merge(Comparable[] a, int low, int mid, int high) {
int i = low;
int j = mid + 1;
for (int k = low; k <= high; k++) {
aux[k] = a[k];
}
for (int k = low; k <= high; k++) {
if (i > mid)
a[k] = aux[j++];
else if (j > high)
a[k] = aux[i++];
else if (Sort.less(aux[i], aux[j]))
a[k] = aux[i++];
else
a[k] = aux[j++];
}
}
}
分析一下以上的代碼涛碑，首先申請一個和原數(shù)組 a 相同大小的輔助空間精堕，調(diào)用 sort() 方法，遞歸分割數(shù)組蒲障，直到 high <= low歹篓，這說明數(shù)組中只存在一個元素了，遞歸分割的意義在于不斷縮小數(shù)組的規(guī)模揉阎，然后對數(shù)組進行排序合并庄撮，用二叉樹來描述這一過程最為合適，左右孩子排序后合成根節(jié)點毙籽。
快速排序
快速排序是當前最流行的排序算法洞斯，是使用最廣泛的排序算法了。之所以它這么受歡迎是因為它只需要一個很小的輔助棧坑赡，而且將一個長度為N 的數(shù)組排序所需時間和 NlgN 成正比烙如。之前學(xué)過的所有算法都無法將這兩個優(yōu)點結(jié)合起來，但是快速排序做到了毅否。
快速排序?qū)崿F(xiàn)的思想是將一個數(shù)組分成兩個數(shù)組亚铁，將兩部分進行獨立排序。但是這個分割不和歸并排序一樣螟加，這里的切分位置是取決于數(shù)組的內(nèi)容的徘溢。切分的過程需要滿足以下三個條件
- 對于某個 j, a[j] 已經(jīng)排定吞琐；
- a[low] 到 a[j-1] 的所有元素都不大于 a[j]；
- a[j+1] 到 a[high] 的所有元素都不小于 [j]然爆；
然后遞歸的調(diào)用切分就可以實現(xiàn)排序站粟，因為每次切分都能排定一個元素。要完成這個實現(xiàn)施蜜，需要實現(xiàn)切分方法卒蘸，一般策略是先隨意的取 a[low] 作為切分元素。
算法 如下
public class QuickSort {
public static void sort(Comparable[] a) {
if (Sort.isSorted(a)) {
return;
}
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);
sort(a, low, j - 1);
sort(a, j + 1, high);
}
private static int partition(Comparable[] a, int low, int high) {
int i = low, j = high + 1;
Comparable v = a[low];
while (true) {
while (Sort.less(a[++i], v))
if (i == high)
break;
while (Sort.less(v, a[--j]))
if (j == low)
break;
if (i >= j)
break;
Sort.exchange(a, i, j);
}
Sort.exchange(a, low, j);
return j;
}
}
算法中的 partition() 函數(shù)主要實現(xiàn)的就是將 a[low] 這個元素排定到指定的位置并且將該位置作為返回值翻默，返回給 sort() 函數(shù)缸沃，用于分割數(shù)組，隨著 sort() 函數(shù)的遞歸調(diào)用修械，會將每個元素排定到指定位置趾牧，從而實現(xiàn)排序。
快速排序雖然有很多優(yōu)點肯污，但是有一個潛在的缺點翘单，在切份不平衡時這個程序可能會極為低效。比如說第一次從最小的那個元素切分蹦渣，第二次從第二小的元素進行切分哄芜，這樣的話每次調(diào)用只會移除一個元素，這個時候性能就非常低了柬唯。所以在使用快速排序的時候最好首相將數(shù)組隨機打亂认臊，這樣的話會將上述概率降到最低。
實際上上述快速排序的實現(xiàn)還是有待改進的锄奢，比如說我們可以在數(shù)組特別小的時候失晴，使用插入排序，只需要在 sort() 方法中將遞歸的判定條件改成如下所示
if (high <= low + X){
InsertSort.sort(a,low,high);
return;
}
X 可以是 5 - 15 內(nèi)的數(shù)拘央，這可以在一定程度上改善涂屁，尤其是在小數(shù)組基本有序的情況下。
當然灰伟，現(xiàn)在比較流行的還是三向切分排序拆又，這種算法主要應(yīng)對在數(shù)組中存在大量重復(fù)的情況，算法的基本思想就是首先選取到一個切分元素袱箱，一般是 a[low],然后取出該元素并命名為v遏乔。設(shè)置 lt 指向 low ， gt 指向 high发笔，i 指向 low+1盟萨。 在 i <= gt 的時候執(zhí)行以下操作：
1.如果a[i] < v,那么將 a[i] 和 a[lt] 互換，并且lt 和 i 加 1 了讨。
2.如果a[i] > v捻激，那么將a[i] 與 a[gt] 互換制轰，并且 gt -1.
3.如果 a[i] = v ，那么直接 i +1,不執(zhí)行交換操作胞谭。
待程序跳出以上循環(huán)的時候垃杖，調(diào)用 sort() 方法，并且左邊的數(shù)組以 lt-1 位上界丈屹，右邊的數(shù)組以 gt+1 為下界调俘。這個時候就可以很明顯的看出來，每次切分就不會再將以前已經(jīng)排過序的元素納入數(shù)組旺垒，這樣在元素有大量重復(fù)的情況下可以顯著提高排序效率彩库，當然在隨機情況下，它的效率也是非常好的先蒋。下面來看看具體實現(xiàn)骇钦。
public class Quick3Way {
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 lt = low, i = low + 1, gt = high;
Comparable v = a[low];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0)
Sort.exchange(a, lt++, i++);
else if (cmp > 0)
Sort.exchange(a, i, gt--);
else
i++;
}
sort(a, low, lt - 1);
sort(a, gt + 1, high);
}
}
各個排序算法的比較
為了驗證算法的優(yōu)劣，我對以上算法分別進行了 1 0000數(shù)量級竞漾，10 0000數(shù)量級眯搭，100 0000數(shù)量級的數(shù)組進行了測試，測試結(jié)果如下：
1.1 0000 數(shù)量級
選擇排序 ： 0.112s
插入排序 ： 0.16s
希爾排序 ： 0.016s
歸并排序 ： 0.011s
快速排序 : 0.008s
2.10 0000 數(shù)量級
選擇排序 : 11.19s
插入排序 : 16.521s
希爾排序 : 0.084 s
歸并排序 : 0.114s
快速排序 : 0.066s
3.100 0000 數(shù)量級
選擇排序 : 等了幾分鐘未果
插入排序 : 等了幾分鐘未果
希爾排序 : 2.022s
歸并排序 : 0.742s
快速排序 : 0.521s
上述用于測試的數(shù)據(jù)由 Random 函數(shù)生成的业岁，并且與數(shù)量級相乘鳞仙，比如說 10000 數(shù)量級就是用 (int) (Math.random() * 10000) 生成，由于數(shù)是隨機的笔时，所以上述時間也不是一個固定的值繁扎，但相差不會太大。
有上述實驗結(jié)果反映出來一些問題
- 選擇排序和插入排序?qū)σ?guī)模大的數(shù)組是無能為力的
- 規(guī)模越大糊闽，快速排序和歸并排序的優(yōu)勢就越大，尤其是快速排序
