排序演算法簡介

排序是計算機演算法中一種最基本、最重要的問題。一組有序的數據為後續各種操作（例如二分查找、求最值等）帶來了極大的方便。我們將分幾節介紹基於比較的排序（O(n^2)、O(nlog(n))）、線性時間排序、外部排序和一些腦洞大開的有意思的排序演算法。

基於比較的O(n^2)排序

1.插入排序

每次將一個新的數放到已經排好序的數組中，初始只有一個數，顯然是排好序的，以後每次添加一個新的數，都選好正確的位置讓它插入，使得插入后的數組還是有序的，這就像打撲克時摸牌整理一樣，美其名曰「摸牌排序」。

插入排序示意圖

下面是一段用 vector 實現的插入排序。事實上插入排序更適合用 list 來實現，因為涉及到在線性表中間插入元素。

insert_sort

插入排序對已排序或近似排序的序列會有較好性能，因為此時內循環近似於 O(1)，所以整體時間趨於O(n)。而對恰好反序排列的序列要耗時 O(n^2)，平均情況耗時O(n^2)。由於只有常數個額外空間使用，所以空間為O(1)，此內循環的終止條件（<而不是<=）決定了此排序演算法是穩定的（排序演算法的穩定性是說原來相等的元素，在排序好的結果中的相對位置是否發生改版，詳見下圖）。

排序穩定性說明

2.選擇排序

每次選擇剩餘元素中最小的，和已排序的數組的後面一個元素交換。初始剩餘元素為全部，已排序個數為0，即應該把第一次選出來的元素和位置為0的元素交換。例子如下圖所示：

選擇排序示意圖

選擇排序使用 vector 或 list 進行都可以，這裡使用 vector 來實現。

select_sort

兩層循環耗時O(n^2)，沒有額外為數據分配空間，所以空間消耗為O(1)，由於涉及到swap，所以排序是不穩定的，考慮（1，2，2，1），不過如果額外分配 O(n) 空間，可以使其變穩定。

3.冒泡排序

這種排序大部分情況下只用在教學，是個 toyalgorithm。每次從首位開始逐一向後比較當前數和后一個數的大小關係，如果後者大於前者則進行次序交換，這樣當第一輪遍歷到最後時最大的數就「浮」到最上面了。進行n-1 次這樣的遍歷，則每次遍歷都會「浮出」剩餘序列中最大的數組，所有 n-1次遍歷完成後，就得到最終排好序的數列。例子如下圖所示：

冒泡排序示意圖

冒泡排序可以使用數組也可以使用鏈表，一種基於 vector 的冒泡演算法如下：

bubble_sort

時間消耗 O(n^2)，空間消耗 O(1)，是穩定的。

總結

本文介紹了三種時間複雜度為 O(n^2) 的排序演算法。還有一些排序演算法比如希爾排序、梳排序、輪轉排序、煎餅排序也是O(n^2) 的，有興趣可以自行了解。雖然時間複雜度並不是最優，但並不是說 O(n^2)排序演算法就一無是處，因為在有些情況下內存寫操作很昂貴，這時採用選擇排序就是一種很優良的方案（其實輪轉排序更優良），因為其需要的內存寫次數最少。這再次驗證了「什麼樣的場景條件決定使用什麼樣的演算法」這一真理！