它們都屬于內(nèi)部排序饵筑，也就是只考慮數(shù)據(jù)量較小僅需要使用內(nèi)存的排序算法，他們之間關(guān)系如下：
穩(wěn)定與非穩(wěn)定：
如果一個(gè)排序算法能夠保留數(shù)組中重復(fù)元素的相對(duì)位置則可以被稱為是穩(wěn)定的处坪。反之根资，則是非穩(wěn)定的。
直接插入排序
基本思想
通常人們整理橋牌的方法是一張一張的來同窘，將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置玄帕。在計(jì)算機(jī)的實(shí)現(xiàn)中，為了要給插入的元素騰出空間想邦，我們需要將其余所有元素在插入之前都向右移動(dòng)一位裤纹。
算法描述
一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)丧没。具體算法描述如下：
從第一個(gè)元素開始鹰椒，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素锡移，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復(fù)步驟3漆际，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
動(dòng)態(tài)效果如下：
注意：
如果比較操作的代價(jià)比交換操作大的話淆珊，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種奸汇，稱為二分查找插入排序套蒂。
代碼實(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;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
/**
* 通過將較大的元素都向右移動(dòng)而不總是交換兩個(gè)元素
*
* @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ù)雜度如下：
平均時(shí)間復(fù)雜度最好情況最壞情況空間復(fù)雜度O(n2)O(n2)O(n2)O(1)
比較與總結(jié)
插入排序所需的時(shí)間取決于輸入元素的初始順序茫蛹。例如操刀，對(duì)一個(gè)很大且其中的元素已經(jīng)有序(或接近有序)的數(shù)組進(jìn)行排序?qū)?huì)比隨機(jī)順序的數(shù)組或是逆序數(shù)組進(jìn)行排序要快得多。
希爾排序
希爾排序婴洼，也稱遞減增量排序算法骨坑，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法柬采。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)欢唾，效率高，即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的粉捻，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一
希爾排序是先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序礁遣，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序肩刃。
基本思想
將待排序數(shù)組按照步長(zhǎng)gap進(jìn)行分組祟霍，然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次再將gap折半減小盈包，循環(huán)上述操作沸呐；當(dāng)gap=1時(shí)，利用直接插入呢燥，完成排序崭添。
可以看到步長(zhǎng)的選擇是希爾排序的重要部分。只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作叛氨。一般來說最簡(jiǎn)單的步長(zhǎng)取值是初次取數(shù)組長(zhǎng)度的一半為增量呼渣，之后每次再減半，直到增量為1寞埠。更好的步長(zhǎng)序列取值可以參考維基百科屁置。
算法描述
選擇一個(gè)增量序列 t1，t2畸裳，……缰犁，tk淳地，其中 ti > tj, tk = 1怖糊；
按增量序列個(gè)數(shù) k帅容，對(duì)序列進(jìn)行 k 趟排序；
每趟排序伍伤，根據(jù)對(duì)應(yīng)的增量 ti并徘，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序扰魂。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理蒋畜，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
效果如下：
代碼實(shí)現(xiàn)
下面參考《算法》中給出的步長(zhǎng)選擇策略徘跪，《算法》中給出的解釋是
下面代碼中遞增序列的計(jì)算和使用都很簡(jiǎn)單置济，和復(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ù)雜度:
平均時(shí)間復(fù)雜度最好情況最壞情況空間復(fù)雜度O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)
總結(jié)與思考
希爾排序更高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性漱贱。排序之初，各個(gè)子數(shù)組都很短进每，排序之后子數(shù)組都是部分有序的接奈，這兩種情況都很適合插入排序利虫。
簡(jiǎn)單選擇排序
基本思想
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法糠惫。它的工作原理如下壤躲。首先在未排序序列中找到最兴赫辍（大）元素，存放到排序序列的起始位置食侮，然后脊奋，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素疙描，然后放到已排序序列的末尾诚隙。以此類推，直到所有元素均排序完畢起胰。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)久又。如果某個(gè)元素位于正確的最終位置上巫延，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素地消，它們當(dāng)中至少有一個(gè)將被移到其最終位置上炉峰，因此對(duì) n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多 n-1 次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中脉执，選擇排序?qū)儆诜浅：玫囊环N疼阔。
算法描述
從未排序序列中，找到關(guān)鍵字最小的元素
如果最小元素不是未排序序列的第一個(gè)元素半夷，將其和未排序序列第一個(gè)元素互換
重復(fù)1婆廊、2步，直到排序結(jié)束巫橄。
動(dòng)圖效果如下所示：
代碼實(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)前值時(shí)進(jìn)行交換
? ? ? ? if (min != i) {
? ? ? ? ? ? int temp = a[i];
? ? ? ? ? ? a[i] = a[min];
? ? ? ? ? ? a[min] = temp;
? ? ? ? }
? ? }
}
復(fù)雜度分析
以下是選擇排序復(fù)雜度:
總結(jié)與思考
選擇排序的簡(jiǎn)單和直觀名副其實(shí)淘邻，這也造就了它”出了名的慢性子”，無論是哪種情況湘换，哪怕原數(shù)組已排序完成宾舅，它也將花費(fèi)將近n2/2次遍歷來確認(rèn)一遍。即便是這樣彩倚，它的排序結(jié)果也還是不穩(wěn)定的筹我。 唯一值得高興的是，它并不耗費(fèi)額外的內(nèi)存空間帆离。
堆排序
1991年的計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者蔬蕊、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同發(fā)明了著名的堆排序算法(Heap Sort).
堆的定義如下：nn個(gè)元素的序列{k1,k2,..,kn}
當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆盯质。
把此序列對(duì)應(yīng)的二維數(shù)組看成一個(gè)完全二叉樹袁串。那么堆的含義就是：完全二叉樹中任何一個(gè)非也子節(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)造成一個(gè)堆，選出堆中最大的移走压储，再把剩余的元素調(diào)整成堆鲜漩，找出最大的再移走，重復(fù)直至有序集惋。
算法描述
先將初始序列K[1..n]K[1..n]建成一個(gè)大頂堆, 那么此時(shí)第一個(gè)元素K1K1最大, 此堆為初始的無序區(qū).
再將關(guān)鍵字最大的記錄K1K1?(即堆頂, 第一個(gè)元素)和無序區(qū)的最后一個(gè)記錄?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ū)只有一個(gè)元素時(shí)停止孕似。
動(dòng)圖效果如下所示：
代碼實(shí)現(xiàn)
從算法描述來看，堆排序需要兩個(gè)過程刮刑，一是建立堆喉祭，二是堆頂與堆的最后一個(gè)元素交換位置养渴。所以堆排序有兩個(gè)函數(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）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)蔽氨，并做最大堆調(diào)整的遞歸運(yùn)算
對(duì)于堆節(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);
? ? ? ? //堆頂元素(第一個(gè)元素)與Kn交換
? ? ? ? int temp = a[0];
? ? ? ? a[0] = a[i];
? ? ? ? a[i] = temp;
? ? }
}
/***
*
*? 將數(shù)組堆化
*? i = 第一個(gè)非葉子節(jié)點(diǎn)藐唠。
*? 從第一個(gè)非葉子節(jié)點(diǎn)開始即可。無需從最后一個(gè)葉子節(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, 時(shí)間復(fù)雜度為O(n);
調(diào)整堆的過程是沿著堆的父子節(jié)點(diǎn)進(jìn)行調(diào)整, 執(zhí)行次數(shù)為堆的深度, 時(shí)間復(fù)雜度為O(lgn);
堆排序的過程由n次第2步完成, 時(shí)間復(fù)雜度為O(nlgn).
總結(jié)與思考
由于堆排序中初始化堆的過程比較次數(shù)較多, 因此它不太適用于小序列泄伪。 同時(shí)由于多次任意下標(biāo)相互交換位置, 相同元素之間原本相對(duì)的順序被破壞了, 因此, 它是不穩(wěn)定的排序殴蓬。
冒泡排序
我想對(duì)于它每個(gè)學(xué)過C語言的都會(huì)了解匿级，這可能是很多人接觸的第一個(gè)排序算法。
基本思想
冒泡排序（Bubble Sort）是一種簡(jiǎn)單的排序算法染厅。它重復(fù)地走訪過要排序的數(shù)列痘绎，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來肖粮。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換孤页，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端涩馆。
算法描述
冒泡排序算法的運(yùn)作如下：
比較相鄰的元素行施。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)魂那。
對(duì)每一對(duì)相鄰元素作同樣的工作蛾号，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后涯雅，最后的元素會(huì)是最大的數(shù)鲜结。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)活逆。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟精刷，直到?jīng)]有任何一對(duì)數(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次, 時(shí)間復(fù)雜度為O(n2). 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對(duì)的, 因此退出循環(huán), 時(shí)間復(fù)雜度為O(n). 平均來講, 時(shí)間復(fù)雜度為O(n2). 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間, 因此空間復(fù)雜度為常量O(1).
總結(jié)與思考
由于冒泡排序只在相鄰元素大小不符合要求時(shí)才調(diào)換他們的位置, 它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法蔗候。
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法怒允。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較锈遥。在最壞狀況下則需要 Ο(n2) 次比較纫事，但這種狀況并不常見仰美。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快儿礼，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來咖杂。
基本思想
快速排序的基本思想：挖坑填數(shù)+分治法。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）蚊夫。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用诉字。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法知纷。
快速排序的名字起的是簡(jiǎn)單粗暴壤圃，因?yàn)橐宦牭竭@個(gè)名字你就知道它存在的意義，就是快琅轧，而且效率高伍绳！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)乍桂，但是人家就是優(yōu)秀冲杀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好。
算法描述
快速排序使用分治策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）睹酌。步驟為：
從數(shù)列中挑出一個(gè)元素权谁，稱為"基準(zhǔn)"（pivot）即横。
重新排序數(shù)列丢烘，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面仪搔，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）集灌。在這個(gè)分區(qū)結(jié)束之后璃吧，該基準(zhǔn)就處于數(shù)列的中間位置作喘。這個(gè)稱為分區(qū)（partition）操作惧笛。
遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序仲翎。
遞歸到最底部時(shí)壶辜，數(shù)列的大小是零或一悯舟，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束士复，因?yàn)樵诿看蔚牡╥teration）中图谷，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
代碼實(shí)現(xiàn)
用偽代碼描述如下：
i = L; j = R;將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]阱洪。
j--便贵，由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑a[i]中冗荸。
i++承璃，由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑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)分治轴猎，并遞歸地對(duì)分治后的兩個(gè)劃分繼續(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)快速排序性能的一個(gè)簡(jiǎn)單方法基于以下兩點(diǎn)：
對(duì)于小數(shù)組惫搏，快速排序比插入排序慢
因?yàn)檫f歸具温，快速排序的sort()方法在小數(shù)組中葉會(huì)調(diào)用自己
因此，在排序小數(shù)組時(shí)應(yīng)該切換到插入排序晶府。
三者取中法
快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的桂躏。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)钻趋，快排序反而蛻化為冒泡排序川陆。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄蛮位，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄较沪。
三向快速排序
實(shí)際應(yīng)用中經(jīng)常會(huì)出現(xiàn)含有大量重復(fù)元素的數(shù)組。例如失仁，一個(gè)元素全部重復(fù)的子數(shù)組就不需要繼續(xù)排序了尸曼，但我們的算法還會(huì)繼續(xù)將它切分為更小的數(shù)組。在有大量重復(fù)元素的情況下萄焦，快速排序的遞歸性會(huì)使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn)控轿，這就有很大的改進(jìn)潛力，經(jīng)當(dāng)前實(shí)現(xiàn)的線性對(duì)數(shù)級(jí)的性能提高到線性級(jí)別拂封。
算法描述：
在lt之前的(lo~lt-1)都小于中間值
在gt之前的(gt+1~hi)都大于中間值
在lt~i-1的都等于中間值
在i~gt的都還不確定（最終i會(huì)大于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）的一個(gè)非常典型的應(yīng)用在抛，且各層分治遞歸可以同時(shí)進(jìn)行。
基本思想
歸并排序算法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表萧恕，即把待排序序列分為若干個(gè)子序列刚梭，每個(gè)子序列是有序的肠阱。然后再把有序的序列合并為整體有序序列。
算法描述
歸并排序可通過兩種方式實(shí)現(xiàn):
自上而下的遞歸
自下而上的迭代
遞歸法（假設(shè)序列共有n個(gè)元素）：
將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作朴读，形成 floor(n/2)個(gè)序列屹徘，排序后每個(gè)序列包含兩個(gè)元素；
將上述序列再次歸并衅金，形成 floor(n/4)個(gè)序列缘回，每個(gè)序列包含四個(gè)元素；
重復(fù)步驟2典挑，直到所有元素排序完畢酥宴。
迭代法
申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和您觉，該空間用來存放合并后的序列
設(shè)定兩個(gè)指針拙寡，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間琳水，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
代碼實(shí)現(xiàn)
歸并排序其實(shí)要做兩件事：
分解：將序列每次折半拆分
合并：將劃分后的序列段兩兩排序合并
因此肆糕，歸并排序?qū)嶋H上就是兩個(gè)操作，拆分+合并
下面是遞歸的方法：
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[]中在孝，然后在歸并會(huì)a[]中诚啃。方法咋歸并時(shí)(第二個(gè)for循環(huán))
? ? * 進(jìn)行了4個(gè)條件判斷：
? ? * - 左半邊用盡(取右半邊的元素)
? ? * - 右半邊用盡(取左半邊的元素)
? ? * - 右半邊的當(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ù)組長(zhǎng)度為n私沮，那么拆分?jǐn)?shù)組共需logn始赎，, 又每步都是一個(gè)普通的合并子數(shù)組的過程， 時(shí)間復(fù)雜度為O(n)仔燕， 故其綜合時(shí)間復(fù)雜度為O(nlogn)造垛。另一方面， 歸并排序多次遞歸過程中拆分的子數(shù)組需要保存在內(nèi)存空間晰搀， 其空間復(fù)雜度為O(n)五辽。
總結(jié)與思考
歸并排序最吸引人的性質(zhì)是它能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需時(shí)間和NlogN成正比，它的主要缺點(diǎn)則是他所需的額外空間和N成正比外恕。
基數(shù)排序
基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)（Tabulation Machine）, 排序器每次只能看到一個(gè)列杆逗。它是基于元素值的每個(gè)位上的字符來排序的。 對(duì)于數(shù)字而言就是分別基于個(gè)位鳞疲，十位罪郊， 百位或千位等等數(shù)字來排序。
基數(shù)排序（Radix sort）是一種非比較型整數(shù)排序算法建丧，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字排龄，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)橄维。
基本思想
它是這樣實(shí)現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度尺铣，數(shù)位較短的數(shù)前面補(bǔ)零。然后争舞，從最低位開始凛忿，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后竞川，數(shù)列就變成一個(gè)有序序列店溢。
基數(shù)排序按照優(yōu)先從高位或低位來排序有兩種實(shí)現(xiàn)方案：
MSD（Most significant digital） 從最左側(cè)高位開始進(jìn)行排序。先按k1排序分組, 同一組中記錄, 關(guān)鍵碼k1相等, 再對(duì)各組按k2排序分成子組, 之后, 對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組, 直到按最次位關(guān)鍵碼kd對(duì)各子組排序后. 再將各組連接起來, 便得到一個(gè)有序序列委乌。MSD方式適用于位數(shù)多的序列床牧。
LSD （Least significant digital）從最右側(cè)低位開始進(jìn)行排序。先從kd開始排序遭贸，再對(duì)kd-1進(jìn)行排序戈咳，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列壕吹。LSD方式適用于位數(shù)少的序列著蛙。
算法描述
我們以LSD為例，從最低位開始耳贬，具體算法描述如下：
取得數(shù)組中的最大數(shù)踏堡，并取得位數(shù)；
arr為原始數(shù)組咒劲，從最低位開始取每個(gè)位組成radix數(shù)組顷蟆；
對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
代碼實(shí)現(xiàn)
基數(shù)排序：通過序列中各個(gè)元素的值缎患，對(duì)排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來實(shí)現(xiàn)排序慕的。
分配：我們將L[i]中的元素取出，首先確定其個(gè)位上的數(shù)字挤渔，根據(jù)該數(shù)字分配到與之序號(hào)相同的桶中
收集：當(dāng)序列中所有的元素都分配到對(duì)應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[]风题。對(duì)新形成的序列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;
? ? }
? ? //申請(qǐng)一個(gè)桶空間
? ? int[][] buckets = new int[10][arr.length];
? ? int base = 10;
? ? //從低位到高位眼刃，對(duì)每一位遍歷，將所有元素分配到桶中
? ? for (int i = 0; i < maxDigit; i++) {
? ? ? ? int[] bktLen = new int[10];? ? ? ? //存儲(chǔ)各個(gè)桶中存儲(chǔ)元素的數(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ù)挨個(gè)撈出來,為下一輪高位排序做準(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ù)組個(gè)數(shù)昵骤。在基數(shù)排序中树碱，因?yàn)闆]有比較操作，所以在復(fù)雜上变秦，最好的情況與最壞的情況在時(shí)間上是一致的成榜，均為O(d*(n + r))。
總結(jié)和思考
基數(shù)排序更適合用于對(duì)時(shí)間, 字符串等這些整體權(quán)值未知的數(shù)據(jù)進(jìn)行排序蹦玫。
基數(shù)排序不改變相同元素之間的相對(duì)順序赎婚，因此它是穩(wěn)定的排序算法。
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念樱溉，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值
八大排序算法總結(jié)
各種排序性能對(duì)比如下:
從時(shí)間復(fù)雜度來說：
平方階O(n2)排序：各類簡(jiǎn)單排序：直接插入挣输、直接選擇和冒泡排序
線性對(duì)數(shù)階O(nlog?n)排序：快速排序、堆排序和歸并排序
O(n1+§))排序福贞，§是介于0和1之間的常數(shù)：希爾排序
線性階O(n)排序：基數(shù)排序歧焦，此外還有桶、箱排序
論是否有序的影響：
當(dāng)原表有序或基本有序時(shí)肚医，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)绢馍，時(shí)間復(fù)雜度可降至O（n）；
而快速排序則相反肠套，當(dāng)原表基本有序時(shí)舰涌，將轉(zhuǎn)化為冒泡排序，時(shí)間復(fù)雜度提高為O（n2）你稚；
原表是否有序瓷耙，對(duì)簡(jiǎn)單選擇排序、堆排序刁赖、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大搁痛。
