题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
思路
归并中的 “归”
归并排序实际上是运用分治法的一个问题,把一个大问题分为两个小问题,然后我们运用递归把小问题继续划分为两个小小问题。
设定要排序的边界l
和r
,如果l >= r
即要排序的数组内元素小于等于1,认为该数组排序完成,此即递归终点
归并中的 “并”
为了方便,我们把大数组a分为的两个小数组称为Left
和Right
,再定义临时数组tmp
,大数组的下标中点为mid
我们使用指针i
j
分别指向两个数组的起始端,即最小值(这两个数组已经排序好了,想想为什么)
此时我们比较Left[i] <= Right[j]
若成立,将Left[i]
放入tmp,i++
i指向下一个数
若不成立,将Right[j]
放入tmp,j++
j指向下一个数
我们的目的是从小到大排序,上述步骤的比较则是为了把两个数组中的最小值放入临时数组,两个数组的最小值即为大数组的最小值
我们知道,i和j不一定都能指向终点,所以我们还需要进行处理
我们判断while (i <= mid)
,通过判断i是否能指向终点的方式把左边数组剩下的数字放入临时数组,右边数组同理
为什么能直接放入临时数组呢?任一边数组的数字剩余,说明另一边数组的数字一定全部放入,思考一下。
以下是代码实现
C++ 代码
//
// Created by Owwkmidream on 2021/10/28.
//
#include "iostream"
using namespace std;
const int N = 100008;
int a[N],tmp[N];
void merge_soft(int p[], int l,int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_soft(p, l, mid), merge_soft(p, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid and j <= r)
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (i = l, j = 0; i <= r; ++i, ++j)
p[i] = tmp[j];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
merge_soft(a, 0, n - 1);
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
return 0;
}