前言

相較于上一期我講的冒泡、選擇、插入等基礎排序，快速排序、歸并排序和堆排序憑借更優的時間復雜度，成為處理大規模數據排序任務的首選方案。本文我將深入剖析這三種高效排序算法的原理、實現細節、性能特點及適用場景，助力你掌握它們在實際開發中的應用技巧。

一、快速排序（Quick Sort）

1.1 算法原理

快速排序由托尼?霍爾（Tony Hoare）于 1959 年提出，是一種基于分治思想的排序算法。其核心步驟如下：

選擇基準值：從數組中選取一個元素作為基準值（通常選擇第一個、最后一個或中間元素）。

分區操作：將數組分為兩個子數組，使得左邊子數組的所有元素都小于等于基準值，右邊子數組的所有元素都大于基準值。

遞歸排序：對左右兩個子數組分別遞歸地進行快速排序。

通過不斷重復上述步驟，最終使整個數組達到有序狀態。例如，對于數組[5, 3, 8, 6, 2]，若選擇5作為基準值，經過分區操作后，數組變為[3, 2, 5, 6, 8]，然后分別對[3, 2]和[6, 8]進行遞歸排序，最終得到有序數組[2, 3, 5, 6, 8]。

1.2 代碼實現（Python）

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

上述代碼中，首先判斷數組長度，若小于等于 1 則直接返回。接著選取基準值，通過列表推導式將數組分為小于、等于、大于基準值的三個部分，最后遞歸地對左右子數組進行排序并合并。

1.3 性能分析

時間復雜度：

平均情況下，快速排序的時間復雜度為$O(n\log n)$ ，其中n為數組元素個數。

最壞情況下（如數組已有序且每次選擇的基準值為最大或最小元素），時間復雜度退化為$O(n^2)$ 。

空間復雜度：快速排序的空間復雜度主要取決于遞歸調用棧的深度。平均情況下，空間復雜度為$O(\log n)$ ；在最壞情況下，遞歸深度達到n，空間復雜度為$O(n)$ 。

穩定性：快速排序是不穩定的排序算法，因為在分區過程中，相同元素的相對順序可能會發生改變。

二、歸并排序（Merge Sort）

2.1 算法原理

歸并排序同樣基于分治思想，它將一個數組分成兩個大致相等的子數組，分別對兩個子數組進行排序，然后將排好序的子數組合并成一個最終的有序數組。具體步驟如下：

分解：將待排序數組不斷平均分成兩個子數組，直到子數組長度為 1（單個元素可視為有序）。

排序：對每個子數組進行排序（可使用其他排序方法，通常也是遞歸地使用歸并排序）。

合并：從最底層開始，將兩個有序的子數組合并成一個更大的有序數組，不斷向上合并，直至得到整個有序數組。

例如，對于數組[8, 4, 2, 1, 7, 6, 3, 5]，先分解為多個子數組，再依次排序并合并，最終得到有序數組[1, 2, 3, 4, 5, 6, 7, 8]。

2.2 代碼實現（Java）

import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null) {return;}int[] temp = new int[arr.length];mergeSort(arr, temp, 0, arr.length - 1);}private static void mergeSort(int[] arr, int[] temp, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, temp, left, mid);mergeSort(arr, temp, mid + 1, right);merge(arr, temp, left, mid, right);}}private static void merge(int[] arr, int[] temp, int left, int mid, int right) {System.arraycopy(arr, left, temp, left, right - left + 1);int i = left;int j = mid + 1;int k = left;while (i <= mid && j <= right) {if (temp[i] <= temp[j]) {arr[k++] = temp[i++];} else {arr[k++] = temp[j++];}}while (i <= mid) {arr[k++] = temp[i++];}while (j <= right) {arr[k++] = temp[j++];}}public static void main(String[] args) {int[] arr = {8, 4, 2, 1, 7, 6, 3, 5};mergeSort(arr);System.out.println(Arrays.toString(arr));}
}

在上述 Java 代碼中，mergeSort方法作為入口，調用遞歸的mergeSort方法進行分解和排序，merge方法用于合并兩個有序子數組。通過臨時數組temp輔助完成合并操作，保證合并過程中數據的正確處理。

2.3 性能分析

時間復雜度：歸并排序無論在最好、最壞還是平均情況下，時間復雜度均為$O(n\log n)$ ，因為每次分解和合并操作的時間開銷相對固定，總操作次數與$n\log n$相關。

空間復雜度：歸并排序在合并過程中需要使用額外的空間存儲臨時數據，空間復雜度為$O(n)$ 。

穩定性：歸并排序是穩定的排序算法，在合并子數組時，相同元素的相對順序不會發生改變。

三、堆排序（Heap Sort）

3.1 算法原理

堆排序利用了堆這種數據結構（大頂堆或小頂堆）的特性來實現排序。大頂堆的特點是每個父節點的值都大于或等于其子節點的值，小頂堆則相反。堆排序的主要步驟如下：

建堆：將待排序數組構建成一個大頂堆（升序排序時）或小頂堆（降序排序時）。

交換與調整：將堆頂元素（最大值或最小值）與堆的最后一個元素交換，然后對剩余元素重新調整堆結構，使其再次滿足堆的性質。

重復操作：不斷重復步驟 2，直到堆中只剩下一個元素，此時數組即為有序狀態。

例如，對于數組[4, 6, 8, 5, 9]，先構建大頂堆[9, 6, 8, 5, 4]，然后將 9 與 4 交換，調整堆為[8, 6, 4, 5, 9]，依次類推，最終得到有序數組[4, 5, 6, 8, 9]。

3.2 代碼實現（C++）

#include <iostream>
#include <vector>
using namespace std;// 調整堆結構
void heapify(vector<int>& arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 堆排序
void heapSort(vector<int>& arr) {int n = arr.size();// 建堆for (int i = n / 2 - 1; i >= 0; --i) {heapify(arr, n, i);}// 交換與調整for (int i = n - 1; i > 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

上述 C++ 代碼中，heapify函數用于調整堆結構，確保以i為根節點的子樹滿足堆的性質。heapSort函數先進行建堆操作，然后通過不斷交換堆頂元素和堆的最后一個元素，并調整堆結構，實現排序功能。

3.3 性能分析

時間復雜度：堆排序的時間復雜度主要由建堆和調整堆兩部分組成。建堆的時間復雜度為$O(n)$ ，調整堆的時間復雜度為$O(n\log n)$ ，因此整體時間復雜度為$O(n\log n)$ ，且在最好、最壞和平均情況下均保持不變。

空間復雜度：堆排序在排序過程中只需要常數級別的額外空間，空間復雜度為$O(1)$ 。

穩定性：堆排序是不穩定的排序算法，因為在調整堆結構時，相同元素的相對順序可能會被打亂。

四、三種高效排序算法的對比與適用場景

排序算法	平均時間復雜度	最壞時間復雜度	空間復雜度	穩定性	適用場景
快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不穩定	數據隨機分布、對空間要求不高的場景；適合內部排序，常用于通用排序庫
歸并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	穩定	對穩定性有要求、外部排序（如處理大文件）、數據規模較大且內存充足的場景
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不穩定	對空間要求嚴格、需要在線性時間內找到最大 / 最小元素的場景，如優先隊列實現

總結

快速排序、歸并排序和堆排序作為高效排序算法，在不同的應用場景中發揮著各自的優勢。快速排序憑借其簡潔高效的特點，在多數常規排序任務中表現出色；歸并排序以穩定的性能和適用于外部排序的特性，成為處理大規模數據的可靠選擇；堆排序則因其對空間的高效利用和穩定的時間復雜度，在特定場景下展現出獨特價值。下期博客中,我將帶你探索更多高級排序算法與優化技巧，例如希爾排序、計數排序等，分析它們與快速排序、歸并排序、堆排序的差異，以及在不同業務場景中的實際應用案例，幫助大家進一步拓寬排序算法的知識邊界。

That’s all, thanks for reading!
創作不易，點贊鼓勵；
知識無價，收藏備用；
持續精彩，關注不錯過！