DIV CSS 佈局教程網

JavaScript 排序與陣列去重:從 sort 到分治算法的實作解析
編輯:關於JavaScript     

排序與去重是陣列操作的基本功。這兩件事都有「一行搞定」的寫法,也都有「手刻算法」的版本。本文兩邊都寫,並解釋為什麼在什麼情況下該選哪一個。

一、排序

簡潔版:直接用 sort()

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; });   // 降冪

算法版:手刻合併排序(Merge Sort)

如果不用內建方法,自己實作分治法排序:

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);

演算法在解什麼

流程是「不斷二分,分到不能再分,再回頭合併」:

  1. 遞迴終止條件:只剩 1 個元素(start == end)直接回傳;只剩 2 個(start == end - 1)比一次大小就排好,不必再遞迴。這個「兩個元素特例化」的優化能少一層函式呼叫。
  2. 分割:取中間點 Math.floor((start + end) / 2),左右各自遞迴排序。
  3. 合併:兩個已排序的陣列,各看第一個元素誰小就取誰(用 shift() 取出並移除),放進結果陣列。某一邊空了,就把另一邊剩下的用 concat() 整段接上。

為什麼不直接用第一種就好? 這個問題問得很好。答案是:在幾個、幾十個、幾百個資料時,兩者跑起來的時間差幾乎看不出來。但當資料量到了幾萬、幾十萬,演算法的差距就會非常明顯。更重要的是,演算法的核心思想是「分而治之」——把大問題切成小問題解決,這個思路的價值遠大於排序本身,它能被套用到大量其他問題上。

實務補充:現代 JavaScript 引擎的 Array.prototype.sort 本身已經是高度最佳化的實作(V8 現已使用 TimSort),效能與穩定性都優於手刻版本。手刻的價值在於理解,不在於取代。

二、陣列去重

簡潔版:迴圈 + indexOf 判斷

思路是:宣告一個空陣列,把原陣列逐一 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)] 就好;手刻分治法(合併排序、分治去重)的價值在於理解「分而治之」這個通用問題拆解策略——它不只用在排序,也用在大量演算法與系統設計的場景中。知道內建方法怎麼運作,才能在遇到內建方法無法處理的客製需求時,寫出自己的版本。

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