归并排序：分治法的经典应用

一、前言归并排序是基于分治法的典型排序算法通过递归将数组拆分为最小单元单个元素再通过合并操作将有序子序列逐步组合成完整有序序列。其核心在于分解与合并的协同操作二、分治法与递归拆分分治法将原问题分解为若干规模较小但结构相似的子问题递归求解后再合并子问题的解。归并排序是分治法的直接体现拆分将待排序数组从中间分成左右两半分别递归排序直到每个子数组只包含一个元素单个元素天然有序。合并将两个有序子数组合并为一个有序数组。整个过程需要两个核心函数Divide递归拆分和Merge合并两个有序数组三、函数设计Divide函数负责递归拆分数组void Divide(int arr[], int left, int right) { int mid (left right) / 2; //可能会超int类型存储上限 left/2 right/2) if (left right) { //[left, right] mid //左半边[left, mid] 右半边[mid 1, right] Divide(arr, left, mid); Divide(arr, mid 1, right); Merge(arr, left, mid, right); //合并 } }Merge函数负责合并两个有序子数组void Merge(int arr[], int left, int mid, int right) { //0.安全判断 //1.申请一个辅助空间brr长度只要能放下合并的这两个组的所有元素即可 int len right - left 1; int* brr (int*)malloc(sizeof(int) * len); if (brr NULL) return; //exit(EXIT_FAILURE); //2.申请两个变量i j, 分别指向两个组的第一个元素 int i left; //左边组开头 int j mid 1; //右边组开头 int k 0; //辅助数组下标 //3.进入while循环循环条件i,j没有越界循环合法 while (i mid j right) { //4.比较i j指向的两个组的各自第一个元素值 // 谁小谁向下放brr,相等的话也是下放 if (arr[i] arr[j]) brr[k] arr[i]; else brr[k] arr[j]; } //5.当while循环进不去代表肯定i或者j走完了 //有一个组的数据被挪动完了则将另一个组没有挪动完的值同步 while (i mid) brr[k] arr[i]; while (j right) brr[k] arr[j]; //6.这是两个组的合并结果就在brr里面最后再将brr的数据同步给arr for (k 0; k len; k) { arr[left k] brr[k]; } // 释放临时空间 free(brr); brr NULL; }MergeSort函数对外接口void MergeSort(int arr[], int len) { //执行递归分函数 Divide(arr, 0, len - 1); }四、手算模拟以数组[5, 3, 8, 4, 2]为例拆分阶段第一层拆分[5,3,8]和[4,2]第二层拆分[5,3]、[8]和[4]、[2]第三层拆分[5]、[3]合并阶段合并[5]和[3]得到[3,5]合并[3,5]和[8]得到[3,5,8]合并[4]和[2]得到[2,4]最终合并[3,5,8]和[2,4]得到[2,3,4,5,8]五、复杂度分析时间复杂度所有情况均为O(n log n)。每次递归将问题规模减半log n层每层需O(n)时间合并。空间复杂度O(n)用于辅助数组。稳定性稳定由于合并时对相等元素优先取左子数组元素算法是稳定的六、优缺点对比优点时间复杂度稳定为O(n log n)不受输入数据分布影响。稳定排序适合需要保持原始顺序的场景。缺点需要额外O(n)空间不适合内存严格受限的环境。对比O(n²)排序如冒泡排序归并排序在大规模数据下效率显著更高但小规模数据可能因递归开销反而更慢。下次我们将讲解另一种分治排序——快速排序它采用不同的拆分策略按基准元素划分且可以做到原地排序。敬请期待