DIV CSS 佈局教程網

從 sort() 到冒泡排序:手寫一遍 JS 的排序邏輯
編輯:關於JavaScript     

一、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)。這樣的優化在資料接近有序時效果明顯。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved