排序算法對比：快速排序、歸并排序、堆排序

1. 快速排序（Quick Sort）

原理

快速排序采用 分治法（Divide and Conquer），通過選取基準值（pivot），將數組劃分為 小于基準值 和 大于基準值 的兩個部分，并遞歸排序。

特點

• 時間復雜度：
  • 最優：O(n log n)
  • 平均：O(n log n)
  • 最差：O(n2)（當選取的 pivot 總是最小或最大值時，會退化成冒泡排序）
• 空間復雜度：O(log n)（遞歸調用棧）
• 是否穩定：? 不穩定（交換過程中可能改變相同元素的相對位置）
• 適用場景：
  • 適用于大規模數據排序
  • 數據較隨機時性能較優
  • 不適用于數據接近有序 或 需要穩定性的場景

---

2. 歸并排序（Merge Sort）

原理

歸并排序同樣采用 分治法，將數組拆分成 左右兩部分，分別排序后再 合并（merge），確保整體有序。

特點

• 時間復雜度：
  • 最佳、最差、平均：O(n log n)（即使是最壞情況下也能保持 O(n log n)）
• 空間復雜度：O(n)（額外存儲歸并時的數組）
• 是否穩定：? 穩定（歸并過程不會打亂相同元素的相對順序）
• 適用場景：
  • 適用于數據量大且需要穩定性的情況
  • 適用于鏈表排序
  • 適用于外部排序（大數據排序），因其可并行處理數據

---

3. 堆排序（Heap Sort）

原理

堆排序基于 二叉堆（Binary Heap） 數據結構，先將數組構造成 最大堆（Max Heap），然后依次取出堆頂元素（最大值），調整堆結構，最終得到一個有序數組。

特點

• 時間復雜度：
  • 最優、平均、最差：O(n log n)
• 空間復雜度：O(1)（原地排序，不需要額外空間）
• 是否穩定：? 不穩定（堆調整過程中可能改變相同元素的相對位置）
• 適用場景：
  • 適用于 大規模數據排序
  • 適用于 對最壞情況有較好保證 的場景
  • 適用于 優先隊列的實現

---

4. 排序算法對比

排序算法	時間復雜度（最優）	時間復雜度（平均）	時間復雜度（最差）	空間復雜度	是否穩定	適用場景
快速排序	O(n log n)	O(n log n)	O(n2)（退化）	O(log n)	? 不穩定	適用于大規模數據，且數據較隨機時性能較優
歸并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	? 穩定	適用于數據量較大且需要穩定性的情況，如鏈表排序、外部排序
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	? 不穩定	適用于 原地排序 且對 最壞情況 有較好保證的場景

---

5. 選擇哪種排序？

• 快速排序：一般情況下最快，適用于數據規模大、數據隨機分布的情況。
• 歸并排序：適用于數據量大、穩定性要求高 的情況，如數據庫排序。
• 堆排序：適用于 大規模數據排序，適用于 時間復雜度需要穩定的情況。

推薦：

• 如果數據量大，推薦 快速排序（但注意避免最壞情況）。
• 如果要求穩定排序，推薦 歸并排序。
• 如果空間受限，推薦 堆排序（因為它是 O(1) 空間復雜度的 O(n log n) 排序算法）。

---

總結：

1. 快速排序 是平均情況下最快的 O(n log n) 排序，但最壞情況下退化為 O(n2)。
2. 歸并排序 始終 是 O(n log n)，但需要額外 O(n) 空間，是穩定排序。
3. 堆排序 適用于大數據且需要 O(1) 額外空間，但不穩定。