做网站广告,小果seo实战培训课程,公众号如何推广,坂田杨美企业网站建设注意点1#xff1a;判断插入排序不能从头开始判断是否为目标数组#xff0c;
比如#xff1a;初始为1 2 3 4 3#xff0c;目标数组也为1 2 3 4 3#xff0c;则如果是从头开始推的#xff0c;则下一步会变成1 2 3 4 3#xff0c;而下一步应该是 1 2 3 3 4。所以我们应该…注意点1判断插入排序不能从头开始判断是否为目标数组
比如初始为1 2 3 4 3目标数组也为1 2 3 4 3则如果是从头开始推的则下一步会变成1 2 3 4 3而下一步应该是 1 2 3 3 4。所以我们应该从第一个无序的位置开始排序。也就是从最后一个3开始排序判断目标数组。
注意点2题目中的归并排序为相邻归并递推归并而非中分归并递归归并。
技巧点排序可以用sort减少思考步骤。
常规模拟版
#includebits/stdc.h
using namespace std;
int a[110],b[110],c[110];
int n;
bool check(){for(int i0;in;i){if(c[i]!b[i])return 0;}return 1;
}
void print(){for(int i0;in;i){coutc[i];if(i!n-1)cout ;}
}
bool insert(){bool flag0;for(int i1;in;i){//找到第一个无序的位置排序。if(c[i-1]c[i])continue;if(check())flag1;int posi;int tempc[i];while(pos0c[pos-1]temp){c[pos]c[pos-1];pos--;}c[pos]temp;if(flag)return 1;}return 0;
}
void merge(){bool flag0;for(int len2;lenn;len*2){if(check())flag1;for(int l0;ln;llen){int rmin(n-1,llen-1);int midllen/2-1;int il,jmid1;vectorinttemp;while(imidjr){if(c[i]c[j])temp.push_back(c[i]);else temp.push_back(c[j]);}while(imid)temp.push_back(c[i]);while(jr)temp.push_back(c[j]);for(il,j0;ir;i,j){c[i]temp[j];}}if(flag)return ;}
}
int main(){cinn;for(int i0;in;i)cina[i];for(int i0;in;i)cinb[i];memcpy(c,a,sizeof a);if(insert()){coutInsertion Sortendl;print();}else {memcpy(c,a,sizeof a);merge();coutMerge Sortendl;print();}
}
sort版
#includebits/stdc.h
using namespace std;
int a[110],b[110],c[110];
int n;
bool check(){for(int i0;in;i){if(c[i]!b[i])return 0;}return 1;
}
void print(){for(int i0;in;i){coutc[i];if(i!n-1)cout ;}
}
bool insert(){bool flag0;for(int i1;in;i){//找到第一个无序的位置排序。if(c[i-1]c[i])continue;if(check())flag1;sort(c,ci1);if(flag)return 1;}return 0;
}
void merge(){bool flag0;for(int len2;lenn;len*2){if(check())flag1;for(int i0;in;ilen){int jmin(n,ilen);sort(ci,cj);}if(flag)return ;}
}
int main(){cinn;for(int i0;in;i)cina[i];for(int i0;in;i)cinb[i];memcpy(c,a,sizeof a);if(insert()){coutInsertion Sortendl;print();}else {memcpy(c,a,sizeof a);merge();coutMerge Sortendl;print();}
}
