一、sort() 的排序原理
sort() 會對陣列做原地排序並回傳該陣列,且排序不一定穩定。不傳參數時,元素會被轉成字串,依 Unicode 碼位順序排列。
語法:arr.sort([compareFunction])
參數 compareFunction(可選)用來指定排序規則:
如果 compareFunction(a, b) 小於 0,a 排在 b 前面;
如果等於 0,a 與 b 的相對位置不變(註:ES 規範並不保證這點,也不是所有瀏覽器都遵守);
如果大於 0,b 排在 a 前面。
// 由小到大排列
var arr = [11, 55, 22, 45, 16, 87];
arr.sort(function (a, b) { return a - b; });
console.log(arr);
順帶一提,不傳 compareFunction 時 [11, 55, 22] 會被排成 [11, 22, 55] 看起來沒錯,但 [9, 10] 會變成 [10, 9]——因為字串比較下 "10" 排在 "9" 前面。這是最常見的誤用之一。
二、手寫模擬排序過程
sortSelf(arr, function (a, b) { return a - b; });
console.log(arr);
function sortSelf(array, fn) {
for (var i = 0; i < array.length - 1; i++) {
var isSorted = true; // 先假設本輪已排好
for (var j = 0; j < array.length - 1 - i; j++) {
if (fn(array[j], array[j + 1]) > 0) {
// 前大於後就交換
var temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
isSorted = false;
}
}
if (isSorted) { break; } // 一輪都沒換過,代表已有序
}
}
這實作的是冒泡排序,並加了一個優化:外層每跑完一輪,若 isSorted 仍是 true,就代表資料本來已排序,直接 break 提早結束。最壞情況時間複雜度仍是 O(n²),最好情況(已排序)降到 O(n)。這樣的優化在資料接近有序時效果明顯。