歸并排序：分治策略的經典實現
算法原理
歸并排序采用分治法策略，包含三個關鍵步驟：
-
分解：遞歸地將數組分成兩半
-
解決：對子數組進行排序
-
合并：將兩個有序子數組合并為一個有序數組
C語言實現
#include <stdio.h>
#include <stdlib.h>// 合并兩個有序子數組
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;int n2 = right - mid;// 創建臨時數組int *L = (int*)malloc(n1 * sizeof(int));int *R = (int*)malloc(n2 * sizeof(int));// 拷貝數據到臨時數組for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并臨時數組i = 0; j = 0; k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 拷貝剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}free(L);free(R);
}// 歸并排序主函數
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}性能分析
-
時間復雜度：O(n log n)（所有情況）
-
空間復雜度：O(n)（需要臨時數組）
-
穩定性：穩定排序（保持相等元素順序）
優化方向
-
小數組優化：當子數組較小時（如n<15）改用插入排序
-
原地歸并：減少空間使用但增加時間復雜度
-
并行化：利用多線程處理獨立子問題
堆排序：基于完全二叉樹的高效排序
算法原理
堆排序利用堆數據結構的特性：
-
建堆：將無序數組構建為最大堆
-
排序：反復取出堆頂元素（最大值）并調整堆
C語言實現
#include <stdio.h>// 調整堆
void heapify(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) {// 交換int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 遞歸調整受影響的子堆heapify(arr, n, largest);}
}// 堆排序主函數
void heapSort(int arr[], int n) {// 構建最大堆（從最后一個非葉子節點開始）for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 逐個提取元素for (int i = n - 1; i > 0; i--) {// 將當前根移動到數組末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 在減小的堆上調用heapifyheapify(arr, i, 0);}
}性能分析
-
時間復雜度：O(n log n)（所有情況）
-
空間復雜度：O(1)（原地排序）
-
穩定性：不穩定排序（可能改變相等元素順序）
優化方向
-
堆化優化：減少不必要的比較操作
-
多叉堆：使用d叉堆減少樹高度
-
并行建堆：利用多線程加速建堆過程
算法對比與選擇指南
| 特性 | 歸并排序 | 堆排序 |
|---|---|---|
| 時間復雜度 | O(n log n) | O(n log n) |
| 空間復雜度 | O(n) | O(1) |
| 穩定性 | 穩定 | 不穩定 |
| 適用場景 | 大數據量、外部排序 | 內存受限環境 |
| 最佳用途 | 需要穩定結果時 | 優先級隊列實現 |
實際應用建議
-
選擇歸并排序：
-
需要穩定排序結果
-
處理大數據集（特別是外部排序）
-
內存充足的情況
-
-
選擇堆排序：
-
內存受限環境
-
需要原地排序
-
實現優先級隊列
-
-
其他考慮：
-
小規模數據（n<100）可考慮簡單排序（如插入排序）
-
現代CPU架構下，歸并排序的緩存友好性可能帶來實際性能優勢
-
總結
歸并排序和堆排序都是基于O(n log n)復雜度排序算法，各有其特點和適用場景。
歸并排序作為分治策略的經典實現，優勢在于穩定性、可預測的性能以及適用于外部排序的特點。它的遞歸實現簡潔優雅，是理解分治思想的絕佳案例。在實際應用中，歸并排序是處理大規模數據、特別是無法全部裝入內存時的首選算法。
堆排序則充分利用了完全二叉樹的性質，實現了原地排序，空間效率極高。它不僅是一種排序算法，更重要的是其堆數據結構在優先級隊列等場景中有廣泛應用。堆排序特別適合內存受限的環境，或者需要同時維護優先級隊列功能的場景。
在實際開發中，選擇排序算法需要綜合考慮數據結構特征、穩定性要求、內存限制等多方面因素。現代標準庫通常會在不同場景下選擇最適合的排序算法，甚至采用混合策略以獲得最佳性能。
