题目描述
归并模板题(主要是归并的思想)
思想:通过不断递归将两个有序数列合并成一个有序数列以此类推,当合并两个有序数列时用到i,j两个光标一步一步比较大小通过temp数组暂时保存新排号的序列,然后将序列保存到原来数组;
模拟:https://visualgo.net/zh/sorting(排序网站)
1(二分):找到中间值进行二分;
2(递归):递归到只剩一个元素时就返回;
3(组合):通过i,j光标分别指向左右两个有序数列直到左 右某个数列的光标指向末尾结束;
4(扫尾):将余下的一侧有序数列继续加入temp数组保存;
5(归还):将l,r的新有序数列归还给原数组;
样例
5
3 1 2 4 5
算法1
时间复杂度
O(nlogn)
参考文献
y总课程
C++ 代码
#include<iostream>
int const maxn=1e5+10;
int q[maxn];
int temp[maxn];
using namespace std;
//递归模板
void merge_sort(int q[],int l,int r)
{
//递归结束条件
if(l>=r) return;
//1.二分
int mid=l+r>>1;
//2.递归左右
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
//3.组合 (左右两个有序数列)
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(q[i]<q[j]) temp[k++]=q[i++];
else temp[k++]=q[j++];
}
//4.扫尾
while(i<=mid) temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
//5.归还
for(int i=0,j=l;j<=r;i++,j++) q[j]=temp[i];
}
//主函数的输入输出
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++) scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++) printf("%d ",q[i]);
}