归并排序 (Merge Sort)像“分家再合并”一样先把队伍从中间劈成两半一直劈到每个人自成一个小队(天然有序)。然后两两合并在合并时像“双指针”一样每次只比较两个小队排头的人谁小谁先站到新的队伍里。不断向上合并最后整个队伍就排好序了。核心代码#include stdio.h // 辅助数组用于在合并时暂存数据 int temp[100]; // 合并函数将两个已排序的子数组合并成一个有序数组 void merge(int arr[], int left, int mid, int right) { int i left; // 左半部分起始指针 int j mid 1; // 右半部分起始指针 int k left; // 辅助数组的填充指针 // 双指针比较哪边小就把哪边的元素放入 temp while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 将左半部分剩余的元素直接倒入 temp while (i mid) temp[k] arr[i]; // 将右半部分剩余的元素直接倒入 temp while (j right) temp[k] arr[j]; // 将排好序的 temp 数据倒回原数组 arr for (int p left; p right; p) { arr[p] temp[p]; } } // 归并排序函数 void mergeSort(int arr[], int left, int right) { if (left right) return; // 递归终止条件区间只有一个元素 int mid (left right) / 2; // 找到中间分界点 mergeSort(arr, left, mid); // 递归排序左半边 mergeSort(arr, mid 1, right); // 递归排序右半边 merge(arr, left, mid, right); // 合并左右两边 } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 34, 25, 12, 22}; int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf(排序前); printArray(arr, n); mergeSort(arr, 0, n - 1); // 调用归并排序 printf(排序后); printArray(arr, n); return 0; }示例演示{64, 34, 25, 12, 22}第 1 步不断递归拆分(分治的“分”)目标将数组从中间劈开直到每个子数组只剩 1 个元素。拆分 {64, 34, 25, 12, 22} - {64, 34} 和 {25, 12, 22}继续拆分 {64, 34} - {64} 和 {34}继续拆分 {25, 12, 22} - {25} 和 {12, 22}继续拆分 {12, 22} - {12} 和 {22}拆分结束得到 5 个单元素子数组它们天然有序。第 2 步自底向上合并(分治的“治”)目标利用双指针将相邻的有序子数组合并成更大的有序数组。合并 {64} 和 {34}比较 64 34先放 34再放 64。结果{34, 64}合并 {12} 和 {22}比较 12 22先放 12再放 22。结果{12, 22}合并 {25} 和 {12, 22}比较 25 12放 12比较 25 22放 22左半部分剩 25 直接放入。结果{12, 22, 25}当前状态数组变成了两个有序块[34, 64] 和 [12, 22, 25]第 3 步最终合并目标将最后两个有序块合并成完整的有序数组。合并 {34, 64} 和 {12, 22, 25}比较 34 12放 12比较 34 22放 22比较 34 25放 25。此时右半边已合并完将左半边剩余的 {34, 64} 直接追加到末尾。合并完成。最终结果[12, 22, 25, 34, 64]复杂度时间复杂度是\(O(nlogn)\)(无论最好、最坏还是平均情况拆分和合并的代价都非常稳定)空间复杂度是\(O(n)\)(因为合并时需要借助一个与原数组等长的辅助数组 temp 来暂存数据)