题目描述
把一个长度为N的数值数组按从小到大的顺序排序并输出
输入描述:
输入为两行 第一行为一个整型数字N 第二行输入N个整型数字num 代表数组里面的元素（每个元素之间用空格隔开）
输出描述:
输出为一行 即为数组从小到大排序后的结果 每个数字之间用空格隔开（行末没有空格）
自测输入
10
1 8 7 6 4 4 4 789 4 1
实际输出
1 1 4 4 4 4 6 7 8 789
归并排序
归是递归,并是合并
先递归,再排序
如何递归,将数组均分成两半(可能有一边多一个{奇数没法均分成两半})
然后将两块再分成四块 (循环了哈)
merge_sort(l,mid); merge_sort(mid+1,r);
直到分无可分,即长度为一
if(l >= r) return ;
再合并,我们是先递归,再合并
因从我们一定是从小区间先排序,小区间有序了,再去排序大区间
每一次排序区间长度分别为 [1,mid] [mid+1,r]
两个片段采用双指针法,令 i,j 分别为两个区间的头,k为临时数组的头(我们需要一个临时数组来存一下当前排序后的有序数据的结果)
int i=l,j=mid+1,k=1;
然后判断两个指针指向的数据谁小,小的放到临时数组中
while(i<=mid&&j<=r) { if(a[i]<=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; }
能比较的都比较完了,有剩余数据的那些,说明他们比另一个数组中的所有数据都大,丢在临时数组末尾就好
while(i<=mid) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++];
该区间排序完毕,但是我们是用临时数组来存储排序后的有序数据,所有我们需要把临时数组的数据,迁移到原数组的[l,r]区间内
for(int i=l,j=1;i<=r;i++,j++) a[i]=b[j];
给个板子
#include<iostream> #include<algorithm> using namespace std; const int N = 1e5+10; int a[N]; int b[N]; void merge_sort(int l,int r) { //当只剩一个元素的时候就不再进行递归了 if(l >= r) return ; int mid = l+r >>1; //先递归 merge_sort(l,mid); merge_sort(mid+1,r); //再合并 //将已经排好序的左右两边进行合并 //两边从前往后双指针进行判断,小的放到 b数组中 int i=l,j=mid+1,k=1; while(i<=mid&&j<=r) { if(a[i]<=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } while(i<=mid) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++]; //最后再把 b数组替换到 a数组对应位置 for(int i=l,j=1;i<=r;i++,j++) a[i]=b[j]; } int main() { //IOS 关闭流,可写可不写,你写个快读效果差不多(一般不会出现什么问题) ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; while(cin>>n) { for(int i=1;i<=n;i++) cin>>a[i]; merge_sort(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; } return 0; }
