破解快速排序演算法：幾分鐘內從理論到實踐

快速排序是最快的排序演算法之一。它採用一組值，選擇其中一個值作為「樞軸」元素，並移動其他值，以便較低的值位於樞軸元素的左側，較高的值位於其右側。

快速排序是演算法世界中最優雅、最有效率的排序演算法之一。與冒泡排序或選擇排序等更簡單的演算法不同，快速排序採用複雜的分而治之策略，使其在實踐中速度顯著加快。雖然合併排序也使用分而治之，但快速排序獨特的分區方法通常會帶來更好的效能和記憶體使用。

平均時間複雜度：O(n log n)

最壞情況時間複雜度：O(n²)

空間複雜度：O(log n)

目錄

1. 什麼是快速排序演算法
2. 快速排序是如何運作的
   • 時間複雜度
   • 空間複雜度
3. JavaScript 實作
4. 結論

什麼是快速排序演算法

快速排序是一種高效的排序演算法，它的工作原理是從數組中選擇一個「主元」元素，然後根據其他元素是否小於或大於主元將它們劃分為兩個子數組。與先劃分後合併的歸併排序不同，快速排序在劃分過程中進行排序。

考慮與其他排序演算法的比較：

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

快速排序是如何運作的？

在深入研究快速排序演算法的 JavaScript 實作之前，讓我們透過四個簡單步驟手動對簡單的數字數組進行排序，逐步了解該演算法的工作原理。

快速排序可以分為四個簡單的步驟：

1. 從陣列中選擇一個主元。這個元素可以是列表/陣列中的第一個、最後一個、中間的甚至是隨機元素。
2. 重新排列數組，使所有小於基準的元素位於左側，所有大於基準的元素位於右側。
3. 將樞軸元素與數值較大的第一個元素交換，使樞軸位於中間。
4. 遞歸地將相同的操作應用於樞軸左側和右側的子數組。

讓我們將這些步驟應用到真實的陣列中。我們可以嗎？

初始陣列: [3, 6, 2, 7, 1]

第 1 步：選擇一個樞軸

• 為了簡單起見，我們選擇最後一個元素作為樞軸。
• 樞軸 = 1

第 2 步：圍繞樞軸重新排列數組

• 重新排列，使所有小於主元 (1) 的元素位於左側，所有大於主元的元素位於右側。
• 當我們瀏覽每個元素：
  • 3（大於 1）→ 保持在右側。
  • 6（大於 1）→ 留在右側。
  • 2（大於 1）→ 保持在右側。
  • 7（大於 1）→ 保持在右側。
• 重新排列的陣列: [1, 6, 2, 7, 3]

第 3 步：將樞軸交換到正確的位置

• 將主元 (1) 與第一個大於它的元素（即 6）交換。
• 交換後的陣列: [1, 3, 2, 7, 6]
• 現在，1 處於正確的位置（索引 0）。

第四步：子數組的遞歸快速排序

• 左子數組: []（1 中沒有剩餘的元素，所以這裡不需要排序）
• 右子數組: [3, 2, 7, 6]

---

遞歸地將右子數組 [3, 2, 7, 6] 排序

第 1 步：選擇一個樞軸

• 樞軸 = 6（最後一個元素）

第 2 步：圍繞樞軸重新排列數組

• 將小於 6 的元素排列在左側，將大於 6 的元素排列在右側：
  • 3（小於 6）→ 留在左邊。
  • 2（小於 6）→ 留在左邊。
  • 7（大於 6）→ 留在右側。
• 重新排列的陣列：[3,2,6,7]

第 3 步：將樞軸交換到正確的位置

• 6 已經在正確的位置（索引 2）。
• 陣列: [1, 3, 2, 6, 7]

第四步：子數組的遞歸快速排序

• 左子數組: [3, 2]
• 右子數組：[7]（單一元素，無需排序）

---

對左子數組 [3, 2] 進行排序

第 1 步：選擇一個樞軸

• 樞軸 = 2（最後一個元素）

第 2 步：圍繞樞軸重新排列數組

• 重新排列，使小於 2 的元素位於左側：
  • 3（大於2）→ 留在右側。
• 重新排列的陣列: [2, 3]

第 3 步：將樞軸交換到正確的位置

• 2 已經處於正確位置（索引 1）。
• 陣列: [1, 2, 3, 6, 7]

第四步：子數組的遞歸快速排序

• 左子數組：[]（無元素）
• 右子數組：[3]（單一元素，無需排序）

---

最終排序數組

對所有子數組進行排序後，我們得到最終的排序數組：

排序數組: [1, 2, 3, 6, 7]

以下是現實生活中如何運作的最佳說明：

時間複雜度

快速排序的時間複雜度因主元選擇而異：

• 最佳情況（O(n log n)）:

  • 當主元總是將陣列分成相等的兩半時發生
  • 類似歸併排序的效能

• 平均情況 (O(n log n)):

  • 最實用的場景
  • 由於更好的快取利用率而優於合併排序

• 最壞情況 (O(n²)):

  • 發生在已經排序的陣列和糟糕的主元選擇
  • 可以透過良好的樞紐選擇策略來避免

空間複雜度

快速排序的空間複雜度為 O(log n)，因為：

• 遞歸呼叫堆疊深度
• 就地分區（與歸併排序的 O(n) 額外空間不同）
• 與歸併排序相比，記憶體效率更高

JavaScript 實作

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

結論

快速排序因其效率和就地排序而成為流行的選擇。它具有 O(n log n) 平均情況性能和低空間複雜度，優於冒泡排序和選擇排序等更簡單的演算法。

重點：

1. 謹慎選擇樞紐選擇策略
2. 在快速排序和其他演算法之間做出決定時考慮輸入特徵
3. 使用隨機主元選擇以獲得更好的平均情況表現

---

---

保持更新和聯繫

確保您不會錯過本系列的任何部分，並與我聯繫以進行更深入的了解
關於軟體開發（Web、伺服器、行動或抓取/自動化）、資料的討論
結構和演算法，以及其他令人興奮的技術主題，請關注我：

伊曼紐爾·艾因德關注

軟體工程師|技術撰稿人 |後端、網路和行動開發人員？ |熱衷於打造高效且可擴充的軟體解決方案。 #讓連線？

• GitHub
• 領英
• X（推特）

敬請期待並祝您編碼愉快??‍??

以上是破解快速排序演算法：幾分鐘內從理論到實踐的詳細內容。更多資訊請關注PHP中文網其他相關文章！