PTA basic 1035 插入与归并 (25 分) c++语言实现(g++)

2023-08-08 08:51:40

根据*的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 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通过

之前写的归并函数存在边界处理问题,但是我不知道具体原因,找了很久没找到放弃了,把问题代码放在了下面

测试用例

1 2 3 8 4 3 1

1 2 3 8 3 4 1

2 3 5 6 7 1 8 4

1 2 3 5 6 7 8 4

1 2 3 8 4 3 1 2

1 2 3 8 3 4 1 2

1 3 2

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);
    }
}

码农公寓