DIV CSS 佈局教程網

JavaScript 快速排序(Quick Sort)原理與實作全解
編輯:JavaScript基礎知識     

快速排序是對氣泡排序的一種改良。它的核心思想是「分治」:挑出一個基準值,透過一趟掃描把整個序列切成左右兩段,左段全部不大於基準、右段全部不小於基準,接著對這兩段分別重複同樣的動作,直到每段子序列只剩一個元素,整個序列自然就有序了。

一趟分割(partition)到底做了什麼

以下假設待排序陣列為 A[0] … A[N-1]:

  1. 設定兩個指標 low 與 high,起始時 low = 0、high = N - 1。
  2. 取第一個元素作為基準值,記為 base = A[low]。
  3. 從右往左找,找到第一個小於 base 的元素,把它換到左側空位。
  4. 再從左往右找,找到第一個大於 base 的元素,把它換到右側空位。
  5. 重複 3、4 兩步,直到 low === high,此時基準值就落在它最終的正確位置上。

要特別注意的是:快速排序不是穩定排序。值相同的元素在過程中被長距離搬移,結束後相對順序很可能改變。

程式碼實作

function partition(elements, low, high) {
  var base = elements[low];          // 以區間首元素為基準
  while (low < high) {
    // 從後往前,跳過所有大於等於基準的元素
    while (low < high && elements[high] >= base) high--;
    elements[low] = elements[high];  // 把較小的值填進左邊空位

    // 從前往後,跳過所有小於等於基準的元素
    while (low < high && elements[low] <= base) low++;
    elements[high] = elements[low];  // 把較大的值填進右邊空位
  }
  elements[low] = base;              // 基準值歸位
  return low;                        // 回傳分割點
}

function sort(elements, low, high) {
  if (low >= high) return;
  var pos = partition(elements, low, high);
  sort(elements, low, pos - 1);      // 遞迴排序左段
  sort(elements, pos + 1, high);     // 遞迴排序右段
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements, 0, elements.length - 1);
console.log('after : ' + elements);

這裡順手修掉了一個常見的抄寫錯誤:遞迴左段時必須傳入 low,而不是硬寫 0。寫成 0 在第一次呼叫時剛好沒差,但只要 sort 被巢狀呼叫過就會出錯。

效率分析

  • 時間複雜度:最佳 O(n log n)、平均 O(n log n)、最差 O(n²)(例如序列已排序且固定取首元素為基準)。隨機選基準或三數取中可以有效避開最壞情況。
  • 空間複雜度:主要來自遞迴呼叫堆疊,平均 O(log n),最壞 O(n)。
  • 穩定性:不穩定。
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved