搞懂基本排序算法
上篇文章寫了關(guān)于 Java 內(nèi)部類的基本知識钧舌，感興趣的朋友可以去看一下：搞懂 JAVA 內(nèi)部類流椒；本文寫的內(nèi)容是最近學習的算法相關(guān)知識中的基本排序算法敏簿，排序算法也算是面試中的常客了，實際上也是算法中最基本的知識惯裕。由于 Android 開發(fā)中用到的地方并不多温数，所以也很容易遺忘，但是為了進階高級工程師鞏固基本算法和數(shù)據(jù)結(jié)構(gòu)也是必修課程之一轻猖。
基本排序算法按難易程度來說可以分為：冒泡排序帆吻，選擇排序，插入排序咙边，歸并排序猜煮，選擇排序。本文也將從這五種排序算法來講解各自的中心思想败许，和 Java 實現(xiàn)方式王带。
冒泡排序
冒泡排序恐怕是我們計算機專業(yè)課程上以第一個接觸到的排序算法，也算是一種入門級的排序算法市殷。
冒泡排序雖然簡單但是對于 n 數(shù)量級很大的時候愕撰，其實是很低效率的。所以實際生產(chǎn)中很少使用這種排序算法醋寝。下面我們看下這種算法的具體實現(xiàn)思路：
冒泡排序算法原理：
- 比較相鄰的元素搞挣。如果第一個比第二個大，就交換他們兩個音羞。
- 對每一對相鄰元素作同樣的工作囱桨，從開始第一對到結(jié)尾的最后一對。這步做完后嗅绰，最后的元素會是最大的數(shù)舍肠。
- 針對所有的元素重復以上的步驟，除了最后一個窘面。
- 持續(xù)每次對越來越少的元素重復上面的步驟翠语，直到?jīng)]有任何一對數(shù)字需要比較。
一次比較過程如圖所示（圖片 Google 來的侵刪）
冒泡排序 Java 代碼實現(xiàn)：
/**
* @param arr 待排序數(shù)組
* @param n 數(shù)組長度
*/
private static void BubbleSort(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 1; j < n - i - 1; j++) {
if (arr[j - 1] > arr[j]) {
//交換兩個元素
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
冒泡排序時間空間復雜度及算法穩(wěn)定性分析
對于長度為 n 的數(shù)組财边，冒泡排序需要經(jīng)過 n(n-1)/2 次比較肌括，最壞的情況下，即數(shù)組本身是倒序的情況下酣难，需要經(jīng)過 n(n-1)/2 次交換们童，所以其
冒泡排序的算法時間平均復雜度為O(n2)【校空間復雜度為 O(1)。
可以想象一下：如果兩個相鄰的元素相等是不會進行交換操作的跷跪，也就是兩個相等元素的先后順序是不會改變的馋嗜。如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個元素相鄰起來吵瞻，最終也不會交換它倆的位置葛菇，所以相同元素經(jīng)過排序后順序并沒有改變甘磨。
所以冒泡排序是一種穩(wěn)定排序算法。所以冒泡排序是穩(wěn)定排序眯停。這也正是算法穩(wěn)定性的定義：
排序算法的穩(wěn)定性：通俗地講就是能保證排序前兩個相等的數(shù)據(jù)其在序列中的先后位置順序與排序后它們兩個先后位置順序相同济舆。
冒泡排序總結(jié)：
- 冒泡排序的算法時間平均復雜度為O(n2)。
- 空間復雜度為 O(1)莺债。
- 冒泡排序為穩(wěn)定排序滋觉。
選擇排序
選擇排序是另一種簡單的排序算法。選擇排序之所以叫選擇排序就是在一次遍歷過程中找到最小元素的角標位置齐邦，然后把它放到數(shù)組的首端椎侠。我們排序過程都是在尋找剩余數(shù)組中的最小元素，所以就叫做選擇排序措拇。
選擇排序的思想
選擇排序的思想也很簡單：
- 從待排序序列中我纪，找到關(guān)鍵字最小的元素；起始假定第一個元素為最小
- 如果最小元素不是待排序序列的第一個元素丐吓，將其和第一個元素互換浅悉；
- 從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素券犁，重復1术健，2步，直到排序結(jié)束族操。
示意圖：
選擇排序 Java 代碼實現(xiàn)：
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
// for 循環(huán) i 之后所有的數(shù)字 找到剩余數(shù)組中最小值得索引
for (int j = i + 1; j < n; j++) {
if (arr[j]< arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
/**
* 角標的形式 交換元素
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
選擇排序時間空間復雜度及算法穩(wěn)定性分析
上述 java 代碼可以看出我們除了交換元素并未開辟額外的空間苛坚，所以額外的空間復雜度為O(1)。
對于時間復雜度而言色难，選擇排序序冒泡排序一樣都需要遍歷 n(n-1)/2 次,但是相對于冒泡排序來說每次遍歷只需要交換一次元素泼舱，這對于計算機執(zhí)行來說有一定的優(yōu)化。但是選擇排序也是名副其實的慢性子枷莉，即使是有序數(shù)組娇昙，也需要進行 n(n-1)/2 次比較，所以其時間復雜度為O(n2)笤妙。
即便無論如何也要進行n(n-1)/2 次比較冒掌，選擇排序仍是不穩(wěn)定的排序算法，我們舉一個例子如：序列5 8 5 2 9蹲盘， 我們知道第一趟選擇第1個元素5會與2進行交換股毫，那么原序列中兩個5的相對先后順序也就被破壞了。
選擇排序總結(jié)：
- 選擇排序的算法時間平均復雜度為O(n2)召衔。
- 選擇排序空間復雜度為 O(1)铃诬。
- 選擇排序為不穩(wěn)定排序。
插入排序
對于插入排序，大部分資料都是使用撲克牌整理作為例子來引入的趣席，我們打牌都是一張一張摸牌的兵志，沒摸到一張牌就會跟手里所有的牌比較來選擇合適的位置插入這張牌，這也就是直接插入排序的中心思想宣肚，我們先來看下動圖：
[圖片上傳失敗...(image-9dcd7b-1519835757103)]
相信大家看完動圖以后大概知道了插入排序的實現(xiàn)思路了想罕。那么我們就來說下插入排序的思想。
插入排序的思想
- 從第一個元素開始霉涨，該元素可以認為已經(jīng)被排序
- 取出下一個元素按价，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟 3嵌纲，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟 2~5
插入排序的 Java 實現(xiàn)：
下面先看下最基本的實現(xiàn)：
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
//內(nèi)層循環(huán)比較 i 與前邊所有元素值俘枫，如果 j 索引所指的值小于 j- 1 則交換兩者的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
swap(arr,j-1,j);
}
}
}
在上述算法實現(xiàn)中我們每次尋找 i 應該處在數(shù)組中哪個為位置的時候，都是以交換當前元素與上一個元素為代價的逮走，我們知道交換操作是要比賦值操作要費時的鸠蚪，因為每次交換都需要經(jīng)過三次賦值操作，我們想一下我們玩撲克的時候沒有拿起一張牌一個個向前挪知道放到其該放的位置的吧师溅，都是拿出這張牌茅信，找到位置就插進去（突然邪惡），實際上我們是將這個位置以后的牌一次向后挪了一個位置墓臭，那么用Java 代碼是否能實現(xiàn)呢蘸鲸？答案肯定是可以的：
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
//拎出來當前未排序的這樣牌
int e = arr[i];
//尋找其該放的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
arr[j]= arr[j-1];
}
//循環(huán)結(jié)束后 arr[j] >= arr[j-1] 那么 j 角標就是e 應該在的位置。
arr[j] = e;
}
}
插入排序的時間復雜度和空間復雜度分析
對于插入的時間復雜度和空間復雜度窿锉，通過代碼就可以看出跟選擇和冒泡來說沒什么區(qū)別同屬于 O(n2) 級別的時間復雜度算法 酌摇，只是遍歷方式有原來的 n n-1 n-2 ... 1，變成了 1 2 3 ... n 了嗡载。最終得到時間復雜度都是 n(n-1)/2窑多。
對于穩(wěn)定性來說千所，插入排序和冒泡一樣藏姐，并不會改變原有的元素之間的順序重窟，如果遇見一個與插入元素相等的充边，那么把待插入的元素放在相等元素的后面。所以姻锁，相等元素的前后順序沒有改變嫩痰，從原無序序列出去的順序仍是排好序后的順序睹限，所以插入排序是穩(wěn)定的铲掐。
對于插入排序這里說一個非常重要的一點就是：由于這個算法可以提前終止內(nèi)層比較（ arr[j-1] > arr[j]）所以這個排序算法很有用拾弃！因此對于一些 NlogN 級別的算法，后邊的歸并和快速都屬于這個級別的摆霉，算法來說對于 n 小于一定級別的時候（Array.sort 中使用的是47）都可以用插入算法來優(yōu)化,另外對于近乎有序的數(shù)組來說這個提前終止的方式就顯得更加又有優(yōu)勢了砸彬。
插入排序總結(jié)：
- 插入排序的算法時間平均復雜度為O(n2)颠毙。
- 插入排序空間復雜度為 O(1)。
- 插入排序為穩(wěn)定排序砂碉。
- 插入排序?qū)τ诮跤行虻臄?shù)組來說效率更高，插入排序可用來優(yōu)化高級排序算法
歸并排序
接下來我們看一個 NlogN 級別的排序算法刻两，歸并算法增蹭。 歸并算法正如其名字一樣采用歸并的方法進行排序：
我們總是可以將一個數(shù)組一分為二，然后二分為四直到磅摹，每一組只有兩個元素滋迈，這可以理解為個遞歸的過程，然后將兩個元素進行排序户誓，之后再將兩個元素為一組進行排序饼灿。直到所有的元素都排序完成。同樣我們來看下邊這個動圖帝美。
歸并算法的思想
歸并算法其實可以分為遞歸法和迭代法（自低向上歸并）碍彭，兩種實現(xiàn)對于最小集合的歸并操作思想是一樣的區(qū)別在于如何劃分數(shù)組，我們先介紹下算法最基本的操作：
- 申請空間悼潭，使其大小為兩個已經(jīng)排序序列之和庇忌，該空間用來存放合并后的序列
- 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素舰褪，選擇相對小的元素放入到合并空間皆疹，并移動指針到下一位置
- 重復步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
假設(shè)我們現(xiàn)在在對一個數(shù)組的 arr[l...r] 部分進行歸并，按照上述歸并思想我們可將數(shù)組分為兩部分 假設(shè)為 arr[l...mid] 和 arr[mid+1...r]兩部分占拍，注意這兩部分可能長度并不相同略就，因為基數(shù)個數(shù)的數(shù)組劃分的時候總是能得到一個 長度為1 和長度為2 的部分進行歸并.
那么我們按照上述思路進行代碼編寫：
歸并排序的 Java 實現(xiàn)：
/**
* arr[l,mid] 和 arr[mid+1,r] 兩部分進行歸并
*/
private static void merge(int[] arr, int l, int mid, int r) {
// 復制等待歸并數(shù)組 用來進行比較操作，最將原來的 arr 每個角標賦值為正確的元素
int[] aux = new int[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = arr[i];
}
int i = l;
int j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
//說明左邊部分已經(jīng)全都放進數(shù)組了
arr[k] = aux[j - l];
j++;
} else if (j > r) {
//說明左邊部分已經(jīng)全都放進數(shù)組了
arr[k] = aux[i - l];
i++;
} else if (aux[i - l] < aux[j - l]) {
//當左半個數(shù)組的元素值小于右邊數(shù)組元素值得時候 賦值為左邊的元素值
arr[k] = aux[i - l];
i++;
} else {
//當左半個數(shù)組的元素值大于等于右邊數(shù)組元素值得時候 賦值為左邊的元素值 這樣也保證了排序的穩(wěn)定性
arr[k] = aux[j - l];
j++;
}
}
}
相信大家配合剛才的動圖和上述算法實現(xiàn)已經(jīng)理解了歸并算法了晃酒，如果感到迷糊的話可以試著拿個一個數(shù)組在紙上演算一下歸并的過程表牢，相信大家一定可以理解。上述只是實現(xiàn)了算法核心部分掖疮，那么我們應該怎么對整個數(shù)組來進行排序呢初茶？上邊也提到了有兩種方法，一種是遞歸劃分法浊闪，一種是迭代遍歷法（自低向上）那么我們先來開來看遞歸實現(xiàn)：
/**
*
* @param arr 待排序數(shù)組
* @param l 其實元素角標 0
* @param r 最后一個元素角標 n -1
*/
private static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
//開始歸并排序 向下取整
int mid = (l + r) / 2;
//遞歸劃分數(shù)組
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
//檢查是否上一步歸并完的數(shù)組是否有序恼布，如果有序則直接進行下一次歸并
if (arr[mid] <= arr[mid + 1]) {
return;
}
//將兩邊的元素歸并排序
merge(arr, l, mid, r);
}
如果對遞歸過程不理解可以配合下邊這個圖來理解（圖片來自網(wǎng)上，侵刪）：
當然我們merge先對左半部分進行的也就是先進行到Level3的左邊最底層 8 | 6 搁宾，然后歸并完成后進行右邊遞歸到底 最終是 8 6 2 3 | 1 5 7 4 進行歸并折汞。
對于迭代實現(xiàn)歸并其實和遞歸實現(xiàn)有所不同，迭代的時候我們是將數(shù)組分為 一個一個的元素盖腿，然后每兩個歸并一次爽待，第二次我們將數(shù)組每兩個分一組损同，兩個兩個的歸并，知道分組大小等于待歸并數(shù)組長度為止鸟款，即先局部排序膏燃，逐步擴大到全局排序
/**
* 自低向上的歸并排序
*
* @param n 為數(shù)組長度
* @param arr 數(shù)組
*/
private static void mergeSortBU(Integer[] arr, int n) {
//外層遍歷從歸并區(qū)間長度為1 開始 每次遞增一倍的空間 1 2 4 8 sz 需要遍歷到數(shù)組長度那么大
//sz = 1 : [0] [1]...
//sz = 2 : [0,1] [2.3] ...
//sz = 4 : [0..3] [4...7] ...
for (int sz = 1; sz <= n; sz += sz) {
//內(nèi)層遍歷要比較 arr[i,i+sz-1] arr[i+sz,i+sz+sz-1] 兩個區(qū)間的大小 也就是每次對 sz - 1 大小的數(shù)組空間進行歸并
// 注意每次 i 遞增 兩個 sz 的長度 ，因為每次 merge 的時候已經(jīng)歸并了兩個 sz 長度 部分的數(shù)組
for (int i = 0; i + sz < n; i += sz + sz) {
merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));
}
}
}
比如我們看第一次是 sz = 1 個長度的歸并即 i = 0 i = 1 的元素歸并 下次歸并應該為 i= 2 i = 3 一次類推 所以內(nèi)層循環(huán) i 每次應該遞增 兩個 sz 那么大 為了避免角標越界且保證歸并的右半部分存在 所以 i + sz < n ,又考慮到數(shù)組長度為奇數(shù)的情況何什，所以右半邊的右邊為 Math.min(i + sz + sz - 1, n - 1)组哩；可以參考下邊的圖片：
歸并排序的時間復雜度和空間復雜度分析
其實對于歸并排序的時間復雜對有一個遞歸公式來推斷出時間復雜度，但簡單來講假設(shè)數(shù)組長度為 N 处渣，那么我們就有 logN 次劃分區(qū)間伶贰，而最終會劃分為常數(shù) 級別的歸并，將所有層的歸并時間加起來得到了一個 NlogN罐栈，想要了解歸并排序時間復雜度講解的同學可以左轉(zhuǎn) 歸并排序及其時間復雜度分析黍衙，這里不再過多講解。
對于空間復雜度荠诬，我們通過算法實現(xiàn)可以看出我們歸并過程申請了 長度為 N 的臨時數(shù)組琅翻，來進行歸并所以空間復雜度為 O(n);
又由于我們在排序過程中對于 aux[i - l] = aux[j - l] 并沒有進行位置交換直接取得靠前的元素先賦值，所以算法是穩(wěn)定的浅妆。
** 歸并排序總結(jié)：**
- 歸并排序的算法時間平均復雜度為O(nlog(n))望迎。
- 歸并排序空間復雜度為 O(n)。
- 歸并排序為穩(wěn)定排序凌外。
- 對于
快速排序
快速排序為應用最多的排序算法辩尊，因為快速二字而聞名】导快速排序和歸并排序一樣摄欲，采用的都是分治思想。分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題疮薇。遞歸地解這些子問題胸墙，然后將這些子問題的解組合為原問題的解。我們只需關(guān)注最小問題該如何求解按咒，和如何去遞歸既可以得到正確的算法實現(xiàn)迟隅。快速排序可以分為：單路快速排序励七，雙路快速排序智袭，三路快速排序，他們區(qū)別在于選取幾個指針來對數(shù)組進行遍歷下面我們依次來講解掠抬。
單路快速算法的思想：
首先我們選取數(shù)組中的一個數(shù)吼野，將其放在合適的位置，這個位置左邊的數(shù)全部小于該數(shù)值两波，這個位置右邊的數(shù)全部大于該數(shù)值 瞳步。
假設(shè)數(shù)組為
arr[l...r]假設(shè)指定數(shù)值為數(shù)組第一個元素int v = arr[l]闷哆，假設(shè) j 標記為比 v 小的最后一個元素， 即arr[j+1] > v单起。當前考察的元素為 i 則有arr[l + 1 ... j] < v 抱怔， arr[j+1,i) >= v如上圖所示。假設(shè)正在考察的元素值為 e 嘀倒，
e >= v的時候我們只需交將不動野蝇，直接 i++ 去考察下一個元素，當
e < v由上述假設(shè)我們需要將 e 放在<v 的部分 括儒，此時我們只需將arr[j]和arr[i]交換一下位置即可。最后一個元素考察完成以后锐想，我們再講
arr[l]和arr[j]調(diào)換一下位置就可以了帮寻。上述遍歷完成以后
arr[l + 1 ... j] < v ， arr[j+1,i) >= v就滿足了赠摇，接下來我們只需要遞歸的去考察 arr[l + 1 ... j] 和 arr[j+1,r] 即可固逗。
單路快速排序的 Java 實現(xiàn):
private static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// p 為 第一次 排序完成后 v 應該在的位置，即分治的劃分點
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
private static int partition(Integer[] arr, int l, int r) {
// 為了提高效率藕帜，減少造成快速排序的遞歸樹不均勻的概率烫罩，
// 對于一個數(shù)組，每次隨機選擇的數(shù)為當前 partition 操作中最小最大元素的可能性為 1/n
int randomNum = (int) (Math.random() * (r - l + 1) + l);
swap(arr, l, randomNum);
int v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr, j + 1, i);
j++;
}
}
swap(arr, l, j);
return j;
}
private static void swap( int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
對于上述算法中為什么選取了當前排序數(shù)組中隨機一個元素進行比較洽故，假設(shè)我們在考察的數(shù)組已經(jīng)為已經(jīng)排序好的數(shù)組贝攒，那么我們遞歸樹就會向右側(cè)延伸 N 的深度，這種情況使我們不想要看到的时甚，如果我們每次 partition 都隨機從數(shù)組中取一個數(shù)隘弊，那么這個數(shù)是當前排序數(shù)組中最小元素可能性為 1/n 那么每次都取到最小的數(shù)的可能性就很低了。
雙路快速排序算法思想：
跟單路一樣荒适，雙路快速排序梨熙，同樣選擇數(shù)組的第一個元素當做標志位（經(jīng)過隨機選擇后的）
雙路快速排序要求有兩個指針，指針 i j 分別指向 l+1 和 r 的位置然后兩者同時向數(shù)組中間遍歷 在遍歷過程中要保證
arr[l+1 ... i) <= v刀诬， arr(j....r] >= v因此我們可以初始化 i = l+1 以保證左側(cè)區(qū)間初始為空咽扇，j = r 保證右側(cè)空間為空遍歷過程中要 i <= r 且 arr[i] <= v 的時候 i ++ 就可以了 當 arr[i] > v 時表示遇到了 i 的值大于 v 數(shù)值 此刻能等待 j 角標的值，從右向左遍歷數(shù)組 當 arr[i] < v 表示遇到了 j 的值小于 v 的元素陕壹，它不該在這個位置呆著质欲，
得到了 i j 的角標后 先要判斷是否到了循環(huán)結(jié)束的時候了，即 i 是否已經(jīng) 大于 j 了帐要。
否則 應該講 i 位置的元素和 j 位置的元素交換位置把敞，然后 i++ j-- 繼續(xù)循環(huán)
遍歷結(jié)束的條件是 i>j 此時 arr[j]為最后一個小于 v 的元素 arr[i] 為第一個大于 v 的元素 因此 j 這個位置 就應該是 v 所應該在數(shù)組中的位置 因此遍歷結(jié)束后需要交換 arr[l] 與 arr[j]
雙路快速排序的 Java 實現(xiàn):
private static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 這里 p 為 小于 v 的最后一個元素，=v 的第一個元素
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
private static int partition(int[] arr, int l, int r) {
// 為了提高效率榨惠，減少造成快速排序的遞歸樹不均勻的概率奋早，
// 對于一個數(shù)組盛霎，每次隨機選擇的數(shù)為當前 partition 操作中最小最大元素的可能性降低
int randomNum = (int) (Math.random() * (r - l + 1) + l);
swap(arr, l, randomNum);
int v = arr[l];
int i = l + 1;
int j = r;
while (true) {
while (i <= r && arr[i] <= v) i++;
while (j >= l + 1 && arr[j] >= v) j--;
if (i > j) break;
swap(arr, i, j);
i++;
j--;
}
//j 最后角標停留在 i > j 即為 比 v 小的最后一個一元素位置
swap(arr, l, j);
return j;
}
雙路快速排序為最經(jīng)常使用的快速排序?qū)崿F(xiàn)，java 中對基本數(shù)據(jù)類型的排序 Arrays.sort() Collections.sort() 內(nèi)部原理就是通過這種快速排序?qū)崿F(xiàn).
三路快速排序
上述兩種算法我們發(fā)現(xiàn)對于與標志位相同的值得處理總是耽装，做了多余的交換處理愤炸，如果我們能夠?qū)?shù)組分為> = <三部分的話效率可能會有所提高。
如下圖所示：
我們將數(shù)組劃分為
arr[l+1...lt] <v arr[lt+1..i) =v arr[gt...r] > v三部分 其中 lt 指向 < v 的最后一個元素前一個元素掉奄，gt 指向>v的第一個元素的前一個元素规个，i 為當前考察元素定義初始值得時候依舊可以保證這初始的時候這三部分都為空
int lt = l; int gt = r; int i = l + 1;當
e > v的時候我們需要將arr[i] 與 arr[gt-1]交換位置，并將> v的部分擴大一個元素 即gt--但是此時 i 指針并不需要操作姓建，因為換過過來的數(shù)還沒有被考察诞仓。當
e = v的時候 i ++ 繼續(xù)考察下一個當
e < v的時候我們需要將arr[i] 與 arr[lt+1]交換位置當循環(huán)結(jié)束的時候 lt 位于小于 v 的最后一個元素位置所以最后我們需要將arr[l] 與 arr[lt] 交換一下位置。如下圖2所示
三路快速排序 Java 代碼實現(xiàn)：
private static void quickSort3(int[] num, int length) {
quickSort(num, 0, length - 1);
}
private static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 為了提高效率速兔，減少造成快速排序的遞歸樹不均勻的概率墅拭，
// 對于一個數(shù)組，每次隨機選擇的數(shù)為當前 partition 操作中最小最大元素的可能性 降低 1/n!
int randomNum = (int) (Math.random() * (r - l + 1) + l);
swap(arr, l, randomNum);
int v = arr[l];
// 三路快速排序即把數(shù)組劃分為大于 小于 等于 三部分
//arr[l+1...lt] <v arr[lt+1..i) =v arr[gt...r] > v 三部分
// 定義初始值得時候依舊可以保證這初始的時候這三部分都為空
int lt = l;
int gt = r;
int i = l + 1;
while (i < gt) {
if (arr[i] < v) {
swap(arr, i, lt + 1);
i++;
lt++;
} else if (arr[i] == v) {
i++;
} else {
swap(arr, i, gt - 1);
gt--;
//i++ 注意這里 i 不需要加1 因為這次交換后 i 的值仍不等于 v 可能小于 v 也可能等于 v 所以交換完成后 i 的角標不變
}
}
//循環(huán)結(jié)束的后 lt 所處的位置為 <v 的最后一個元素 i 肯定與 gt 重合
//但是 最終v 要放的位置并不是 i 所指的位置 因為此時 i 為大于 v 的第一個元素 v
//而 v 應該處的位置為 lt 位置 并不是 i-1 所處的位置（arr[i-1] = arr[l]）
swap(arr, l, lt);
}
我們可以看到三路快速排序沒有了遞歸的過程通過一次循環(huán)既可以完成排序涣狗。
快速排序時間復雜度空間復雜度
由于我們最常使用的是雙路快排因此我們以此來分析：我們?yōu)榱朔奖惴治鑫覀兗俣ㄔ夭皇请S機選取的而是取得數(shù)組第一個元素谍婉，在選取的標準元素和 partition 得到位置交換的時候，很有可能把前面的元素的穩(wěn)定性打亂镀钓，
比如序列為 5 3 3 4 3 8 9 10 11
現(xiàn)在基準元素5和3(第5個元素穗熬，下標從1開始計)交換就會把元素3的穩(wěn)定性打亂。所以快速排序是一個不穩(wěn)定的排序算法丁溅，不穩(wěn)定發(fā)生在基準元素和a[partition]交換的時刻唤蔗。
對于快速排序的時間度取決于其遞歸的深度，如果遞歸深度又決定于每次關(guān)鍵值得取值所以在最好的情況下每次都取到數(shù)組中間值唧瘾，那么此時算法時間復雜度最優(yōu)為 O(nlogn)措译。當然最壞情況就是之前我們分析的有序數(shù)組，那么每次都需要進行 n 次比較則 時間復雜度為 O(n2)饰序，但是在平均情況 時間復雜度為 O(nlogn),同樣若想看詳細的推到這里推薦一個鏈接 快速排序最好领虹，最壞，平均復雜度分析
快速排序的空間復雜度主要取決于表示為選擇的時候的臨時空間求豫，所以跟時間復雜度掛鉤塌衰，所以平均的空間復雜度也是 O(nlogn)。
總結(jié)
本文總結(jié)了常見的排序算法的實現(xiàn)蝠嘉，通過研究這些算法的思想最疆，也有助于算法題的解題思路。對于這幾種算法都是需要我們熟練掌握的蚤告，但是 Android 工作平時不會接觸太多的數(shù)據(jù)處理努酸，因此我們需要刻意的去經(jīng)常復習，本文的圖片大部分來自于網(wǎng)上杜恰，如果有問題的話可以私信我刪掉获诈。如果文章所說的內(nèi)容有技術(shù)問題也歡迎聯(lián)系我仍源。
參考鏈接：
幾種常見排序算法
常用排序算法穩(wěn)定性、時間復雜度分析（轉(zhuǎn)舔涎，有改動）
慕課網(wǎng)波波老師的數(shù)據(jù)結(jié)構(gòu)課程
