Array.sort 淺析

Javascript 是用哪種演算法做排序的？

Published in

De-Magazine

3 min readDec 17, 2017

先來看看一個 js 的神秘之處：

因為預設的 sort 方法會把值轉為 String，並按照 char code 做排序，才會出現上面的結果。不過今天不是要講 Javascript 的 100 道陰影，而是要來探討 Javascript 的 sort 背後的實作方式。

從 V8 的實作當中，我們可以看到幾個事實：

為了簡化 V8 中的代碼，這邊撰寫一個簡單的快速排序代碼：（僅供參考）

快速排序法的實現重點在於如何選擇一個相對好的 pivot，來避免最壞情況的發生。在實際的情況當中，輸入的資料並不一定是隨機的，所以在實務上都會使用 random 的方式來選擇 pivot。

第一個問題是，為什麼 V8 使用快速排序？雖然快速排序的平均時間複雜度可以達到 O(nlogn)，但是最壞情況也有可能達到 O(n²)。

同時，快速排序並不是一個穩定的演算法，也就是兩個同樣值的資料，在排序之後位置可能會不同。

合併排序簡單可以分為兩大步驟，先把 array 分解後再調用 merge 不斷合併。不僅平均、最壞、最好時間複雜度都可以達到 O(nlogn)，演算法本身也是穩定的，為什麼不採用呢？

我們在 quick sort 當中，並不需要對 array 做合併的動作，也就是整個演算法可以不另外耗費空間完成，而 merge sort 需要 O(n) 的空間。因此儘管快速排序有上述的情況發生，但在實務上他仍然是一個相當好的選擇。

我們可以透過 randomize 的方式（關於如何隨機選取 pivot，實際上還能夠寫一大篇文章來解釋），來避免 O(n²) 的情形發生。

不過儘管如此，我們還是沒辦法解決 stable 的問題，雖然在大部分的場景當中可能並不重要（畢竟資料排序通常都是由後端實作），不過如果真的碰到時，這就是非常重要的考量了。

並不是每個瀏覽器的實作都是用 Quicksort

如果仔細看一下 V8 的原始碼，會發現這一段：

插入排序法 — from V8

咦，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？

要理解原因，我們先回想一下插入排序的原理。插入排序跟撲克牌整理牌的方式很像，每次拿起一張牌，找到一個最適當位置放入，每次的要插入的牌組都是已經整理好的，可以達到原址排序。

下面是簡單的實作：

插入排序雖然跟氣泡排序擁有相同的時間複雜度，不過在交換次數上有很大的不同，氣泡排序有 O(n²) 的交換次數，而插入排序最多只需要 O(n)。

回到最剛開始的問題，為什麼在陣列數量小於等於 10 的時候要用插入排序法？

對於小數量的陣列而言，如果已經排序好，或是相當接近有序的陣列，插入排序法是唯一可以達到時間複雜度 O(n) 的演算法。這是相當有效率的一件事。

因為在工作上需要排序，因此開始深入理解了原生的 sort 在背後做了哪些事情。除了要注意 js 會預設轉為字串比較之外，在處理資料量大的陣列時，理解背後的實作方式就顯得相當重要。

同時我們也了解到，不同的排序演算法都有其適合的場景，在使用 sort 的時候要記得：