Closed kjj6198 closed 6 years ago
這篇文章不是談論在 Javascript 原生的 sort 要注意的事項。例如：
[1, 2, 3, 8, 20, 30, 11].sort() // [1, 11, 2, 20, 3, 30, 8]
因為預設的 sort 方法會把值轉為 String，並按照 char code 做排序，所以才會出現上面的結果。
今天要來探討 Javascript 的 sort 背後的實作方式。
從 V8 的實作當中，我們可以看到幾個事實：
為了簡化 V8 中的代碼，這邊撰寫一個簡單的快速排序代碼：（僅供參考）
function quickSort(arr, p, r) { if (p < r) { var q = partition(arr, p, r) quickSort(arr, q - 1, p) quickSort(arr, q + 1, r) } } function partition(arr, p, r) { var x = arr[r]; var i = p - 1; for (var j = p; j < r - 1; j++) { if (arr[j] <= x) { i += 1; var tmp = a[j]; arr[j] = a[i]; arr[i] = tmp; } } var tmp = arr[r]; arr[r] = a[i + 1] arr[i + 1] = tmp; }
快速排序法的實現重點在於如何選擇一個相對好的 pivot，來避免最壞情況的發生。在實際的情況當中，輸入的資料並不一定是隨機的，所以在實務上都會使用 random 的方式來選擇 pivot。
第一個問題是，為什麼 V8 使用快速排序？雖然快速排序的平均時間複雜度可以達到 $O(nlogn)$，但是最壞情況也有可能達到$O(n^2)$。同時，快速排序並不是一個穩定的演算法，也就是兩個同樣值的資料，在排序之後位置可能會不同。
合併排序簡單可以分為兩大步驟，先把 array 分解後再調用 merge 不斷合併。不僅平均、最壞、最好時間複雜度都可以達到$O(nlogn)$，演算法本身也是穩定的，為什麼不採用呢？
我們在 quick sort 當中，並不需要對 array 做合併的動作，也就是整個演算法可以不另外耗費空間完成，而 merge sort 需要 $O(n)$ 的空間。因此儘管快速排序有上述的情況發生，但在實務上他仍然是一個相當好的選擇。
我們可以透過 randomize 的方式（關於如何隨機選取 pivot，實際上還能夠寫一大篇文章來解釋），來避免 $O(n^2)$ 的情形發生。
不過儘管如此，我們還是沒辦法解決 stable 的問題，雖然在大部分的場景當中可能並不重要（畢竟資料排序通常都是由後端實作），不過如果真的碰到時，這就是非常重要的考量了。
並不是每個瀏覽器的實作都是用 Quicksort
如果仔細看一下 V8 的原始碼，會發現這一段：
while (true) { // Insertion sort is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; }
咦，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？
要理解原因，我們先回想一下插入排序的原理。插入排序跟撲克牌整理牌的方式很像，每次拿起一張牌，找到一個最適當位置放入，每次的要插入的牌組都是已經整理好的，可以達到原址排序。
function insertionSort(arr) { for (var j = 1; j < arr.length; j++) { var key = arr[j]; var i = j - 1; while(i >= 0 && arr[i] > key) { arr[i + 1] = arr[i] i = i - 1; } arr[i + 1] = key; } return arr; }
插入排序雖然跟氣泡排序擁有相同的時間複雜度，不過在交換次數上有很大的不同，氣泡排序有$O(n^2)$的交換次數，而插入排序最多只需要$O(n)$。
回到最剛開始的問題，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？
對於小數量的陣列而言，如果已經排序好，或是相當接近有序的陣列，插入排序法是唯一可以達到時間複雜度$O(n)$的演算法。這是相當有效率的一件事。
因為在工作上需要排序，因此開始深入理解了原生的 sort 在背後做了哪些事情。除了要注意 js 會預設轉為字串比較之外，在處理資料量大的陣列時，理解背後的實作方式就顯得相當重要。
同時我們也了解到，不同的排序演算法都有其適合的場景，在使用 sort 的時候要記得：
Array.sort 淺析
這篇文章不是談論在 Javascript 原生的 sort 要注意的事項。例如：
因為預設的 sort 方法會把值轉為 String，並按照 char code 做排序，所以才會出現上面的結果。
今天要來探討 Javascript 的 sort 背後的實作方式。
從 V8 的實作當中，我們可以看到幾個事實：
為了簡化 V8 中的代碼，這邊撰寫一個簡單的快速排序代碼：（僅供參考）
深入探討：為什麼是快速排序？
快速排序法的實現重點在於如何選擇一個相對好的 pivot，來避免最壞情況的發生。在實際的情況當中，輸入的資料並不一定是隨機的，所以在實務上都會使用 random 的方式來選擇 pivot。
第一個問題是，為什麼 V8 使用快速排序？雖然快速排序的平均時間複雜度可以達到 $O(nlogn)$，但是最壞情況也有可能達到$O(n^2)$。同時，快速排序並不是一個穩定的演算法，也就是兩個同樣值的資料，在排序之後位置可能會不同。
為什麼不用合併排序？
合併排序簡單可以分為兩大步驟，先把 array 分解後再調用 merge 不斷合併。不僅平均、最壞、最好時間複雜度都可以達到$O(nlogn)$，演算法本身也是穩定的，為什麼不採用呢？
In-place
我們在 quick sort 當中，並不需要對 array 做合併的動作，也就是整個演算法可以不另外耗費空間完成，而 merge sort 需要 $O(n)$ 的空間。因此儘管快速排序有上述的情況發生，但在實務上他仍然是一個相當好的選擇。
我們可以透過 randomize 的方式（關於如何隨機選取 pivot，實際上還能夠寫一大篇文章來解釋），來避免 $O(n^2)$ 的情形發生。
Stable
不過儘管如此，我們還是沒辦法解決 stable 的問題，雖然在大部分的場景當中可能並不重要（畢竟資料排序通常都是由後端實作），不過如果真的碰到時，這就是非常重要的考量了。
並不是每個瀏覽器的實作都是用 Quicksort
插入排序
如果仔細看一下 V8 的原始碼，會發現這一段：
咦，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？
要理解原因，我們先回想一下插入排序的原理。插入排序跟撲克牌整理牌的方式很像，每次拿起一張牌，找到一個最適當位置放入，每次的要插入的牌組都是已經整理好的，可以達到原址排序。
插入排序雖然跟氣泡排序擁有相同的時間複雜度，不過在交換次數上有很大的不同，氣泡排序有$O(n^2)$的交換次數，而插入排序最多只需要$O(n)$。
回到最剛開始的問題，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？
對於小數量的陣列而言，如果已經排序好，或是相當接近有序的陣列，插入排序法是唯一可以達到時間複雜度$O(n)$的演算法。這是相當有效率的一件事。
結論
因為在工作上需要排序，因此開始深入理解了原生的 sort 在背後做了哪些事情。除了要注意 js 會預設轉為字串比較之外，在處理資料量大的陣列時，理解背後的實作方式就顯得相當重要。
同時我們也了解到，不同的排序演算法都有其適合的場景，在使用 sort 的時候要記得：