#ms001. 归并排序

归并排序

归并排序

题目描述

​ 给定 n 个整数 xix_i,请使用归并排序(Merge Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 归并排序是一种基于分治思想的高效排序算法。它将待排序序列递归地分成两个子序列,分别排序后再将两个有序子序列合并成一个有序序列。归并排序的时间复杂度稳定为 O(n log n),不受输入数据初始顺序影响,是一种稳定的排序算法。

算法原理与步骤

  1. 分解(分治):将当前待排序区间 [l, r] 从中间位置 mid = (l+r)/2 分成两个子区间 [l, mid] 和 [mid+1, r]。
  2. 递归排序:对两个子区间分别递归调用归并排序,直到子区间长度不超过 1(即 l >= r),递归终止。
  3. 合并(归并):将两个已排序的子区间合并成一个有序序列。具体做法是使用两个指针 i 和 j 分别指向两个子区间的起始位置,比较 a[i] 和 a[j] 的大小,将较小的元素依次放入临时数组 b 中,直至一个子区间全部取完,再将另一个子区间剩余元素全部复制到 b 中。最后将 b 中的有序序列复制回原数组 a 的对应位置 [l, r]。
  4. 重复上述过程,最终整个序列有序。

输入格式

​ 第一行一个正整数 n,表示数字个数。 ​ 第二行 n 个整数,每个数在 int 范围内。

输出格式

​ 一行,输出排序后的 n 个整数,相邻数字用空格隔开。

输入输出样例

5
3 1 2 1 3
1 1 2 3 3

数据规模与约定

​ 1 ≤ n ≤ 5000

​ 数值范围:-10^9 ≤xi x_i ≤ 10^9

​ 时间限制:1 秒(归并排序 O(n log n),n=100000 时约 1.7×10^6 次操作,可轻松通过)

​ 内存限制:256 MB(临时数组 b 大小与 a 相同,约 0.8 MB,完全满足)

提示

​ 代码提示:

int a[100005], b[100005];  // 全局数组,b 为临时合并数组

void merge(int l, int r) {
    int mid = (l + r) / 2;
    int i = l;          // 左子区间起始位置
    int j = mid + 1;    // 右子区间起始位置
    int k = 0;          // 临时数组 b 的索引

    // 合并两个有序子区间
    while (i <= mid && j <= r) {
        // TODO: 如果 a[i] <= a[j],将 a[i] 放入 b[k],否则将 a[j] 放入 b[k]
        // 提示:b[k++] = a[i++] 或 b[k++] = a[j++]
    }
    // 将左子区间剩余元素复制到 b
    while (i <= mid) {
        // TODO: ?
    }
    // 将右子区间剩余元素复制到 b
    while (j <= r) {
        // TODO: ?
    }

    // 将有序的 b 复制回 a 的对应位置
    for (int ?; ?; x++) {
        a[?] = b[?];
    }
}

void mergesort(int l, int r) {
    if (l >= r) {
        return;  // 子区间长度不超过1,无需排序
    }
    int mid = (l + r) / 2;
    mergesort(?, ?);      // 递归排序左半部分
    mergesort(?, ?);  // 递归排序右半部分
    merge(l, r);            // 合并左右两个有序子区间
}

int main() {
    //数据输入
    mergesort(1, n);
    //数据输出
}

​ 运用提示:

​ 归并排序的核心在于“分治”和“合并”。分治将问题分解为小规模子问题,合并则将两个有序序列线性合并为一个有序序列。

​ 注意合并时临时数组 b 的下标 k 从 0 开始,复制回 a 时偏移量为 l。

​ 归并排序需要 O(n) 的额外空间(临时数组),但本题 n ≤ 100000,内存充足。

​ 归并排序是稳定的排序算法,即相等元素的相对顺序不会改变。

​ 递归深度为 O(log n),无需担心栈溢出。