经典排序算法解析：归并与堆排序实战

一、今天学习目标

1. 归并排序（分治法经典，稳定排序）
2. 堆排序（利用堆结构实现，原地排序）
3. 完整可运行代码
4. 复杂度与适用场景总结

二、归并排序（Merge Sort）

核心思想：分而治之

1. 把数组不断二分，直到每组只有 1 个元素
2. 再把两个有序子数组合并成一个大的有序数组
3. 递归完成

特点：

• 稳定排序
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)（需要临时数组）

// 合并两个有序区间 [l..mid] 和 [mid+1..r] void merge(int arr[], int l, int mid, int r) { int i = l, j = mid + 1, k = 0; int tmp[r - l + 1]; while (i <= mid && j <= r) { if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= mid) tmp[k++] = arr[i++]; while (j <= r) tmp[k++] = arr[j++]; // 拷贝回原数组 for (i = l, k = 0; i <= r; i++, k++) arr[i] = tmp[k]; } // 归并排序递归 void mergeSort(int arr[], int l, int r) { if (l < r) { int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } }

三、堆排序（Heap Sort）

核心思想：利用大顶堆

1. 把数组构建成大顶堆
2. 堆顶（最大值）与最后一个元素交换
3. 堆大小减 1，重新调整堆
4. 重复直到完成排序

特点：

• 不稳定排序
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)原地排序

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } // 下沉调整（大顶堆） void siftDown(int arr[], int n, int i) { while (1) { int maxPos = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[maxPos]) maxPos = left; if (right < n && arr[right] > arr[maxPos]) maxPos = right; if (maxPos == i) break; swap(&arr[i], &arr[maxPos]); i = maxPos; } } // 堆排序 void heapSort(int arr[], int n) { // 建堆 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, n, i); // 依次取堆顶 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); siftDown(arr, i, 0); } }

四、完整测试代码

#include <stdio.h> // 上面所有函数放这里 void printArr(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr1[] = {6, 1, 8, 3, 5, 2, 7, 4}; int n = sizeof(arr1) / sizeof(arr1[0]); printf("原数组："); printArr(arr1, n); // 归并排序 int arr2[8]; for (int i = 0; i < n; i++) arr2[i] = arr1[i]; mergeSort(arr2, 0, n - 1); printf("归并排序："); printArr(arr2, n); // 堆排序 int arr3[8]; for (int i = 0; i < n; i++) arr3[i] = arr1[i]; heapSort(arr3, n); printf("堆排序："); printArr(arr3, n); return 0; }

运行结果：

原数组：6 1 8 3 5 2 7 4 归并排序：1 2 3 4 5 6 7 8 堆排序：1 2 3 4 5 6 7 8

五、O (n log n) 排序对比

表格

六、今日小练习

对数组{9, 4, 2, 7, 1, 6, 8, 3, 5}分别使用归并排序、堆排序并输出结果。