刷 LeetCode 過程中實在太常用到 sort ，而且往往不是單純排數字那樣簡單，所以決定來深入研究一下到底怎麼靈活運用這個 js 原生的 Array method (畢竟你不會想要一碰到排序問題就要再寫一次快速排序或合併排序吧)

Array.prototype.sort 是用哪種排序演算法？

之前花了很多時間介紹排序演算法，那 Array.prototype.sort 這個方法到底是用哪一種演算法呢？
答案是根據 Browser，以 Chrome V8 引擎的 source code 為例，過去當陣列長度小於 10 時，為了提升效能會改用「Insertion Sort」，而其他時候使用 Quick Sort。若忘了這兩個排序是甚麼，可以點這裡 Insertion Sort、Quick Sort。但現在已經變成更新成使用 Timsort(结合了合并排序和插入排序的排序法)，而且做到 stable! (感謝邦友 Huli 糾正，寫鐵人賽真好還可以 update 資訊)

Array.prototype.sort was among the last builtins implemented in self-hosted JavaScript in V8. Porting it offered us the opportunity to experiment with different algorithms and implementation strategies and finally make it stable in V8 v7.0 / Chrome 70.

詳細部分可以點這裡

甚麼是 stable / unstable ?

大至上就是說

[
	{ name: "Milly",   rating: 14 },
	{ name: "Patches", rating: 14 },
	{ name: "Devlin",  rating: 13 },
	{ name: "Eagle",   rating: 13 },
	{ name: "Jenny",   rating: 13 },
	{ name: "Kona",    rating: 13 },
	{ name: "Leila",   rating: 13 },
	{ name: "Oliver",  rating: 13 },
	{ name: "Choco",   rating: 12 },
	{ name: "Molly",   rating: 12 },
	{ name: "Nova",    rating: 12 }
]

當針對 rating 這個 key 做排序

stable

他會不但會針對 rating 排序好還會照順序，例如 Choco 是 rating : 12 中的第一個接下來是 Molly、Nova

[
    { name: "Choco",   rating: 12 },
    { name: "Molly",   rating: 12 },
    { name: "Nova",    rating: 12 },
    { name: "Devlin",  rating: 13 },
    { name: "Eagle",   rating: 13 },
    { name: "Jenny",   rating: 13 },
    { name: "Kona",    rating: 13 },
    { name: "Leila",   rating: 13 },
    { name: "Oliver",  rating: 13 },
    { name: "Milly",   rating: 14 },
    { name: "Patches", rating: 14 },
]

unstable

他只會針對 rating 排好，不管 name 的順序

[
    { name: "Molly",   rating: 12 },
    { name: "Choco",   rating: 12 },
    { name: "Nova",    rating: 12 },
    { name: "Eagle",   rating: 13 },
    { name: "Devlin",  rating: 13 },
    { name: "Kona",    rating: 13 },
    { name: "Leila",   rating: 13 },
    { name: "Jenny",   rating: 13 },
    { name: "Oliver",  rating: 13 },
    { name: "Patches", rating: 14 },
    { name: "Milly",   rating: 14 },
]

wiki 有列所有排序法是 stable 還是 unstable
另外想知道更詳細推薦這個影片 [偷米騎巴哥] 20180412 前端踩雷日記(解開Sort不穩定現象之謎)

接下來就直接進入正題囉

Array.prototype.sort([compareFunction])

compareFunction 這個 function 是 optional 的，以下會詳細解釋有無 compareFunction 的情況

沒傳 compareFunction: Unicode 編碼排序

var months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

var array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]

疑 ! 為什麼 "100000" 小於 21 ?，我們要來看一下 mdn 上 sort 的定義

The sort() method sorts the elements of an array in place and returns the sorted array. The default sort order is built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.

沒傳 compareFunction 會將元素轉乘字串再按 Unicode 編碼排序，而字串比較會從第一個字開始比 2 > 1, 所以 21 > 100000。

有傳 compareFunction: 自定義排序

compareFunction 通常會表示成

function compareFunction(a, b){}

• compareFunction (a, b) < 0, a 在前 b 在後 [a, b]
• compareFunction (a, b) == 0, 位置不變
• compareFunction (a, b) > 0, b 在前 a 在後 [b, a]

function compareFunction (a, b) {
    if (a is less than b by some ordering criterion) {
        return -1;
    }    
    if (a is greater than b by the ordering criterion) {
        return 1; 
    }
    // a must be equal to b
    return 0;
}

若只是單純要比較數字可以用下面簡化

function compareFunction (a, b) {
    return a - b;
}

以上只有適用單純只有數字，那假如有英文字母。除了最基本方法

function compareFunction (a, b) {
    if(a > b) return 1;
    if(a < b) return -1;
    return 0
}

其實也可以用 localeCompare

The localeCompare() method returns a number indicating whether a reference string comes before or after or is the same as the given string in sort order.

function compareFunction (a, b) {
    return a.localeCompare(b);
}
"a".localeCompare("b"); // -1
"d".localeCompare("b");  // 1
"a".localeCompare("a"); // 0

var a = 'réservé'; // with accents, lowercase
var b = 'RESERVE'; // no accents, uppercase

console.log(a.localeCompare(b));
// expected output: 1
console.log(a.localeCompare(b, 'en', {sensitivity: 'base'}));
// expected output: 0

變化題

我今天遇到一個題目是

let letterArr = ["let1 art can", "let26 own kit dig","let3 art zero"] 

不想管 identifier(let1、let26、let3)，排序剩下的字。就可以用 localeCompare

letterArr.sort( (a, b) => {
    let strA = a.substr(a.indexOf(' ') + 1);
    let strB = b.substr(b.indexOf(' ') + 1);
    if(strA === strB) return a.localeCompare(b);
    return strA.localeCompare(strB);
})
//  ["let1 art can", "let3 art zero", "let26 own kit dig"]

想看詳細題目可以點我的 gitbook

結論

大部分排序都需要寫 compare function，所以知道 compare function 裡是如何運作就很重要了。

鐵人賽不用每天寫好輕鬆阿
如有錯誤或需要改進的地方，拜託跟我說。
我會以最快速度修改，感謝您

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。