它們都屬于內(nèi)部排序，也就是只考慮數(shù)據(jù)量較小僅需要使用內(nèi)存的排序算法，他們之間關(guān)系如下：
穩(wěn)定與非穩(wěn)定：
如果一個排序算法能夠保留數(shù)組中重復(fù)元素的相對位置則可以被稱為是穩(wěn)定的。反之，則是非穩(wěn)定的。
直接插入排序
基本思想
通常人們整理橋牌的方法是一張一張的來，將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置。在計(jì)算機(jī)的實(shí)現(xiàn)中，為了要給插入的元素騰出空間，我們需要將其余所有元素在插入之前都向右移動一位。
算法描述
一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
動態(tài)效果如下：
注意：
如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個變種，稱為二分查找插入排序。
代碼實(shí)現(xiàn)
/**
* 通過交換進(jìn)行插入排序，借鑒冒泡排序
*
* @param a
*/
public static void sort(int[] a) {
? ? for (int i = 0; i < a.length - 1; i++) {
? ? ? ? for (int j = i + 1; j > 0; j--) {
? ? ? ? ? ? if (a[j] < a[j - 1]) {
? ? ? ? ? ? ? ? int temp = a[j];
? ? ? ? ? ? ? ? a[j] = a[j - 1];
? ? ? ? ? ? ? ? a[j - 1] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
/**
* 通過將較大的元素都向右移動而不總是交換兩個元素
*
* @param a
*/
public static void sort2(int[] a) {
? ? for (int i = 1; i < a.length; i++) {
? ? ? ? int num = a[i];
? ? ? ? int j;
? ? ? ? for (j = i; j > 0 && num < a[j - 1]; j--) {
? ? ? ? ? ? a[j] = a[j - 1];
? ? ? ? }
? ? ? ? a[j] = num;
? ? }
}
復(fù)雜度分析
直接插入排序復(fù)雜度如下：
平均時間復(fù)雜度最好情況最壞情況空間復(fù)雜度O(n2)O(n2)O(n2)O(1)
比較與總結(jié)
插入排序所需的時間取決于輸入元素的初始順序。例如，對一個很大且其中的元素已經(jīng)有序(或接近有序)的數(shù)組進(jìn)行排序?qū)入S機(jī)順序的數(shù)組或是逆序數(shù)組進(jìn)行排序要快得多。
希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一
希爾排序是先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。
基本思想
將待排序數(shù)組按照步長gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次再將gap折半減小，循環(huán)上述操作；當(dāng)gap=1時，利用直接插入，完成排序。
可以看到步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。一般來說最簡單的步長取值是初次取數(shù)組長度的一半為增量，之后每次再減半，直到增量為1。更好的步長序列取值可以參考維基百科。
算法描述
選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個數(shù) k，對序列進(jìn)行 k 趟排序；
每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
效果如下：
代碼實(shí)現(xiàn)
下面參考《算法》中給出的步長選擇策略，《算法》中給出的解釋是
下面代碼中遞增序列的計(jì)算和使用都很簡單，和復(fù)雜遞增序列的性能接近。當(dāng)可以證明復(fù)雜的序列在最壞情況下的性能要好于我們所使用的遞增序列。更加優(yōu)秀的遞增序列有待我們?nèi)グl(fā)現(xiàn)。
public static void sort(int[] a) {
? ? int length = a.length;
? ? int h = 1;
? ? while (h < length / 3) h = 3 * h + 1;
? ? for (; h >= 1; h /= 3) {
? ? ? ? for (int i = 0; i < a.length - h; i += h) {
? ? ? ? ? ? for (int j = i + h; j > 0; j -= h) {
? ? ? ? ? ? ? ? if (a[j] < a[j - h]) {
? ? ? ? ? ? ? ? ? ? int temp = a[j];
? ? ? ? ? ? ? ? ? ? a[j] = a[j - h];
? ? ? ? ? ? ? ? ? ? a[j - h] = temp;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
復(fù)雜度分析
以下是希爾排序復(fù)雜度:
平均時間復(fù)雜度最好情況最壞情況空間復(fù)雜度O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)
總結(jié)與思考
希爾排序更高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性。排序之初，各個子數(shù)組都很短，排序之后子數(shù)組都是部分有序的，這兩種情況都很適合插入排序。
簡單選擇排序
基本思想
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移到其最終位置上，因此對 n個元素的表進(jìn)行排序總共進(jìn)行至多 n-1 次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
算法描述
從未排序序列中，找到關(guān)鍵字最小的元素
如果最小元素不是未排序序列的第一個元素，將其和未排序序列第一個元素互換
重復(fù)1、2步，直到排序結(jié)束。
動圖效果如下所示：
代碼實(shí)現(xiàn)
public static void sort(int[] a) {
? ? for (int i = 0; i < a.length; i++) {
? ? ? ? int min = i;
? ? ? ? //選出之后待排序中值最小的位置
? ? ? ? for (int j = i + 1; j < a.length; j++) {
? ? ? ? ? ? if (a[j] < a[min]) {
? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //最小值不等于當(dāng)前值時進(jìn)行交換
? ? ? ? if (min != i) {
? ? ? ? ? ? int temp = a[i];
? ? ? ? ? ? a[i] = a[min];
? ? ? ? ? ? a[min] = temp;
? ? ? ? }
? ? }
}
復(fù)雜度分析
以下是選擇排序復(fù)雜度:
總結(jié)與思考
選擇排序的簡單和直觀名副其實(shí)，這也造就了它”出了名的慢性子”，無論是哪種情況，哪怕原數(shù)組已排序完成，它也將花費(fèi)將近n2/2次遍歷來確認(rèn)一遍。即便是這樣，它的排序結(jié)果也還是不穩(wěn)定的。 唯一值得高興的是，它并不耗費(fèi)額外的內(nèi)存空間。
堆排序
1991年的計(jì)算機(jī)先驅(qū)獎獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同發(fā)明了著名的堆排序算法(Heap Sort).
堆的定義如下：nn個元素的序列{k1,k2,..,kn}
當(dāng)且僅當(dāng)滿足下關(guān)系時，稱之為堆。
把此序列對應(yīng)的二維數(shù)組看成一個完全二叉樹。那么堆的含義就是：完全二叉樹中任何一個非也子節(jié)點(diǎn)的值均不大于（或不小于）其左，右孩子節(jié)點(diǎn)的值。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。因此我們可使用大頂堆進(jìn)行升序排序, 使用小頂堆進(jìn)行降序排序。
基本思想
此處以大頂堆為例，堆排序的過程就是將待排序的序列構(gòu)造成一個堆，選出堆中最大的移走，再把剩余的元素調(diào)整成堆，找出最大的再移走，重復(fù)直至有序。
算法描述
先將初始序列K[1..n]K[1..n]建成一個大頂堆, 那么此時第一個元素K1K1最大, 此堆為初始的無序區(qū).
再將關(guān)鍵字最大的記錄K1K1?(即堆頂, 第一個元素)和無序區(qū)的最后一個記錄?KnKn?交換, 由此得到新的無序區(qū)K[1..n?1]K[1..n?1]和有序區(qū)K[n]K[n], 且滿足K[1..n?1].keys?K[n].keyK[1..n?1].keys?K[n].key
交換K1K1?和?KnKn?后, 堆頂可能違反堆性質(zhì), 因此需將K[1..n?1]K[1..n?1]調(diào)整為堆. 然后重復(fù)步驟2, 直到無序區(qū)只有一個元素時停止。
動圖效果如下所示：
代碼實(shí)現(xiàn)
從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆函數(shù)，二是反復(fù)調(diào)用建堆函數(shù)以選擇出剩余未排元素中最大的數(shù)來實(shí)現(xiàn)排序的函數(shù)。
總結(jié)起來就是定義了以下幾種操作：
最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序
堆排序（HeapSort）：移除位在第一個數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
對于堆節(jié)點(diǎn)的訪問：
父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置：(2*i+1);
父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置：(2*i+2);
子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置：floor((i-1)/2);
/**
* @param a
*/
public static void sort(int[] a) {
? ? for (int i = a.length - 1; i > 0; i--) {
? ? ? ? max_heapify(a, i);
? ? ? ? //堆頂元素(第一個元素)與Kn交換
? ? ? ? int temp = a[0];
? ? ? ? a[0] = a[i];
? ? ? ? a[i] = temp;
? ? }
}
/***
*
*? 將數(shù)組堆化
*? i = 第一個非葉子節(jié)點(diǎn)。
*? 從第一個非葉子節(jié)點(diǎn)開始即可。無需從最后一個葉子節(jié)點(diǎn)開始。
*? 葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)，根節(jié)點(diǎn)就是它自己且自己以下值為最大。
*
* @param a
* @param n
*/
public static void max_heapify(int[] a, int n) {
? ? int child;
? ? for (int i = (n - 1) / 2; i >= 0; i--) {
? ? ? ? //左子節(jié)點(diǎn)位置
? ? ? ? child = 2 * i + 1;
? ? ? ? //右子節(jié)點(diǎn)存在且大于左子節(jié)點(diǎn)，child變成右子節(jié)點(diǎn)
? ? ? ? if (child != n && a[child] < a[child + 1]) {
? ? ? ? ? ? child++;
? ? ? ? }
? ? ? ? //交換父節(jié)點(diǎn)與左右子節(jié)點(diǎn)中的最大值
? ? ? ? if (a[i] < a[child]) {
? ? ? ? ? ? int temp = a[i];
? ? ? ? ? ? a[i] = a[child];
? ? ? ? ? ? a[child] = temp;
? ? ? ? }
? ? }
}
復(fù)雜度分析
建立堆的過程, 從length/2 一直處理到0, 時間復(fù)雜度為O(n);
調(diào)整堆的過程是沿著堆的父子節(jié)點(diǎn)進(jìn)行調(diào)整, 執(zhí)行次數(shù)為堆的深度, 時間復(fù)雜度為O(lgn);
堆排序的過程由n次第2步完成, 時間復(fù)雜度為O(nlgn).
總結(jié)與思考
由于堆排序中初始化堆的過程比較次數(shù)較多, 因此它不太適用于小序列。 同時由于多次任意下標(biāo)相互交換位置, 相同元素之間原本相對的順序被破壞了, 因此, 它是不穩(wěn)定的排序。
冒泡排序
我想對于它每個學(xué)過C語言的都會了解，這可能是很多人接觸的第一個排序算法。
基本思想
冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法描述
冒泡排序算法的運(yùn)作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
針對所有的元素重復(fù)以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
代碼實(shí)現(xiàn)
public static void sort(int[] a) {
? ? //外層循環(huán)控制比較的次數(shù)
? ? for (int i = 0; i < a.length - 1; i++) {
? ? ? //內(nèi)層循環(huán)控制到達(dá)位置
? ? ? ? for (int j = 0; j < a.length - i - 1; j++) {
? ? ? ? ? ? //前面的元素比后面大就交換
? ? ? ? ? ? if (a[j] > a[j + 1]) {
? ? ? ? ? ? ? ? int temp = a[j];
? ? ? ? ? ? ? ? a[j] = a[j + 1];
? ? ? ? ? ? ? ? a[j + 1] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
復(fù)雜度分析
以下是冒泡排序算法復(fù)雜度:
冒泡排序是最容易實(shí)現(xiàn)的排序, 最壞的情況是每次都需要交換, 共需遍歷并交換將近n2/2次, 時間復(fù)雜度為O(n2). 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對的, 因此退出循環(huán), 時間復(fù)雜度為O(n). 平均來講, 時間復(fù)雜度為O(n2). 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間, 因此空間復(fù)雜度為常量O(1).
總結(jié)與思考
由于冒泡排序只在相鄰元素大小不符合要求時才調(diào)換他們的位置, 它并不改變相同元素之間的相對順序, 因此它是穩(wěn)定的排序算法。
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
基本思想
快速排序的基本思想：挖坑填數(shù)+分治法。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因?yàn)橐宦牭竭@個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復(fù)雜度達(dá)到了 O(n2)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好。
算法描述
快速排序使用分治策略來把一個序列（list）分為兩個子序列（sub-lists）。步驟為：
從數(shù)列中挑出一個元素，稱為"基準(zhǔn)"（pivot）。
重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會把一個元素?cái)[到它最后的位置去。
代碼實(shí)現(xiàn)
用偽代碼描述如下：
i = L; j = R;將基準(zhǔn)數(shù)挖出形成第一個坑a[i]。
j--，由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。
i++，由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。
再重復(fù)執(zhí)行2，3二步，直到i==j，將基準(zhǔn)數(shù)填入a[i]中
public static void sort(int[] a, int low, int high) {
? ? //已經(jīng)排完
? ? if (low >= high) {
? ? ? ? return;
? ? }
? ? int left = low;
? ? int right = high;
? ? //保存基準(zhǔn)值
? ? int pivot = a[left];
? ? while (left < right) {
? ? ? ? //從后向前找到比基準(zhǔn)小的元素
? ? ? ? while (left < right && a[right] >= pivot)
? ? ? ? ? ? right--;
? ? ? ? a[left] = a[right];
? ? ? ? //從前往后找到比基準(zhǔn)大的元素
? ? ? ? while (left < right && a[left] <= pivot)
? ? ? ? ? ? left++;
? ? ? ? a[right] = a[left];
? ? }
? ? // 放置基準(zhǔn)值，準(zhǔn)備分治遞歸快排
? ? a[left] = pivot;
? ? sort(a, low, left - 1);
? ? sort(a, left + 1, high);
}
上面是遞歸版的快速排序：通過把基準(zhǔn)插入到合適的位置來實(shí)現(xiàn)分治，并遞歸地對分治后的兩個劃分繼續(xù)快排。那么非遞歸版的快排如何實(shí)現(xiàn)呢？
因?yàn)?b>遞歸的本質(zhì)是棧，所以我們非遞歸實(shí)現(xiàn)的過程中，可以借助棧來保存中間變量就可以實(shí)現(xiàn)非遞歸了。在這里中間變量也就是通過Pritation函數(shù)劃分區(qū)間之后分成左右兩部分的首尾指針，只需要保存這兩部分的首尾指針即可。
public static void sortByStack(int[] a) {
? ? Stack<Integer> stack = new Stack<Integer>();
? ? //初始狀態(tài)的左右指針入棧
? ? stack.push(0);
? ? stack.push(a.length - 1);
? ? while (!stack.isEmpty()) {
? ? ? ? //出棧進(jìn)行劃分
? ? ? ? int high = stack.pop();
? ? ? ? int low = stack.pop();
? ? ? ? int pivotIndex = partition(a, low, high);
? ? ? ? //保存中間變量
? ? ? ? if (pivotIndex > low) {
? ? ? ? ? ? stack.push(low);
? ? ? ? ? ? stack.push(pivotIndex - 1);
? ? ? ? }
? ? ? ? if (pivotIndex < high && pivotIndex >= 0) {
? ? ? ? ? ? stack.push(pivotIndex + 1);
? ? ? ? ? ? stack.push(high);
? ? ? ? }
? ? }
}
private static int partition(int[] a, int low, int high) {
? ? if (low >= high) return -1;
? ? int left = low;
? ? int right = high;
? ? //保存基準(zhǔn)的值
? ? int pivot = a[left];
? ? while (left < right) {
? ? ? ? //從后向前找到比基準(zhǔn)小的元素，插入到基準(zhǔn)位置中
? ? ? ? while (left < right && a[right] >= pivot) {
? ? ? ? ? ? right--;
? ? ? ? }
? ? ? ? a[left] = a[right];
? ? ? ? //從前往后找到比基準(zhǔn)大的元素
? ? ? ? while (left < right && a[left] <= pivot) {
? ? ? ? ? ? left++;
? ? ? ? }
? ? ? ? a[right] = a[left];
? ? }
? ? //放置基準(zhǔn)值，準(zhǔn)備分治遞歸快排
? ? a[left] = pivot;
? ? return left;
}
算法改進(jìn)
切換到插入排序
和大多數(shù)遞歸排序算法一樣，改進(jìn)快速排序性能的一個簡單方法基于以下兩點(diǎn)：
對于小數(shù)組，快速排序比插入排序慢
因?yàn)檫f歸，快速排序的sort()方法在小數(shù)組中葉會調(diào)用自己
因此，在排序小數(shù)組時應(yīng)該切換到插入排序。
三者取中法
快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個端點(diǎn)與中點(diǎn)三個記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。
三向快速排序
實(shí)際應(yīng)用中經(jīng)常會出現(xiàn)含有大量重復(fù)元素的數(shù)組。例如，一個元素全部重復(fù)的子數(shù)組就不需要繼續(xù)排序了，但我們的算法還會繼續(xù)將它切分為更小的數(shù)組。在有大量重復(fù)元素的情況下，快速排序的遞歸性會使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn)，這就有很大的改進(jìn)潛力，經(jīng)當(dāng)前實(shí)現(xiàn)的線性對數(shù)級的性能提高到線性級別。
算法描述：
在lt之前的(lo~lt-1)都小于中間值
在gt之前的(gt+1~hi)都大于中間值
在lt~i-1的都等于中間值
在i~gt的都還不確定（最終i會大于gt，即不確定的將不復(fù)存在）
代碼實(shí)現(xiàn)：
public static void sortThreeWay(int[] a, int lo, int hi) {
? ? if (lo >= hi) {
? ? ? ? return;
? ? }
? ? int v = a[lo], lt = lo, i = lo + 1, gt = hi;
? ? while (i <= gt) {
? ? ? ? if (a[i] < v) {
? ? ? ? ? ? swap(a, i++, lt++);
? ? ? ? } else if (a[i] > v) {
? ? ? ? ? ? swap(a, i, gt--);
? ? ? ? } else {
? ? ? ? ? ? i++;
? ? ? ? }
? ? }
? ? sortThreeWay(a, lo, lt - 1);
? ? sortThreeWay(a, gt + 1, hi);
}
private static void swap(int[] a, int i, int j) {
? ? int t = a[i];
? ? a[i] = a[j];
? ? a[j] = t;
}
復(fù)雜度分析
以下是快速排序算法復(fù)雜度:
歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法，1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用，且各層分治遞歸可以同時進(jìn)行。
基本思想
歸并排序算法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序的序列合并為整體有序序列。
算法描述
歸并排序可通過兩種方式實(shí)現(xiàn):
自上而下的遞歸
自下而上的迭代
遞歸法（假設(shè)序列共有n個元素）：
將序列每相鄰兩個數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個序列，排序后每個序列包含兩個元素；
將上述序列再次歸并，形成 floor(n/4)個序列，每個序列包含四個元素；
重復(fù)步驟2，直到所有元素排序完畢。
迭代法
申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
代碼實(shí)現(xiàn)
歸并排序其實(shí)要做兩件事：
分解：將序列每次折半拆分
合并：將劃分后的序列段兩兩排序合并
因此，歸并排序?qū)嶋H上就是兩個操作，拆分+合并
下面是遞歸的方法：
public class Merge {
? ? //歸并所需的輔助數(shù)組
? ? private static int[] aux;
? ? public static void sort(int[] a) {
? ? ? ? //一次性分配空間
? ? ? ? aux = new int[a.length];
? ? ? ? sort(a, 0, a.length - 1);
? ? }
? ? public static void sort(int[] a, int low, int high) {
? ? ? ? if (low >= high) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? int mid = (low + high) / 2;
? ? ? ? //將左半邊排序
? ? ? ? sort(a, low, mid);
? ? ? ? //將右半邊排序
? ? ? ? sort(a, mid + 1, high);
? ? ? ? merge(a, low, mid, high);
? ? }
? ? /**
? ? * 該方法先將所有元素復(fù)制到aux[]中，然后在歸并會a[]中。方法咋歸并時(第二個for循環(huán))
? ? * 進(jìn)行了4個條件判斷：
? ? * - 左半邊用盡(取右半邊的元素)
? ? * - 右半邊用盡(取左半邊的元素)
? ? * - 右半邊的當(dāng)前元素小于左半邊的當(dāng)前元素(取右半邊的元素)
? ? * - 右半邊的當(dāng)前元素大于等于左半邊的當(dāng)前元素(取左半邊的元素)
? ? * @param a
? ? * @param low
? ? * @param mid
? ? * @param high
? ? */
? ? public static void merge(int[] a, int low, int mid, int high) {
? ? ? ? //將a[low..mid]和a[mid+1..high]歸并
? ? ? ? int i = low, 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 (aux[j] < aux[i]) {
? ? ? ? ? ? ? ? a[k] = aux[j++];
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? a[k] = aux[i++];
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
復(fù)雜度分析
以下是歸并排序算法復(fù)雜度:
從效率上看，歸并排序可算是排序算法中的”佼佼者”. 假設(shè)數(shù)組長度為n，那么拆分?jǐn)?shù)組共需logn，, 又每步都是一個普通的合并子數(shù)組的過程， 時間復(fù)雜度為O(n)， 故其綜合時間復(fù)雜度為O(nlogn)。另一方面， 歸并排序多次遞歸過程中拆分的子數(shù)組需要保存在內(nèi)存空間， 其空間復(fù)雜度為O(n)。
總結(jié)與思考
歸并排序最吸引人的性質(zhì)是它能夠保證將任意長度為N的數(shù)組排序所需時間和NlogN成正比，它的主要缺點(diǎn)則是他所需的額外空間和N成正比。
基數(shù)排序
基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)（Tabulation Machine）, 排序器每次只能看到一個列。它是基于元素值的每個位上的字符來排序的。 對于數(shù)字而言就是分別基于個位，十位， 百位或千位等等數(shù)字來排序。
基數(shù)排序（Radix sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
基本思想
它是這樣實(shí)現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列。
基數(shù)排序按照優(yōu)先從高位或低位來排序有兩種實(shí)現(xiàn)方案：
MSD（Most significant digital） 從最左側(cè)高位開始進(jìn)行排序。先按k1排序分組, 同一組中記錄, 關(guān)鍵碼k1相等, 再對各組按k2排序分成子組, 之后, 對后面的關(guān)鍵碼繼續(xù)這樣的排序分組, 直到按最次位關(guān)鍵碼kd對各子組排序后. 再將各組連接起來, 便得到一個有序序列。MSD方式適用于位數(shù)多的序列。
LSD （Least significant digital）從最右側(cè)低位開始進(jìn)行排序。先從kd開始排序，再對kd-1進(jìn)行排序，依次重復(fù)，直到對k1排序后便得到一個有序序列。LSD方式適用于位數(shù)少的序列。
算法描述
我們以LSD為例，從最低位開始，具體算法描述如下：
取得數(shù)組中的最大數(shù)，并取得位數(shù)；
arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；
對radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
代碼實(shí)現(xiàn)
基數(shù)排序：通過序列中各個元素的值，對排序的N個元素進(jìn)行若干趟的“分配”與“收集”來實(shí)現(xiàn)排序。
分配：我們將L[i]中的元素取出，首先確定其個位上的數(shù)字，根據(jù)該數(shù)字分配到與之序號相同的桶中
收集：當(dāng)序列中所有的元素都分配到對應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個待排序列L[]。對新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結(jié)束
public static void sort(int[] arr) {
? ? if (arr.length <= 1) return;
? ? //取得數(shù)組中的最大數(shù)，并取得位數(shù)
? ? int max = 0;
? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? if (max < arr[i]) {
? ? ? ? ? ? max = arr[i];
? ? ? ? }
? ? }
? ? int maxDigit = 1;
? ? while (max / 10 > 0) {
? ? ? ? maxDigit++;
? ? ? ? max = max / 10;
? ? }
? ? //申請一個桶空間
? ? int[][] buckets = new int[10][arr.length];
? ? int base = 10;
? ? //從低位到高位，對每一位遍歷，將所有元素分配到桶中
? ? for (int i = 0; i < maxDigit; i++) {
? ? ? ? int[] bktLen = new int[10];? ? ? ? //存儲各個桶中存儲元素的數(shù)量
? ? ? ? //分配：將所有元素分配到桶中
? ? ? ? for (int j = 0; j < arr.length; j++) {
? ? ? ? ? ? int whichBucket = (arr[j] % base) / (base / 10);
? ? ? ? ? ? buckets[whichBucket][bktLen[whichBucket]] = arr[j];
? ? ? ? ? ? bktLen[whichBucket]++;
? ? ? ? }
? ? ? ? //收集：將不同桶里數(shù)據(jù)挨個撈出來,為下一輪高位排序做準(zhǔn)備,由于靠近桶底的元素排名靠前,因此從桶底先撈
? ? ? ? int k = 0;
? ? ? ? for (int b = 0; b < buckets.length; b++) {
? ? ? ? ? ? for (int p = 0; p < bktLen[b]; p++) {
? ? ? ? ? ? ? ? arr[k++] = buckets[b][p];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println("Sorting: " + Arrays.toString(arr));
? ? ? ? base *= 10;
? ? }
}
復(fù)雜度分析
以下是基數(shù)排序算法復(fù)雜度，其中k為最大數(shù)的位數(shù)：
其中，d 為位數(shù)，r 為基數(shù)，n 為原數(shù)組個數(shù)。在基數(shù)排序中，因?yàn)闆]有比較操作，所以在復(fù)雜上，最好的情況與最壞的情況在時間上是一致的，均為O(d*(n + r))。
總結(jié)和思考
基數(shù)排序更適合用于對時間, 字符串等這些整體權(quán)值未知的數(shù)據(jù)進(jìn)行排序。
基數(shù)排序不改變相同元素之間的相對順序，因此它是穩(wěn)定的排序算法。
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶
計(jì)數(shù)排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數(shù)值
八大排序算法總結(jié)
各種排序性能對比如下:
從時間復(fù)雜度來說：
平方階O(n2)排序：各類簡單排序：直接插入、直接選擇和冒泡排序
線性對數(shù)階O(nlog?n)排序：快速排序、堆排序和歸并排序
O(n1+§))排序，§是介于0和1之間的常數(shù)：希爾排序
線性階O(n)排序：基數(shù)排序，此外還有桶、箱排序
論是否有序的影響：
當(dāng)原表有序或基本有序時，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)，時間復(fù)雜度可降至O（n）；
而快速排序則相反，當(dāng)原表基本有序時，將轉(zhuǎn)化為冒泡排序，時間復(fù)雜度提高為O（n2）；
原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數(shù)排序的時間復(fù)雜度影響不大。
