题目描述
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
算法:归并排序
$O(nlog2n)$
思路:
- 先确定分界点,即序列的中间数。(与快排的分界点不一样,快排的分界点可以是任意的,这里不行。)
- 然后分别递归处理左右半边的数
- 每次比较左半边的起始处的值和右半边起始处的值,较小的就存放进临时数组temp里面去。
- 第三步处理完成之后,需判断左右半边时候还有剩余的,如果有就全部放在temp的后面。
- 最后一步,把temp临时数组里面排好序的数组再顺序放进原数组里面去。最终排序完成。
- 时间复杂度分析:如上图(参考y总讲解视频)。
(具体处理详见代码,有注释)
参考文献
y总视频
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
//q[N] :要排序的数组
int q[N];
//temp数组,用来临时记录答案的数组
int temp[N];
//l:数组的左边界 r:数组的右边界
void mergeSort(int q[],int l ,int r){
//判断当前区间里面没有数或者只有一个数,那么显然就不用再进行排序了。
if(l >= r) return ;
//确定分界点,也就是中间那个数
int mid = (l + r) / 2;
//递归处理左半边
mergeSort(q,l,mid);
//递归处理右半边
mergeSort(q,mid + 1, r);
/*归并排序采用的二分方法进行排序所以在每次递归处理左右半边的时候,左半边的左边界
和右半边的左边界都在变化中所以这里变量i是指向L(小写的这里加以区别),j同理
k是用来标记临时数组的,i是指向左半边的起始处l,j是指向右半边的起始处
*/
int k = 0 , i = l , j = mid + 1;
//当i,j都在其半边的范围之内,不断比较i,j处的值,较小的放进临时数组
while(i <= mid && j <= r)
//左半边起始处值的小左半边的进入,右边同理
if(q[i] < q[j]) temp[k++] = q[i++];
else temp[k++] = q[j++];
/*
这里两句话是处理比较到最后,还有一个半边有剩余值,但不确定哪半边有
剩余的,所以需要同时处理。
*/
while(i <= mid) temp[k++] = q[i++];
while(j <= r) temp[k++] = q[j++];
/*最后一步,把临时数组里面排好序的值放进原数组。最终排序完成。
这里的临时数组里面的值赋给原数组里面的值是一小段一小段进行赋值的因为这里
就是用而二分的方法进行每一小段的处理所以注意i = l(是小写的L不是1)
*/
for(int i = l, j = 0 ; i <= r; i++ , j++ ) q[i] = temp[j];
}
int main(){
int n;
cin>>n;
for(int i = 0 ; i < n ; i++) cin>>q[i];
mergeSort(q, 0 , n - 1);
for(int i = 0 ; i < n ; i++)cout<<q[i]<<' ';
return 0;
}