排序與去重是陣列操作的基本功。這兩件事都有「一行搞定」的寫法,也都有「手刻算法」的版本。本文兩邊都寫,並解釋為什麼在什麼情況下該選哪一個。
var arr = [];
for(var i = 0; i < 20; i++){
arr.push(Math.floor(Math.random() * 100))
}
arr.sort(function(a, b){
return a > b ? 1 : -1;
})
alert(arr)
陷阱:sort() 預設不是按數字大小排。 不帶參數的 sort() 會把元素轉成字串再依 ASCII 字母順序比較,所以 [10, 9, 100] 排完是 [10, 100, 9]——這是最經典的 JS 面試陷阱之一。
sort() 接受一個比較函式作為參數,該函式有兩個參數,分別代表每次比較的兩個陣列項。每次比較都會呼叫它並傳入這兩項,回傳值為正數就交換順序,為負數或 0 則不交換。所以數字排序的標準寫法是:
arr.sort(function(a, b){ return a - b; }); // 升冪
arr.sort(function(a, b){ return b - a; }); // 降冪
如果不用內建方法,自己實作分治法排序:
var arr = [];
for(var i = 0; i < 20; i++){
arr.push(Math.floor(Math.random() * 100))
}
//生成一個無序的arr數組
function sort(arr, start, end){
//數組長度為1
if(start == end){
return [arr[start]]
} else if(start == end - 1){
//數組長度為2,根據數值大小來排序
if(arr[start] > arr[end]){
return [arr[end], arr[start]]
} else {
return [arr[start], arr[end]]
}
}
// 數組長度一半
var l = Math.floor((start + end) / 2);
//左邊數組
var arrLeft = sort(arr, start, l);
//右邊數組
var arrRight = sort(arr, l + 1, end);
//返回結果
var result = [];
//分割成兩部分 左右兩個數組,只比對數組中的第一個數,
//那個數值小就把它放到結果裡面,並把小的數值刪除掉,故采用數組中的 shift 方法。
//一旦出現左邊數組或右邊數組沒有數據的時候,result 數組就與還有數據的數組合併
//采用 concat,並返回結果
while(arrLeft.length > 0 || arrRight.length > 0){
if(arrLeft.length == 0){
result = result.concat(arrRight);
break;
} else if(arrRight.length == 0){
result = result.concat(arrLeft);
break;
}
if(arrLeft[0] < arrRight[0]){
result.push(arrLeft.shift())
} else {
result.push(arrRight.shift());
}
}
return result;
}
var arrSort = sort(arr, 0, arr.length - 1); //參數:數組,開始位置,結束位置
document.write(arr + '<br/>' + arrSort);
流程是「不斷二分,分到不能再分,再回頭合併」:
start == end)直接回傳;只剩 2 個(start == end - 1)比一次大小就排好,不必再遞迴。這個「兩個元素特例化」的優化能少一層函式呼叫。Math.floor((start + end) / 2),左右各自遞迴排序。shift() 取出並移除),放進結果陣列。某一邊空了,就把另一邊剩下的用 concat() 整段接上。為什麼不直接用第一種就好? 這個問題問得很好。答案是:在幾個、幾十個、幾百個資料時,兩者跑起來的時間差幾乎看不出來。但當資料量到了幾萬、幾十萬,演算法的差距就會非常明顯。更重要的是,演算法的核心思想是「分而治之」——把大問題切成小問題解決,這個思路的價值遠大於排序本身,它能被套用到大量其他問題上。
實務補充:現代 JavaScript 引擎的 Array.prototype.sort 本身已經是高度最佳化的實作(V8 現已使用 TimSort),效能與穩定性都優於手刻版本。手刻的價值在於理解,不在於取代。
思路是:宣告一個空陣列,把原陣列逐一 for 進去,已存在的跳過,不存在的才插入。
var arr = [];
for(var i = 0; i < 20; i++){
arr.push(parseInt(Math.random() * 10));
}
// 手動掛上 indexOf(舊環境沒有原生 indexOf)
Array.prototype.indexOf = function(n){
for(var i = 0; i < this.length; i++){
if(this[i] == n){
return i;
}
}
return -1;
}
function removeDup(arr){
var result = [];
for(var i = 0; i < arr.length; i++){
if(result.indexOf(arr[i]) == -1){
result.push(arr[i]);
}
}
return result;
}
var arr2 = removeDup(arr)
document.write(arr + '<br/>' + arr2)
這個寫法時間複雜度是 O(n²)——每個元素都要在結果陣列裡做一次線性搜尋。資料量小沒問題,大了就會明顯變慢。
var arr = [];
for(var i = 0; i < 20; i++){
arr.push(parseInt(Math.random() * 10));
}
Array.prototype.indexOf = function(n){
for(var i = 0; i < this.length; i++){
if(this[i] == n){
return i;
}
}
return -1;
}
function removeDup(arr, s, e){
if(s == e){
//分割就剩下一個
return [arr[s]]
} else if(s == e - 1){
//為了優化 剩下兩個就不用分割啦
if(arr[s] == arr[e]){
return [arr[s]]
} else {
return [arr[s], arr[e]];
}
}
//數組平分成兩段
var l = Math.floor((s + e) / 2);
//左邊
var arrL = removeDup(arr, s, l);
//右邊
var arrR = removeDup(arr, l + 1, e);
//結果 先把左邊的復制進去
var result = arrL;
//循環 將不重復的數據插入到結果裡面
for(var i = 0; i < arrR.length; i++){
if(result.indexOf(arrR[i]) == -1) result.push(arrR[i])
}
return result; //返回結果
}
var arrDup = removeDup(arr, 0, arr.length - 1);
document.write(arr + '<br/>' + arrDup);
同樣是分治:把陣列切半,直到只剩一個元素(天然無重複)或兩個元素(比一次就知道要不要合併)。然後把左半邊的結果當基底,逐一檢查右半邊的每個元素是否已存在,不存在才補進去。這樣每一層合併都維持了「結果無重複」的性質,遞迴到底自然就得到全去重的答案。
現代 JavaScript 提供了更短、更快、語意更清楚的做法:
// 排序 [3, 1, 2].sort((a, b) => a - b); // 去重:Set 是最直觀的選擇,時間複雜度 O(n) var unique = [...new Set(arr)]; var unique = Array.from(new Set(arr)); // 物件陣列依欄位去重 var byId = [...new Map(list.map(item => [item.id, item])).values()]; // 去重後再排序 var result = [...new Set(arr)].sort((a, b) => a - b);
Set 內部用雜湊表實作,插入與查詢都是 O(1),整體去重降到 O(n),比上面兩種做法都有效率,程式碼還短得多。
總結:日常開發用 sort((a,b) => a-b) 與 [...new Set(arr)] 就好;手刻分治法(合併排序、分治去重)的價值在於理解「分而治之」這個通用問題拆解策略——它不只用在排序,也用在大量演算法與系統設計的場景中。知道內建方法怎麼運作,才能在遇到內建方法無法處理的客製需求時,寫出自己的版本。