前言

前幾天一個朋友在微信里面問我一個關于 JS 數組排序的問題。通過該問題發現了一些之前沒發現的內容，下面話不多少了，來一起看看詳細的介紹吧。

原始數組如下：

var data = [ {value: 4},  {value: 2},  {value: undefined},  {value: undefined},  {value: 1},  {value: undefined},  {value: undefined},  {value: 7},  {value: undefined},  {value: 4}];

data 是個數組，數組的每一項都是一個擁有 value 作為 key 的對象，值為數字或者 undefined。

data .sort((x, y) => x.value - y.value) .map(x => x.value);

對數組的 value 進行排序，然后把排完序的數組進行 flat 處理。得到的結果如下：

[2, 4, undefined, undefined, 1, undefined, undefined, 7, undefined, 4]

顯然這沒有達到我們的目的。

現在我們修改一下排序，挑戰一下函數的調用順序：先對數組進行扁平化(flat)處理，然后再排序。

data .map(x => x.value) .sort((x, y) => x - y)

這時我們得到的結果和之前截然不同：

[1, 2, 4, 4, 7, undefined, undefined, undefined, undefined, undefined]

遇到這種情況第一感覺肯定是要去看看 ECMA 規范，萬一是 JS 引擎的 bug 呢。

在 ES6 規范 22.1.3.24 節寫道：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a < b, a = b, and a > b will be true for a given pair of a and b.

簡單翻譯一下就是：第二個參數 comparefn 返回一個數字，并且不是 NaN。一個注意事項是，對于參與比較的兩個數 a 小于 b、a 等于 b、a 大于 b 這三種情況必須有一個為 true。

所以嚴格意義上來說，這段代碼是有 bug 的，因為比較的結果出現了 NaN。

在 MDN 文檔上還有一個細節：

如果 comparefn(a, b) 等于 0， a 和 b 的相對位置不變。備注：ECMAScript 標準并不保證這一行為，而且也不是所有瀏覽器都會遵守。

翻譯成編程術語就是：sort 排序算法是不穩定排序。

其實我們最疑惑的問題上，上面兩行代碼為什么會輸出不同的結果。我們只能通過查看 V8 源碼去找答案了。

V8 對數組排序是這樣進行的：

如果沒有定義 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;};

然后定義了一個插入排序算法：