一、今天学习目标归并排序分治法经典稳定排序堆排序利用堆结构实现原地排序完整可运行代码复杂度与适用场景总结二、归并排序Merge Sort核心思想分而治之把数组不断二分直到每组只有 1 个元素再把两个有序子数组合并成一个大的有序数组递归完成特点稳定排序时间复杂度O(n log n)空间复杂度O(n)需要临时数组// 合并两个有序区间 [l..mid] 和 [mid1..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重新调整堆重复直到完成排序特点不稳定排序时间复杂度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) 排序对比表格排序时间复杂度空间稳定性特点快排O(nlogn)O(logn)不稳定实际最快归并O(nlogn)O(n)稳定外部排序常用堆排O(nlogn)O(1)不稳定省内存六、今日小练习对数组{9, 4, 2, 7, 1, 6, 8, 3, 5}分别使用归并排序、堆排序并输出结果。