前面在聊資料結構的時候，談過 Array 的基本操作，包含讀取、搜尋、插入、刪除，除此之外，還有「排序」這一個常見的操作我們時常在使用。但是你知道你所用的程式語言中，Array 內建的排序算法用的是哪一種嗎？

我們今天就來聊聊「排序」這個話題。

什麼是排序？

所謂排序，就是將一組資料按照某種條件依序排放，例如按照大小排：1,2,3,5,8,…、按照字母順序排：A,B,D,F…，又或者按照字串長度排：Ad,Bag,Code,Debug,… 等等。

絕大部分的排序算法，都是通過兩筆、兩筆資料的比較，依照條件決定誰放前放後。舉基本的數字為例：2,3,1 三個數字由小到大比較，如果 2 和 3 比，2 會放前面、2 和 1 比，1 又會放在更前面。

排序的原理其實很簡單，就是不斷讓 Array 中的元素互相比較，直到所有資料皆符合給定的條件。然而，重點在於怎麼比最有效率，能夠讓「比較次數最少化」便是更好的排序算法。

Bubble Sort

先看一個常見的簡單排序：Bubble Sort

如果我們要排序 2,3,1 這三個數字，根據 Bubble Sort 的演算法，我們可以讓最大的數字向泡泡一樣冒出來，其作法就是兩個兩個數字比較，數字大的就被交換到右邊，一路交換到所有數字都走訪過，最大的數字就會在最右邊。

然後重複同樣的動作，但是範圍小一些些，從第一個數字至倒數第二個數字，因為最大的數字已經確定在最右邊了。

*Bubble Sort 範例

所以以上圖的例子來說，比完兩輪後 2,3,1 最大的數字已經被移到最右邊了，剩下第三輪只要比較前兩個數字就結束了。

此時我們做了 3 次比較。

Quick Sort

看看另一種排序算法：Quick Sort

*Quick Sort 範例

先隨意挑一個數字當作錨點，也稱作 Pivot，然後讓此 Pivot 與其他數字做比較，比 Pivot 小的放左邊，反之比 Pivot 大的則放右邊。

以 2,3,1 為例，我們挑 2 為 Pivot，只要讓 2 與 1 比較，再讓 2 與 3 比較，就能完成排序。

我們在此範例做了 2 次比較。

排序算法的優劣

那麼，既然 Quick Sort 只比較了 2 次，而 Bubble Sort 卻用了 3 次，我們能說 Quick Sort 就比 Bubble Sort 來的好嗎？

首先我們得分析複雜度，但這是一個又可以寫個一篇分析的內容，我們直接看結論：Bubble Sort 的時間複雜度 O(n^2)，而 Quick Sort 平均來說是 O(nlog(n))。

就一個演算法的效率來講，Quick Sort 遠好於 Bubble Sort。我們在談到時間複雜度的時候有看過這張不同 Big-O 的趨勢圖，O(nlog(n)) 的成長趨勢和 O(n^2) 可像是一個分水嶺被隔開一樣。

*時間複雜度趨勢圖

但，除此之外還有一些因素我們可以納入考量。

例如實作容不容易？Bubble Sort 就是個淺顯易懂的演算法，適合教學及理解排序的基本原理，但是 Quick Sort 卻要花點功夫才能真的理解。

另外一個比較重要的因素是佔用的空間複雜度，Bubble Sort 是 In-Place Sorting 的演算法，僅用交換而不需要用到太多額外的空間；但是 Quick Sort 在最壞的情況下需要和原資料大小一樣的額外空間來暫存中間結果。

綜合以上因素考量，我們最終挑選排序算法時應該根據需求和效率來評估。

雖然說了這麼多，但其實大部分的程式語言其實都幫我們寫好預設的排序算法了，例如 JavaScript 的 Array 只要呼叫一個 .sort() 的 Function 其實就結束了，我們根本不需要自己去實作一個排序算法。

不過，知道自己用的 Build-in Function 到底用的是哪種排序，時間複雜度又是多少，還是蠻有價值的一件事，避免我們再寫出 Performance 不好的程式。

常見排序算法有哪些，都用在哪兒？

目前通用的排序算法時間複雜度都是 O(nlog(n))，就理論而言已經沒有提升的空間了。但是在實務上卻只要有多個幾 % 的平均效率提升，就已經非常有用了。

因此 Quick Sort 算是平均下來效率較好的的排序算法，被目前的 JavaScript Interpreter 所使用，例如 Chrome 的 V8 引擎。

而有另一種要做 Tim Sort 的排序算法則是整合了另外兩種知名的排序 Merge Sort 和 Insertion Sort 混合使用，被目前 Python 的 list 所使用。

講了不同的演算法，其實就中小型專案來講，這一點點的 Performance 差異並不會對我們的產品有什麼特別的影響，畢竟不像是 O(n^2) 和 O(nlog(n)) 這樣有數量級的差別。

因此，我們只要知道我們常用的這些內建排序算法時間複雜度為 O(nlog(n))，並且把 Code 寫得乾淨、簡單，其實就相當足夠了。