排序通常是我們學(xué)習(xí)到的第一個算法，排序算法的應(yīng)用十分廣泛。下面我們就來學(xué)習(xí)關(guān)于排序算法的種種知識。
首先，先給出一個思考題，插入排序和冒泡排序是非常常見的排序方式，它們的時間復(fù)雜度都是O(n2)，但是在實際的軟件開發(fā)中，我們常常傾向于使用插入排序而不是冒泡排序，這是為什么呢？學(xué)習(xí)完本節(jié)內(nèi)容，你會得到答案。
如何分析一個排序算法？
對于排序算法，我們一般會從這幾個方面衡量：
排序算法的執(zhí)行效率（不僅僅包括時間復(fù)雜度）：
1.最好情況、最壞情況、平均情況 的時間復(fù)雜度
分析一個排序算法，你要給出最好情況、最壞情況、平均情況下的時間復(fù)雜度，并且你還要說明怎樣的數(shù)據(jù)會造成“最好”和“最壞”的情況。
為什么要區(qū)分這三種復(fù)雜度呢？第一，有些排序算法在三中情況下的性能表現(xiàn)差異很大，所以我們最好都坐一下區(qū)分。第二，要排序的數(shù)據(jù)中，有序程度是不同的，這種程度對排序的執(zhí)行會有影響，我們需要直到排序算法在不同數(shù)據(jù)下的性能表現(xiàn)。
2.關(guān)注時間復(fù)雜度的系數(shù)、常數(shù)、低階
有些排序算法具有相同的時間復(fù)雜度，在這種情況下我們?nèi)绾慰剂克鼈冎g的性能差異呢？這時我們就需要把系數(shù)、常數(shù)、低階 都考慮進(jìn)來。
3.比較次數(shù)和交換（或移動）次數(shù)
基于比較的排序算法在執(zhí)行過程中，會涉及 比較 和 元素移動兩種操作，這也是我們需要考量的。
排序算法的內(nèi)存消耗（空間復(fù)雜度）：
對于空間復(fù)雜度為O(1)的排序算法，我們稱之為原地排序。
排序算法的穩(wěn)定性：
穩(wěn)定性：待排序的序列中存在值相等的元素，經(jīng)過排序之后，他們的先后順序不發(fā)生改變。
你可能會疑惑穩(wěn)定性對排序有什么意義呢？其實，單純的數(shù)字排序確實不需要穩(wěn)定性，但是在實際編程中，你可能對其它屬性也有所要求。
比如說，我們現(xiàn)在要為電商交易系統(tǒng)中的“訂單”進(jìn)行排序。訂單有兩個屬性：下單時間 和 訂單金額。假設(shè)我們有龐大的訂單數(shù)據(jù)，我們希望按照金額從小到大排序。對金額相同的訂單，希望按照下單時間從早到晚有序，對于這樣的一個需求，我們怎么辦呢？
第一種想法是：先對金額進(jìn)行排序，然后找到金額相同的訂單再按照下單時間排序，這個想法沒有問題，但是實際操作起來比較繁瑣。
第二種想法：我們可以借助排序的穩(wěn)定性，通過兩次排序完成：首先，按照下單時間為訂單排序，然后再使用穩(wěn)定的排序算法，按照訂單金額重新排序。經(jīng)過這兩次排序之后，就達(dá)到了要求。
我們用一個圖幫助你理解：
幾種復(fù)雜度為O(n2)的排序算法
冒泡排序
你可以這樣理解冒泡：在一組數(shù)據(jù)中，依次兩兩比較，將大的數(shù)據(jù)放到上方（數(shù)據(jù)的后方），當(dāng)一趟比較完成，最大的數(shù)就會在最上方（冒泡）。假設(shè)這組數(shù)據(jù)中共有n個數(shù)據(jù)，則進(jìn)行n次冒泡就可以得到有序的數(shù)據(jù)。
你可以用這個圖理解：
上面是一趟冒泡，當(dāng)進(jìn)行n次冒泡后：
排序完成。
上面的這種冒泡有優(yōu)化的空間：如果在某一趟冒泡中沒有發(fā)生數(shù)據(jù)交換，那么這個數(shù)據(jù)已經(jīng)有序，我們可以通過一個標(biāo)記實現(xiàn)：
下面是專欄作者給出的冒泡排序代碼：
// 冒泡排序，a表示數(shù)組，n表示數(shù)組大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循環(huán)的標(biāo)志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有數(shù)據(jù)交換
}
}
if (!flag) break; // 沒有數(shù)據(jù)交換，提前退出
}
}
對照思路，我用python也寫了冒泡：
def mp_sort(l):
for i in range(len(l)):
flag = False
for j in range(len(l) - i - 1):
if l[j] > l[j + 1]:
l[j], l[j + 1] = l[j + 1], l[j]
flag = True
if not flag:
break
讓我們分析一下冒泡排序：
- 空間復(fù)雜度：冒泡排序只使用了常量級的空間，空間復(fù)雜度為O(n)，是原地排序算法。
- 穩(wěn)定性：當(dāng)兩個元素相等的時候，我們可以不對元素進(jìn)行交換，所以，是穩(wěn)定的排序算法。
- 時間復(fù)雜度：
最好情況：數(shù)組已經(jīng)有序，只需要進(jìn)行一趟檢測，復(fù)雜度為O(1)
最壞情況：數(shù)組完全倒序，復(fù)雜度為O(n2)
平均情況：如果要完全依照概率分析，分析十分復(fù)雜，所以這里使用一種簡單的分析思路：
有序度：數(shù)組中具有有序元素對的個數(shù)，其中有序元素對：
有序元素對：a[i] <= a[j], 如果i < j
下圖：
滿有序度：如果一個數(shù)組有 n 個數(shù)，且數(shù)組完全有序，其有序度為 n*(n-1)/2 ，這種完全有序的數(shù)組的有序度叫做滿有序度。（只需要記住那個公式即可）
逆序度：和有序度的定義相反，我們也可以通過計算得到： 逆序度 = 滿有序度 - 有序度
我們假設(shè)要排序的數(shù)組的初始狀態(tài)是 4，5，6，3，2，1 ，其中，有序元素對有 (4，5) (4，6)(5，6)，所以有序度是 3。n=6，所以排序完成之后終態(tài)的滿有序度為 n*(n-1)/2=15。
你會發(fā)現(xiàn)，在冒泡排序中，每交換一次，有序度就 +1 ，也就是說，不管算法怎么改進(jìn)，交換次數(shù)都是確定的，交換次數(shù)就 等于 逆序度。在最好情況下，逆序度為 0 ，在最壞情況下，逆序度為 n*(n-1)/2=15，我們?nèi)∫粋€中間值 n*(n-1)/2=15，來假設(shè)有序度既不是很高也不是很低的情況。
換句話說，平均情況下，需要 n*(n-1)/2=15 次交換操作，比較操作比交換操作多，而復(fù)雜度的上限是O(n2)，所以平均情況下的時間復(fù)雜度為O(n2)。
上面的過程并不嚴(yán)格，但還是很實用，在快排中我們還會用到這種方法來分析平均時間復(fù)雜度。
插入排序
插入思想：如果你要向一個有序數(shù)組中插入一個數(shù)據(jù)，你要怎么辦？
話不多說，直接給代碼：
// 插入排序，a表示數(shù)組，n表示數(shù)組大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 數(shù)據(jù)移動
} else {
break;
}
}
a[j+1] = value; // 插入數(shù)據(jù)
}
}
def insert_sort(l):
for i in range(len(l)):
temp = l[i]
j = i - 1
while j >= 0:
if l[j] > temp:
l[j+1] = l[j]
else:
break
j-=1
l[j+1] = temp
插入排序的性能分析：
- 是否為原地排序算法：是
- 是否為穩(wěn)定排序算法：是
- 時間復(fù)雜度：
最好情況：O(n)
最壞情況：O(n2)
平均時間復(fù)雜度：
我們依舊借助有序度做近似分析：你會發(fā)現(xiàn)，算法移動數(shù)據(jù)的次數(shù) 等于 逆序度：
插入排序的有序度.jpg
分析過程類似，最后得到平均時間復(fù)雜度為O(n2)。
思考解答
前面我們提到，即使冒泡和插入兩種排序算法的時間復(fù)雜度一樣，但是人們更加喜歡使用插入排序。
下面就直接引用專欄作者的話：
我們前面分析冒泡排序和插入排序的時候講到，冒泡排序不管怎么優(yōu)化，元素交換的次數(shù)是一個固定值，是原始數(shù)據(jù)的逆序度。插入排序是同樣的，不管怎么優(yōu)化，元素移動的次數(shù)也等于原始數(shù)據(jù)的逆序度。
但是，從代碼實現(xiàn)上來看，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復(fù)雜，冒泡排序需要 3 個賦值操作，而插入排序只需要 1 個。我們來看這段操作：
冒泡排序中數(shù)據(jù)的交換操作：
if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中數(shù)據(jù)的移動操作：
if (a[j] > value) {
a[j+1] = a[j]; // 數(shù)據(jù)移動
} else {
break;
}
我們把執(zhí)行一個賦值語句的時間粗略地計為單位時間（unit_time），然后分別用冒泡排序和插入排序?qū)ν粋€逆序度是 K 的數(shù)組進(jìn)行排序。用冒泡排序，需要 K 次交換操作，每次需要 3 個賦值語句，所以交換操作總耗時就是 3K 單位時間。而插入排序中數(shù)據(jù)移動操作只需要 K 個單位時間。
這個只是我們非常理論的分析，為了實驗，針對上面的冒泡排序和插入排序的 Java 代碼，我寫了一個性能對比測試程序，隨機(jī)生成 10000 個數(shù)組，每個數(shù)組中包含 200 個數(shù)據(jù)，然后在我的機(jī)器上分別用冒泡和插入排序算法來排序，冒泡排序算法大約 700ms 才能執(zhí)行完成，而插入排序只需要 100ms 左右就能搞定！
所以，雖然冒泡排序和插入排序在時間復(fù)雜度上是一樣的，都是 O(n2)，但是如果我們希望把性能優(yōu)化做到極致，那肯定首選插入排序。
以上就是這部分的內(nèi)容，希望你有所收獲。
注：本文章的主要內(nèi)容來自我對極客時間app的《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄的總結(jié)，我大量引用了其中的代碼和截圖，如果想要了解具體內(nèi)容，可以前往極客時間
