#ms001. 归并排序
归并排序
归并排序
题目描述
给定 n 个整数 ,请使用归并排序(Merge Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。
算法概念
归并排序是一种基于分治思想的高效排序算法。它将待排序序列递归地分成两个子序列,分别排序后再将两个有序子序列合并成一个有序序列。归并排序的时间复杂度稳定为 O(n log n),不受输入数据初始顺序影响,是一种稳定的排序算法。
算法原理与步骤
- 分解(分治):将当前待排序区间 [l, r] 从中间位置 mid = (l+r)/2 分成两个子区间 [l, mid] 和 [mid+1, r]。
- 递归排序:对两个子区间分别递归调用归并排序,直到子区间长度不超过 1(即 l >= r),递归终止。
- 合并(归并):将两个已排序的子区间合并成一个有序序列。具体做法是使用两个指针 i 和 j 分别指向两个子区间的起始位置,比较 a[i] 和 a[j] 的大小,将较小的元素依次放入临时数组 b 中,直至一个子区间全部取完,再将另一个子区间剩余元素全部复制到 b 中。最后将 b 中的有序序列复制回原数组 a 的对应位置 [l, r]。
- 重复上述过程,最终整个序列有序。
输入格式
第一行一个正整数 n,表示数字个数。 第二行 n 个整数,每个数在 int 范围内。
输出格式
一行,输出排序后的 n 个整数,相邻数字用空格隔开。
输入输出样例
5
3 1 2 1 3
1 1 2 3 3
数据规模与约定
1 ≤ n ≤ 5000
数值范围:-10^9 ≤≤ 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),无需担心栈溢出。