原题连接
更好的阅读体验
Hint:阅读密码在本文章最下面哦.
题目描述
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
解题报告
题意理解
这道题目还是让我们排序,只不过这里强制要求我们使用归并排序,所以既然如此的话,让我们好好地康康这道题目.
算法处理
归并排序,它有两大核心操作.
一个是将数组一分为二,一个无序的数组成为两个数组.
另外一个操作就是,合二为一,将两个有序数组合并成为一个有序数组.
代码实现
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39790/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
蒟蒻的代码
#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)//缩短代码
const int N=1000000 +100;
int b[N],a[N],n;
void merge(int a[],int l,int r)
{
if (r-l<1)//区间长度小于1了
return ;
int mid=(l+r)>>1;//二分
merge(a,l,mid);//左半段
merge(a,mid+1,r);//右半段
int i=l,j=mid+1;
fir(k,l,r)
if (j>r || i<=mid && a[i]<=a[j])//将当前最小的放入备用数组.
b[k]=a[i++];//a[i]被放入,要么是当前最小,要么就是另外一个数组已经空了
else
b[k]=a[j++];
fir(k,l,r)
a[k]=b[k];
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
merge(a,1,n);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
阅读博客密码:Acwinghh 各位不要外传哦,毕竟大家都是VIP大佬!
给兄弟们分享个各类排序动态图解,转自CSDN
https://blog.csdn.net/kexuanxiu1163/article/details/103051357
太感谢了 光看代码老是想不明白
我去,救命了hxd
跪谢
为什么要把a传进去,a不是一个全局变量的数组嘛
bits/stdc++.h这个头文件在工程中用的多吗,
N=1e6+10;//为什么要加10 是怕溢出么?
是的
蟹蟹~
您客气了。
if (l >= r) return;
int mid = l + r >> 1; merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
dalao们,为什么这里是递归排序,我觉得这里没有排序的过程
这里是将原数组的由无序转为有序的操作,还没有进行排序,排序操作在下面,原数组是无序的还不能进行归并,这里递归的目的是以mid为中间边界进行划分,最后划分出一个个只有一个数的“部分”,由于只有一个数,所以这些“部分”是有序的,这样将一个原本无序的数组转换成一个个有序的“部分”,就可以进行归并排序了,最后递归回溯进行归并就完成排序了
66666666666666666666666666
#include [HTML_REMOVED]
using namespace std;
int n;
#define read(m) cin >> m
#define write(m) cout << m << ” “
#define rep for (int i = 1; i <= n; i)
int a[100005],tmp[100005];
void merge_sort(int q[],int l,int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q,l,mid),merge_sort(q,mid + 1,r);
int i = l,j = mid + 1,k = l;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k] = q[i];
else tmp[k] = q[j];
}
while(i <= mid) tmp[k] = q[i];
while(j <= r) tmp[k] = q[j];
for (i = l; i <= r; i) q[i] = tmp[i];
}
int main()
{
read(n);
rep read(a[i]);
merge_sort(a,1,n);
rep write(a[i]);
return 0;
}
int mid = l + r >> 1;问下大佬们>> 1是啥意思
相当于 / 2,但 >> 1是位运算,比 / 2 快很多
感谢大佬😘😘😘
图很形象,递归后排序的思想看这个就很清晰了,感谢大佬
太美丽啦
感谢
if (j>r || i<=mid && a[i]<=a[j])//将当前最小的放入备用数组.
大佬,想问一下这里为啥是j>r 不是应该j 不超过r吗 也就是说 j应该<=r
不太懂
我也这样想的 j<=r
j > r 就是默认右边的排完了
佬,可以把b数组赋值给a数组那的循环语句改成j<k吗
同问
可以的
tql
思路很好,还学到了缩短代码的写法,谢谢答主~
既然最后temp数组是排好序的,为什么不能直接输出temp数组,而需要for(int i = l, j = 0; i <= r; i, j) q[i] = temp[j],为什么而且直接输出temp数组答案不对
因为后面进行递归操作,要继续对q进行操作
最后一次递归应该是把两个有序数组合并为一个有序数组,此时temp数组应该是排好序的吧,但是直接输出temp不对啊
我好像明白了 谢了大佬
我不明白qaq
清晰的一批
递归处理左半段和有半段是处理左半段和有半段中l>=r的问题嘛
数据可视化这个网站可以