淺談 JS sort() 到背後排序方法

4 min readFeb 10, 2019

Front-End / JavaScript

Unicode 編碼排序

我們知道 sort() 是在 JS 原生就有功能（Array.prototype.sort()），他會對一個陣列的所有元素進行排序並回傳。而這裡的排序方式是根據 Unicode 編碼位置來排序：（範例參考MDN）

//Stringvar months = ['March', 'Jan', 'Feb', 'Dec'];
console.log(months.sort()); // ["Dec", "Feb", "Jan", "March"]//Numbervar array1 = [1, 30, 4, 21, 100000];
console.log(array1.sort()); // [1, 100000, 21, 30, 4]

自定義排序

如果我們想將排序方式制定成數字「由小到大」、「由大到小」，sort 提供我們帶入一個 compareFunction 比較：（範例參考MDN）

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  if (a > b) return 1;
  if (a < b) return -1;
  return 0;
});
console.log(numbers); // [1, 2, 3, 4, 5]

一開始看到這樣的寫法覺得很神奇！也就讓我繼續探討下面兩個問題：

每次傳入的 a, b 各是什麼？
背後的排序法是用哪一種？

接下來開始研究這兩個問題。如果讀者已經可以秒答，那可以左轉打遊戲，不用再看下去了ＸＤ。

sort 內 function 傳入的參數 a, b ?

我們把 a, b 直接 console 出來看… 出來的每個數字真的黑人問號Ｑ

我們還是先跳過這題，看第二題吧（從入門到放棄ＸＤ

sort 背後的排序方法

查了一下 Chrome V8 引擎的 source code 所實作背後的運作原理：

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.
  if (!IS_CALLABLE(comparefn)) {
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
      }
      x = TO_STRING(x);
      y = TO_STRING(y);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
}

註釋寫著他是用「Quick Sort」，而當陣列長度小於 10 時，為了提升效能會改用「Insertion Sort」。

如果不懂 Quick Sort 和 Insertion Sort ，可以參考以下連結，影音並茂的方式說明十分明瞭：

Quick Sort : 點我 | Insertion Sort : 點我

有了上面兩個排序法的概念，我們來看一下剛剛跳過的問題。

第一次傳入 a = 3, b = 1，由於 a > b 故 1 會在 3 的左邊。

第二次傳入 a = 15, b = 3，3 會在 15 的左邊。

… 直到第五次

第五次傳入 a = 275, b = 310，由於 a < b 故 275 會在 310 的左邊。

這裡有趣的是，第六次 console 出來的值是 a = 275, b = 15

而這邊原生的演算法還加入了「二分搜尋法 Binary Search」的實作來優化排序速度，帶進去的 a, b 值才會是我們所看到的這樣。

總結

原先筆者只是看一些前端文章，但看到 sort 內 return 1 和 -1 就能夠排序，實在是無法睜一隻眼閉一隻眼跳過不去理解後面原理啊ＸＤ。不過這樣研究下來也對 Array.prototype.sort 有更深一層認識。

在這次研究還查到了一個對於 sort 所謂「不穩定」現象解釋的影片，覺得講得非常好，連結也附在此。

謝謝你 / 妳的觀看，如果覺得有幫助的話別忘了順手拍個手，感激不盡：Ｄ