考研笔记

板子：归并排序

从中间对半分，左右两半分别排好，再用双指针合并成一个有序段。分割点永远在正中间，和数据无关，所以最好、最坏、平均都是 。

代码

int *B;                                      // 辅助数组（教材写法：全局指针，排序前申请 n 个）
 
void Merge(int A[], int low, int mid, int high) {   // 把有序的 A[low..mid] 和 A[mid+1..high] 合并
    for (int k = low; k <= high; k++) B[k] = A[k];  // 先把这一段整体复制到 B
    int i = low, j = mid + 1, k = low;       // i、j 分别扫描 B 的前后两段，k 是写回 A 的位置
    while (i <= mid && j <= high)
        A[k++] = B[i] <= B[j] ? B[i++] : B[j++];    // 用 <=：相等时先取前一段的，保证稳定
    while (i <= mid) A[k++] = B[i++];        // 剩下的直接接上（两个 while 只会执行一个）
    while (j <= high) A[k++] = B[j++];
}
 
void MergeSort(int A[], int low, int high) {
    if (low >= high) return;                 // 只有一个元素：已经有序
    int mid = (low + high) / 2;              // 从中间分成两半
    MergeSort(A, low, mid);                  // 左半 [low, mid]
    MergeSort(A, mid + 1, high);             // 右半 [mid+1, high]
    Merge(A, low, mid, high);                // 两半合并
}
// 调用：B = (int *)malloc(n * sizeof(int));  MergeSort(A, 0, n - 1);  free(B);

复杂度：时间最好、平均、最坏都是 ；空间 （辅助数组 B）。稳定。

关键边界

代码为什么
左半是 [low, mid]，右半是 [mid+1, high]mid 归左半。写成 [low, mid-1] 和 [mid, high] 的话，两个元素时 mid == low，右半还是原区间，会无限递归
B[i] <= B[j] 带等号相等时先取前一段的元素，相对次序不变，所以归并排序稳定
先复制到 B 再写回 A直接在 A 上合并会覆盖还没比较的元素
B 只申请一次在 Merge 里每次 malloc 也对，但频繁申请和释放很慢。教材用的是全局数组

易错点

  • 归并排序是唯一一个平均 而且稳定的排序算法，选择题的直接答案。
  • 二路归并的趟数是 ，手算题问「第 趟以后的序列」时，按长度 的有序段两两合并。
  • Merge 的写法和 有序表合并 是同一个骨架。

链接

反向链接