啊之前在大学MOOC上排序的时候课后作业就是这个 一直没写 然后按部就班刷题刷到这里了
自己辣鸡的思路：排一趟比较一趟，插入确实可以这样！但是归并在电脑上的实行机制不是想象中的那样的！！！！在电脑上是把左边全部排完再排右边，所以这个方法行不通，所以归并这里需要修改
小姐姐的思路：点击打开链接
第一：先遍历一遍B数组，找到还未交换的那个数（即前面比后面大的那个数）,i赋值为这个数的位置
第二：从这个数后面一个数开始遍历，判断a数组和b数组是否相等，如果相等j++
第三：判断 j是否等于n
如果相等则是插入排序
不相等则是归并排序
第四：对于插入排序
sort(a,a+i+2)第五:归并排序
两个两个排
到四个四个排
到八个八个排
int k=1;int flag= 1;while(flag){flag = 0;for(i=0;i<n;i++){if(a[i]!=b[i])flag = 1;} k = k*2;for(i=0;i<n/k;i++){sort(a+i*k,a+(i+1)*k,cmp);}sort(a+n/k*k,a+n,cmp);完整code:
#include<iostream>
#include<algorithm>
using namespace std;
int cmp(int a,int b)
{return a<b;
} int main()
{int n;int i,j;cin >> n;int *a = new int [n];int *b = new int [n];for(i=0;i<n;i++){cin >> a[i];}for(i=0;i<n;i++){cin >> b[i];}for(i=0; i<n-1 && b[i]<=b[i+1]; i++);//找到还未交换的那个数 //cout << i << endl<< endl; for(j=i+1;a[j]==b[j] && j<n;j++);//判断这个数后面的是否跟初始数字相等
// cout << j << endl;if(j==n)//如果相等是插入排序 {cout << "Insertion Sort" << endl;sort(a,a+i+2,cmp);}else{cout << "Merge Sort" << endl;int k=1;int flag= 1;while(flag){flag = 0;for(i=0;i<n;i++){if(a[i]!=b[i])flag = 1;} k = k*2;// cout << k << endl << endl;for(i=0;i<n/k;i++){//cout << i*k << " " << (i+1)*k <<"memeda" <<endl;sort(a+i*k,a+(i+1)*k,cmp);}// for(j=0;j<n;j++)
// {
// cout << a[j] << " ";
// }
// cout << endl;sort(a+n/k*k,a+n,cmp);//cout << n/k*k <<n <<endl;}}for(j=0;j<n-1;j++){cout << a[j] << " ";}cout << a[n-1];delete [] a;delete [] b;return 0;
}