根据*的定义:
插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作:首先将原始序列看成 N 个只包含 1 个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法?
输入格式:
输入在第一行给出正整数 N (≤100);随后一行给出原始序列的 N 个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式:
首先在第 1 行中输出Insertion Sort
表示插入排序、或Merge Sort
表示归并排序;然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行首尾不得有多余空格。
输入样例 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
输出样例 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0
输入样例 2:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
输出样例 2:
Merge Sort 1 2 3 8 4 5 7 9 0 6
解题思路
测试点024为插入排序 测试点1356为归并排序
第一次提交 测试点0 1 通过 23456不通过
第二次提交 测试点01234通过
第三次提交 测试全通过 使用了algorithm库提供的sort()函数之后,测试点5,测试点6通过
之前写的归并函数存在边界处理问题,但是我不知道具体原因,找了很久没找到 放弃了,把问题代码放在了下面
测试用例
7
1 2 3 8 4 3 1
1 2 3 8 3 4 1
8
2 3 5 6 7 1 8 4
1 2 3 5 6 7 8 4
8
1 2 3 8 4 3 1 2
1 2 3 8 3 4 1 2
3
1 3 2
1 3 2
11
3 1 2 8 7 5 9 4 11 0 6
1 2 3 8 4 5 7 9 0 6 11
AC代码
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <algorithm> 5 using namespace std; 6 //直接插入排序一轮迭代 7 void dsort_onestep(vector<int> &pres_sorted,int i){//i为标记当前有序序列的下一位 8 int temp,j; 9 if(pres_sorted[i]<pres_sorted[i-1]){ 10 temp=pres_sorted[i];//暂存Ai为temp 11 for(j=i;temp<pres_sorted[j-1]&&j>0;j--){//从i位置开始 把temp与前面每一个元素进行比较,将大于temp的元素向后移动一位 12 pres_sorted[j]=pres_sorted[j-1]; 13 } 14 pres_sorted[j]=temp;//把temp放入最后一个小于temp的元素的后面的位置 15 } 16 } 17 18 19 void merge_onestep(vector<int>&preSorted,int steplength){//一轮归并,使用sort()库函数 20 int maxIndex=preSorted.size()-1;//数组结尾标记 21 int i; 22 for(i=0;i+steplength<maxIndex;i+=steplength){//使前 步长*(size/步长)个元素有序,m=size%步长为剩下未处理的m个元素 23 sort(preSorted.begin()+i,preSorted.begin()+i+steplength); 24 } 25 if(i<maxIndex){//使剩下的元素有序 26 sort(preSorted.begin()+i,preSorted.end()); 27 } 28 } 29 30 void printArray(vector<int> nums){//打印数组 31 int i; 32 for(i=0;i<nums.size()-1;i++){ 33 cout << nums[i] <<" "; 34 } 35 cout <<nums[i]<<endl; 36 } 37 38 int main(){ 39 int flag=1,i,steplength; 40 int n{0}; 41 cin >> n ; 42 vector<int> nums(n,0);//原序列 43 vector<int> compare(n,0);//中间序列 44 vector<int> directly_insertion_sorted;//直接插入算法序列 45 vector<int> merge_sorted;//归并排序序列 46 47 for(i=0;i< n;i++){ 48 cin >> nums[i]; 49 } 50 for(i=0;i< n;i++){ 51 cin >> compare[i]; 52 } 53 merge_sorted=nums; 54 directly_insertion_sorted=nums; 55 56 for(i=1;i<nums.size();i++){//是否为插入算法,每一趟比较一次 是则标记flag为0; 57 dsort_onestep(directly_insertion_sorted, i); 58 if(directly_insertion_sorted==compare){ 59 flag=0; 60 break; 61 } 62 } 63 if(flag==0){ 64 cout << "Insertion Sort" << endl; 65 while(directly_insertion_sorted==compare){ 66 dsort_onestep(directly_insertion_sorted,++i);//继续迭代到下一次数组元素位置变动 67 } 68 printArray(directly_insertion_sorted); 69 }else{ 70 for(steplength=2;steplength<merge_sorted.size();steplength*=2){ 71 //初始步长为2,迭代一次比较一次,然后步长*2直到步长大于元素个数,因为题目要求匹配后继续迭代一次,所以步长一定小于数组大小 72 merge_onestep(merge_sorted,steplength); 73 if(merge_sorted==compare){ 74 flag=1; 75 break; 76 } 77 } 78 cout << "Merge Sort"<<endl; 79 while(merge_sorted==compare){ 80 merge_onestep(merge_sorted,steplength*2);//继续迭代到下一次数组元素位置变动 81 } 82 printArray(merge_sorted); 83 } 84 return 0; 85 }
直接插入排序
A0到An依次插入一个有序序列
实现算法时,默认A0是有序序列,从A2开始排序
Ai与前一位比较,如果小于前一位,则寻找插入位置,先将Ai暂存,从Ai开始向前查找,依次将比Ai大的元素向后挪动一位,直到遇到一个位置的元素比Ai小时
将Ai插入该元素之后
1 //直接插入排序 2 void directly_insertion_sort(vector<int>& pre_sorted){ 3 int temp,j; 4 for(int i=1;i<pre_sorted.size();i++){//从第二个元素开始是第一轮迭代 5 if(pre_sorted[i]<pre_sorted[i-1]){ 6 //如果当前元素小于前面的元素,先暂存这个元素,然后把前面比当前元素大的元素都后移一个位置 7 //把当前元素放入最后一个比当前元素小的位置,恰好是移动后空缺出来的位置 8 temp=pre_sorted[i]; 9 for(j=i;temp<pre_sorted[j-1];j--){ 10 pre_sorted[j]=pre_sorted[j-1]; 11 } 12 pre_sorted[j]=temp; 13 } 14 } 15 }
归并排序
归并排序分为两个部分,两个有序子序列合并为一个新的有序序列,以及待排序数列递归划分成子序列直到子序列只有1个元素为止,使用的是分而治之的思想
merge()的功能是两个有序子序列合并为一个新的有序子序列,而mergeSort()的功能是待排序序列划分子序列然后调用merge()依次合并子序列
merge(int list[],int low,int mid, int high)
low,mid分别是子序列1的第一个元素和最后一个元素下标,mid+1和high是子序列2的第一个元素和最后一个元素下标
合并过程是先将list的中的元素都复制到辅助数组中,然后比较辅助数组的 两个子序列的第一个元素开始比较,数值小的就加入原数组
然后原数组下标和拿出元素的子序列下标后移,直到一个子序列到达末尾下标后,结束循环
将没有到达末尾下标的子序列中剩余元素取出放入原数组
mergeSort()的功能是递归划分子序列以及调用merge()合并划分后的子序列,分别合并左右两边子序列后,类似后序遍历
1 void merge(vector<int>&preSorted,int low,int mid,int high){//合并两个相邻子序列 2 vector<int>temp{preSorted}; 3 int i,j,k=0; 4 for(i=low,j=mid+1,k=i;j<=high&&i<=mid;k++){ 5 if(temp[i]<temp[j]){ 6 preSorted[k]=temp[i++]; 7 }else{ 8 preSorted[k]=temp[j++]; 9 } 10 } 11 while(j<=high)preSorted[k++]=temp[j++]; 12 while(i<=mid)preSorted[k++]=temp[i++]; 13 } 14 15 void mergeSort(vector<int>&preSorted,int low,int high){//递归划分子序列,依次合并两个相邻序列 16 if(low<high){ 17 int mid=(low+high)/2; 18 mergeSort(preSorted, low,mid); 19 mergeSort(preSorted, mid+1,high); 20 merge(preSorted,low,mid,high); 21 } 22 }
//不能通过测试点5 6的归并一轮迭代方法
void msort_onestep(vector<int>&preSorted,int steplength){//一轮归并 int maxIndex=preSorted.size()-1; int i,j,mid; for(i=0;i+steplength<maxIndex;i+=steplength){ j=i+steplength-1; mid=(i+j)/2; merge(preSorted,i,mid,j); } if(i<maxIndex){ j=maxIndex; mid=(i+j)/2; merge(preSorted,i,mid,j); } }