萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 快速排序算法詳解與優化實現

算法核心思想

快速排序採用分治法:

  1. 從陣列中選取一個基準值。
  2. 將陣列分為兩個子陣列:小於基準值的放左邊,大於等於基準值的放右邊。
  3. 遞迴對左右子陣列重複上述過程,直到子陣列長度 ≤ 1。
  4. 最後將左陣列 + 基準值 + 右陣列拼接,得到有序陣列。

基礎實現(教學版)

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 遞迴終止條件

  // 選取中間元素作為基準(避免已排序陣列最壞情況)
  var midIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(midIndex, 1)[0]; // 取出基準值,原陣列移除該元素

  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 遞迴排序左右子陣列並合併
  return quickSort(left).concat([pivot], quickSort(right));
}

// 測試
console.log(quickSort([32, 45, 37, 16, 2, 87])); // [2, 16, 32, 37, 45, 87]

關鍵點解析

  • arr.splice(midIndex, 1)[0]:同時獲取基準值並從陣列移除,避免後續比較時重複處理。
  • concat:創建新陣列合併結果,不修改原陣列(函數式風格)。
  • 時間複雜度:平均 O(n log n),最壞 O(n²)(如陣列已有序且每次選首/尾元素為基準)。
  • 空間複雜度:O(n log n)(遞迴調用棧 + 新陣列分配)。

優化方向

1. 原地分區,降低空間複雜度至 O(log n)

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;

  var pivotIndex = partition(arr, left, right);
  quickSortInPlace(arr, left, pivotIndex - 1);
  quickSortInPlace(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  var pivot = arr[right]; // 選最右為基準
  var i = left - 1;
  for (var j = left; j < right; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, right);
  return i + 1;
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

2. 三向切分,處理大量重複元素

荷蘭國旗問題思路,將陣列分為 < pivot、= pivot、> pivot 三區,避免重複元素導致的退化。

3. 隨機化基準或三數取中

隨機選取基準或取「首、中、尾」三者中位數,大幅降低最壞情況概率。

ES6 現代寫法(函數式、不可變)

const quickSort = (arr) => 
  arr.length <= 1 
    ? arr 
    : quickSort(arr.filter(x => x < arr[0]))
        .concat(arr.filter(x => x === arr[0]))
        .concat(quickSort(arr.filter(x => x > arr[0])));

// 注意:此寫法易讀但會多次遍歷陣列,效能不如迴圈版本

總結

  • 快速排序是實務中最常用的通用排序算法之一(V8 引擎 Array.sort 內部即採用快排變體)。
  • 理解分區邏輯與遞迴結構是掌握的關鍵。
  • 實際專案中優先使用原生 arr.sort((a,b)=>a-b),僅在教學、面試或特殊定制場景手寫實現。
copyright © 萬盛學電腦網 all rights reserved