插入与归并(25)

#include <algorithm>
#include <iostream>
using namespace std;
int n,a[110],s[110];
void mergesort(int (&a)[110],int s[],int n){   //注意引用数组的写法
    int step=1,flag=1;
    while(flag){                               //flag表示数组的中间步骤是否与中间数组相同
        flag=0;
        for(int i=0;i<n;i++){
            if(a[i]!=s[i])
                flag=1;
        }
        step*=2;                              //不断的归并排序，直到与中间数组相同，再排序一次并退出
        for(int i=0;i<n;i+=step)
            sort(a+i,a+min(i+step,n));        //不像插入排序一样只用一次处理。是因为判断归并的有序 区间大小比较复杂
    }
}
int main(){
    int i,j;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
        cin>>s[i];
    for (i = 0; i < n - 1 && s[i] <= s[i + 1]; i++);  //找出中间数组的有序部分
    for (j = i + 1; a[j] == s[j] && j < n; j++);      //判断排序类型
    if(j==n){
        cout<<"Insertion Sort"<<'\n'; 
        sort(a,a+i+2);                      //直接用sort函数代替插入排序（注意下标）       
    }
    else{
        cout<<"Merge Sort"<<'\n';
        mergesort(a,s,n);
    }
    for(int i=0;i<n;i++){
        cout<<a[i];
        if(i!=n-1) cout<<" ";
    }
    return 0;
}

	

import java.util.Scanner;
import java.util.Arrays;
public class No1025 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n];//原始的
		int[] b = new int[n];//部分排序过的
		for(int i = 0;i<n;i++)
			a[i] = in.nextInt();
		for(int i = 0;i<n;i++)
			b[i] = in.nextInt();
		String type = "Insertion Sort";
		int index = 0;
		for(int i = 0;i<n-1;i++){
			if(b[i]>b[i+1]){
				index = i+1;//从i+1这里开始无序
				break;
			}
		}
		for(int i = index;i<n;i++){
			if(a[i]!=b[i]){
				type = "Merge Sort";//如果是插入排序，从index开两个数组的顺序是一样的
				break;
			}
		}
		if(type.equals("Insertion Sort")){
			int num = b[index];
			for(int j = index;j>0;j--){
				if(b[j]<b[j-1]){
					b[j] = b[j-1];
					b[j-1] = num;
				}
			}
		}else{
			//如果是归并排序 index的值表示这么多的规模已经排序完，
			//比如index==2 说明规模为2的已经排序完 下一次排序规模为4 
			index = 2*index;
			for(int i = 0;i<n;i+=index){
				int next = i+index>n?n:i+index;
				Arrays.sort(b,i,next);
			}
		}
		System.out.println(type);
		for(int i = 0;i<n-1;i++)
			System.out.print(b[i]+" ");
		System.out.print(b[n-1]);
	}
}

PAT_B插入与归并

的测试用例有问题

10

3 1 2 8 7 5 9 4 6 0

1 2 3 5 7 8 9 4 6 0

已排序部分既有可能是

1 2 3 5 7 8

也有可能是

1 2 3 5 7 8 9

会造成多解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void main() {
	int N,next = 0;
	cin >> N;
	vector<int> org,cur;
	enum property{insert,merge}pro = insert;
	for(int i = 0; i < N; ++i)
                cin >> org[i];
	for(int i = 0; i < N; ++i)
                cin >> cur[i];
	for(unsigned int i = 1; i < cur.size(); ++i) {
		if(cur[i] < cur[i-1]) {
			next = i;
			for(; i < cur.size(); ++i) {
				if(cur[i] != org[i]) {//走到这里，说明就是归并了
					pro = merge;
					break;
				}
			}
		}
		if(pro == merge)
		    break;
	}
	if(pro == insert) {
		cout << "Insertion Sort" << endl;
		for(unsigned int i = 0; i < cur.size(); ++i) {
			if(cur[i] < cur[next])
				cout << cur[i] << " ";
			else {
				cout << cur[next] << " ";
				vector<int>::iterator it = cur.begin() + next;
				cur.erase(it);
				for(;i < cur.size(); ++i) {
					cout << cur[i];
					if(i != cur.size() - 1)
						cout << " ";
				}
			}
		}
	}else {
		cout << "Merge Sort" << endl;
		for(unsigned int i = 0; i < cur.size() / (next * 2); ++i)
			sort(cur.begin() + i*next*2, cur.begin() + i*next*2 + next*2);
		for(unsigned int i = 0; i < cur.size(); ++i) {
			cout << cur[i];
			if(i != cur.size() - 1)
				cout << " ";
		}
	}
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int a[]=new int[n];
		int b[]=new int[n];
		for (int i=0;i<n;i++){
			a[i]=in.nextInt();
		}
		for (int i=0;i<n;i++){
			b[i]=in.nextInt();
		}
		
		Boolean f=false;
		int index=0;
		while(b[index+1]>=b[index]){
			index++;
		}
		for(int j=index+1;j<n;j++){
			if(a[j]!=b[j]){
				f=true;
				break;
			}
		}
		
		if(!f){
			System.out.println("Insertion Sort");
			int j=index;
			int i=b[index+1];
			while(j>=0&&b[j]>i){
				b[j+1]=b[j];
				j--;
			}
				b[j+1]=i;
				
		}else{
			System.out.println("Merge Sort");
			index=(index+1)*2;
			int k=0;
			for(;k+index<n;k+=index){
				Arrays.sort(b,k,k+index);
			}
			Arrays.sort(b,k,n);
			
		}
		for(int k=0;k<n;k++){
			System.out.print(k==0?b[0]:" "+b[k]);
		}
	}

}

# -*- coding:utf-8 -*-

N = raw_input()
lst_1 = map(int, raw_input().split()) #UnSorted
lst_2 = map(int, raw_input().split()) #Sorted

tc1 = [1, 2, 3, 7, 8, 5, 9, 4, 6, 0]
tc2 = [1, 3, 2, 8, 5, 7, 4, 9, 0, 6]
tc3 = [7,8,9,10,2,3,4,5]
tc4 = [5,2]
#---------------------------------------

def isSorted(inlst,i,j):
	# Check inlst[i,j)
	out = True
	# print "isSorted(inlst,%d,%d)"%(i,j)
	for i in range(i,min(j-1, len(inlst)-1)):
		if inlst[i] > inlst[i+1]:
			out = False
			break
	return out

# print isSorted([1,2,3,4],0,4)

def findUnsorted(inlst, i):
	# Check inlst[i:]'s first unsorted element's index.
	# If all sorted, return len(lst)
	allSorted = True
	for i in range(i,len(inlst)-1):
		if inlst[i] > inlst[i+1]:
			allSorted = False
			return i+1
	if allSorted:
		return len(inlst)


# ------------------List Generator---------------------
def mergeState(inlst):
	mergeStep = [pow(2,i) for i in range(1, len(inlst)) if pow(2,i) <= len(inlst)]
	mergeState = [[isSorted(inlst,i,i+step) for i in range(0,len(inlst),step)] for step in mergeStep]
	return mergeState

def nextMerge(inlst, num):
	lstToMerge = [inlst[i:min(i+pow(2,num),len(inlst))] for i in range(0,len(inlst),pow(2,num))]
	out = []
	for lst in lstToMerge:
		out = out + sorted(lst)
	return out

def allTrue(inlst):
	return not (False in inlst)

def isMerge(inlst):
	# inlst: type of mergeState
	# if idx == 0, it's not mergeSort
	for idx, lst in enumerate(inlst):
		if allTrue(lst):
			pass
		else:
			return idx

def isMerge_capped(inlst):
	return isMerge(mergeState(inlst))

# ------------------List Generator---------------------

# print isMerge_capped(tc1)
# print isMerge_capped(tc2)

def inSert(inlst, hi):
	# Aim to insert[hi]
	inlst[0:hi+1] = sorted(inlst[0:hi+1])
	return inlst

if isMerge_capped(lst_2) == 0:
	print "Insertion Sort"
	print str(inSert(lst_2, findUnsorted(lst_2,0))).strip('[]').replace(', ', ' ')
else:
	print "Merge Sort"
	print str(nextMerge(lst_2, isMerge_capped(lst_2)+1)).strip('[]').replace(', ', ' ')

N = int(input())
m = list(map(int, input().split()))
n = list(map(int, input().split()))
M = m[:]
flag = 1
step = 1
for i in range(1, N):
    t = i
    if n == m:
        print('Insertion Sort')
        while t >= 1:
            if m[t] < m[t-1]:
                m[t], m[t - 1] = m[t-1], m[t]
                t -= 1
            else:
                break
        for i in m:
            print(i, end=' ')
        break
    while t >= 1:
        if m[t] < m[t-1]:
            m[t], m[t-1] = m[t-1], m[t]
            t -= 1
        else:
            break
    if i == N - 1:
        print('Merge Sort')
        while flag:
            flag = 0
            for j in range(0, N):
                if n[j] != M[j]:
                    flag = 1
                    break
            step *= 2
            for z in range(0, N, step):
                M[z: min(z+step, N)] = sorted(M[z: min(z+step, N)])
        for i in M:
            print(i, end=' ')
        break

#include <iostream>
#include <memory.h>

using namespace std;

const int maxn = 100;

int orgin[maxn] = {0};
int target[maxn] = {0};
int ins[maxn] = {0};
int mer[maxn] = {0};

bool checkSame(int *a1, int *a2, int n) {
    for (int i = 0; i < n; i++) {
        if (a1[i] != a2[i]) {
            return false;
        }
    }
    return true;
}

void printArray(int *a, int n) {
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            cout << a[i];
        } else {
            cout << " " << a[i];
        }
    }
}


bool checkInsert(int n) {
    int index = 0;
    bool finish = false;
    while(index < n) {
        int cur = ins[index];
        int i;
        for (i = 0; i < index; i++) {
            if (ins[i] > cur) {
                for (int j = index - 1; j >= i; j--) {
                    ins[j + 1] = ins[j];
                }
                ins[i] = cur;
                break;
            }
        }
        if (i == index) {
            index++;
            continue;
        }

        if (finish) {
            cout << "Insertion Sort" << endl;
            printArray(ins, n);
            return true;
        }

        if (checkSame(ins, target, n)) {
            finish = true;
        }

        index++;
    }
    return false;
}

void Merge(int *r, int *r1, int s, int m, int t) {
    int i = s;
    int j = m + 1;
    int k = s;
    while (i <= m && j <= t) {
        if (r[i] < r[j]) {
            r1[k++] = r[i++];
        } else {
            r1[k++] = r[j++];
        }
    }
    if (i <= m) {
        while (i <= m) {
            r1[k++] = r[i++];
        }
    }

    if (j <= t) {
        while (j <= t) {
            r1[k++] = r[j++];
        }
    }
}

void MergePass(int *r, int *r1, int n, int h) {
    int i = 0;
    while (i + 2 * h - 1 < n) {
        Merge(r, r1, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (i + h < n) {
        Merge(r, r1, i, i + h - 1, n);
    } else {
        for (int j = i; j < n; j++) {
            r1[j] = r[j];
        }
    }
}

bool checkMerge(int n, int *r) {
    int h = 1;
    int r1[maxn] = {0};
    bool finish = false;
    while (h < n) {
        MergePass(r, r1, n, h);
        h = 2 * h;

        for (int i = 0; i < n; i++) {
            r[i] = r1[i];
        }

        memset(r1, 0, n * sizeof(int));

        if (finish) {
            cout << "Merge Sort" << endl;
            printArray(r, n);
            return true;
        }

        if (checkSame(r, target, n)) {
            finish = true;
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        orgin[i] = data;
        ins[i] = data;
        mer[i] = data;
    }

    for (int i = 0; i < n; i++) {
        cin >> target[i];
    }

    checkInsert(n);
    checkMerge(n, mer);
    return 0;
}

import java.util.*;

public class Main{
	static int swi = 1;
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int k = 0;
        boolean flag = true;
        int [] arr = new int [n];
        int [] sortArr = new int [n];
        for(int i = 0; i < n; i++)
        	arr[i] = sc.nextInt();
        for(int i = 0; i < n; i++)
        	sortArr[i] = sc.nextInt();
        for(int i = 1; i < n; i++){
        	if(sortArr[i - 1] > sortArr[i]){
        		k = i;
        		break;
        	}
        }
        for(int i = k; i < n; i++){
        	if(arr[i] != sortArr[i]){
        		flag = false;
        		break;
        	}
        }
        if(flag)
        	insertionSort(sortArr, k);
        else{ 
        	int [] t = new int[arr.length];
        	for(int i = 1; i < n && swi != 0; i <<= 1, i++,swi++){
        		for(int j = 0; j < n; j += i + 1){
        			if(j + i > n)
        				sort(arr,j, n - 1,t);
        			else
        				sort(arr,j, j + i,t);
        		}
        		boolean f = check(arr, sortArr);
         		if(f) swi = -2;
        	}
        	System.out.println("Merge Sort");
        	for(int i = 0; i < arr.length - 1; i++)
    			System.out.print(arr[i] + " ");
    		System.out.print(arr[sortArr.length - 1]);
        }
    }
   private static boolean check(int[] arr, int[] sortArr) {
	   for(int k = 0 ;k < sortArr.length; k++){
			if(arr[k] != sortArr[k])return false;
		}
		return true;
	}
private static void sort(int[] arr, int start, int end, int[] temp) {
	    int i = start, j = (start + end) / 2 + 1;
		int m = (start + end) / 2, n = end;
		int k = 0;
		while (i <= m && j <= n)
		{
			if (arr[i] <= arr[j])
				temp[k++] = arr[i++];
			else
				temp[k++] = arr[j++];
		}
		
		while (i <= m)
			temp[k++] = arr[i++];
		
		while (j <= n)
			temp[k++] = arr[j++];
		
		for (i = 0; i < k; i++)
			arr[start + i] = temp[i];

		
	}
	private static void insertionSort(int[] sortArr, int k) {
		int v = sortArr[k];
		int i = k;
		while(i > 0){
			if(sortArr[i - 1] > v) sortArr[i] = sortArr[i - 1];
			else break;
			i--;
		}
		sortArr[i] = v;
		System.out.println("Insertion Sort");
		for(i = 0; i < sortArr.length - 1; i++)
			System.out.print(sortArr[i] + " ");
		System.out.print(sortArr[sortArr.length - 1]);
	}
}

#include<stdio.h>
#include<stdlib.h>
void printList(int list[],int len){
	int i;
	for(i=0;i<len-1;i++)
	    printf("%d ",list[i]);
    printf("%d\n",list[i]);
}
int	compareVec(int list1[],int list2[], int len){
	for(int i=0;i<len;i++)
	    if(list1[i]!=list2[i]) return 0;
    return 1;
} 
void MergeSortedVec(int list[],int low, int median, int high){
	int tempList[high-low+1];
	int i=low,j=median+1,k=0;
	while(i<=median && j<=high){
		 if(list[i]>list[j])
 			tempList[k++] = list[j++];
	     else
	        tempList[k++] = list[i++];}
    if(i<=median)
       while(i<=median)
	      tempList[k++] = list[i++];
    if(j<=high)
       while(j<=high)
          tempList[k++] = list[j++];
    for(i=low,k=0;i<=high;i++,k++)
          list[i] = tempList[k];          
}
int MergeSort(int list[],int len, int referVec[]){
	int low,subLen,i;
	subLen=1;
	i=0;
	while(subLen<len){
          low=0;
		  while(low+subLen<=len){
  			  if(low+2*subLen<len){
  			  	MergeSortedVec(list,low,low+subLen-1,low+2*subLen-1);
  			  }else{
  			  	MergeSortedVec(list,low,low+subLen-1,len-1);
  			  }
  			  low+=2*subLen;
  		   }
  		   if(i==0){
  		     if(compareVec(list,referVec,len)) i=1;}
	          else{
	       	     if(compareVec(list,referVec,len)==0){
		         printf("Merge Sort\n");
                         printList(list,len);
			 return 1;}
		   }	         
		   subLen*=2;		
	}
	return 0;
}
int insertSort(int list[],int len, int referVec[]){
	 int temp,i,j,k;
	 k=0;
	 for(i=1;i<len;i++){
 		temp=list[i];
 		for(j=i-1;list[j]>temp && j>=0;j--)
		 	list[j+1]=list[j];
	 	list[j+1]=temp;
	 	if(k==0){
	 	   if(compareVec(list,referVec,len)) k=1;}
        else{
        	if(compareVec(list,referVec,len)==0){
		         printf("Insertion Sort\n");
                 printList(list,len);
			     return 1;}
        }
 	}
 	return 0;
}

int main(){
	int *list1,*list2,*templist,i,n;
	scanf("%d",&n);
	list1=(int *)malloc(n*sizeof(int));
	list2=(int *)malloc(n*sizeof(int));
	templist=(int *)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
	   {scanf("%d",list1+i);templist[i]=list1[i];}
        for(i=0;i<n;i++)
           scanf("%d",list2+i);
        if(MergeSort(list1,n,list2)) return 0;
	if(insertSort(templist,n,list2)) return 0; 
        printf("no sort find!\n"); 
}

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
int main()
{
	int n,i,j,k=1,c,pan=1,is=0,q;
	int a[100],b[100],m[100];
//	fstream inFile;
//	inFile.open("data1035.txt",ios::in);
//	inFile>>n;
	cin>>n;
	for(i=0;i<n;i++)
	{
//		inFile>>a[i];
		cin>>a[i];
		m[i]=a[i];
		//		cout<<a[i]<<" ";
	}
	//	for(i=0;i<n;i++)
	
	for(i=0;i<n;i++)
	{
	//	inFile>>b[i];
		cin>>b[i];
		//		cout<<b[i]<<" ";
	}
	for(;k<n;)
	{
		k=k*2;
		pan=1;
		for(j=0;j<n;j=j+k)
		{
			if(j+k<=n)
				sort(a+j,a+j+k);
			else
				sort(a+j,a+n);
		}
		for(c=0;c<n;c++)
		{
			if(a[c]!=b[c])
			{
				pan=0;
				break;
			}
		}
		if(pan==1)
		{
			is=1;
			k=k*2;
			for(j=0;j<n;j=j+k)
			{
				if(j+k<=n)
					sort(a+j,a+j+k);
				else
					sort(a+j,a+n);
			}
			printf("Merge Sort\n");
			for(c=0;c<n;c++)
			{
				cout<<a[c];
				if(c!=n-1)
					cout<<" ";
			}
			break;
		}
	}
	if(is==0)
	{
		
		for(q=1;q<n;q++)
		{
			pan=1;
			sort(m,m+q);
			for(i=0;i<n;i++)
				if(m[i]!=b[i])
					pan=0;
				if(pan==1)
				{
					cout<<"Insertion Sort"<<endl;
					sort(m,m+q+1);
					for(i=0;i<n;i++)
					{
						cout<<m[i];
						if(i!=n-1)
							cout<<" ";
					}
				}
				if(pan==1)
				{
				//	q=n+1;
					break;
				}
		}
	}
//	cout<<endl;
	return 0;
}
对应输出应该为:
Insertion Sort
1 2 3 4 5 7 8 9 6 0

你的输出为:

Insertion Sort
1 2 3 5 7 8 9 4 6 0
Q
这个错误应该怎么改

#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[101] = { 0 };
int brr[101] = { 0 };
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i){
scanf("%d", &arr[i]); 
}
for (int i = 0; i < n; ++i){
scanf("%d", &brr[i]);
}
int i = 1;
while (i < n&&brr[i] >= brr[i - 1]){
++i;
}
int j = i;
while (i < n&&arr[i]==brr[i]){
++i;
}
if (i == n){
printf("Insertion Sort\n");
int tmp = brr[j];
while (j>=0){
if (tmp < brr[j - 1]){
brr[j] = brr[j - 1];
--j;
}
else{
break;
}
}
if (j != -1){
brr[j] = tmp;
}
else{
brr[0] = tmp;
}
for (int k = 0; k < n; k++){
printf("%d%c", brr[k], k == n - 1 ? '\n' : ' ');
}
}
else{
printf("Merge Sort\n");
int i = 1;
int *start;
int *end;
while (true){
bool equal = true;
for (int k = n-1; k >= 0; --k){
if (arr[k] != brr[k]){
equal = false;
break;
}
}
if (equal){
break;
}
    start = &arr[0];
end = &arr[n - 1];
while (start < end){
sort(start, min(start + i, end));
start += i;
}
i <<= 1;
}
start = &arr[0];
end = &arr[n - 1];
while (start < end){
sort(start, min(start + i, end));
start += i;
}
for (int i = 0; i < n; ++i){
printf("%d%c", arr[i], i == n - 1 ? '\n' : ' ');
}
}
system("pause");
return 0;
}

#include <stdio.h>
#include <stdlib.h>
 
//int insertion_sort(int*, int*, int);
int cmp(const void* a, const void* b)
{
    return (*(int *)a - *(int *)b);
}
 
void merge_sort(int*, int*, int);
 
int main()
{
    int a[100] = {0}, b[100] = {0};
    int n, i, j;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", a + i);
    for(i = 0; i < n; i++)
        scanf("%d", b + i);
    for(i = 0; i < n - 1 && b[i] < b[i + 1]; i++);//排除掉有序的部分
    for(j = i + 1; j < n && a[j] == b[j]; j++);   //判断剩下的部分是否与原部分相同
    if(j == n)
    {
        printf("Insertion Sort\n");
        qsort(a, i + 2, sizeof(int), cmp);
    }
    else
    {
        printf("Merge Sort\n");
        merge_sort(a, b, n);
    }
    for(i = 0; i < n; i++)
    {
        if(i == 0)
            printf("%d", a[i]);
        else
            printf(" %d", a[i]);
    }
    printf("\n");
 
    return 0;
}
 
void merge_sort(int a[], int b[], int n)
{
    int step = 1, flag = 1, tmp, i;
    while(flag)
    {
        flag = 0;
        for(i = 0; i < n; i++)
        {
            if(a[i] != b[i])
                flag = 1;
        }
        step *= 2;
        for(i = 0; i < n; i += step)
        {
            if(i + step > n)//若归并时step的范围超出数组有值的部分，则调整step
            {
                tmp = step;
                step = n - i;
            }
            qsort(a + i, step, sizeof(int), cmp);
            if(i + tmp > n)//将step恢复至原来的值
            {
                step = tmp;
            }
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
int main(){
    int N, origin[100], halfsort[100], i, j, length;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", origin + i);
    for(int i = 0; i < N; i++) scanf("%d", halfsort + i);
    /* 如果是插入排序，则返回排序长度，如果是，则返回零 */
    for(i = 0; i < N - 1 && halfsort[i] <= halfsort[i + 1]; i++) ;
    for(length = ++i; i < N && halfsort[i] == origin[i]; i++) ;
    length = i == N ? length + 1 : 0;
    if(length){/* 插入排序 */
        puts("Insertion Sort");
        qsort(origin, length, sizeof(int), comp);
    }else{/* 归并排序，对原始数组进行操作 */
        put***erge Sort");
        for(length = 1, i = 0; i < N && length <= N; length *= 2){
            for(i = 0; i < N && origin[i] == halfsort[i]; i++) ;
            for(j = 0; j < N / length; j++)
                qsort(origin + j * length, length, sizeof(int), comp);
            qsort(origin + j * length, N % length, sizeof(int), comp);
        }
    }
    for(int i = 0; i < N; i++)
        printf("%d%c", origin[i], i == N - 1 ? '\n' : ' ');
    return 0;
}

为啥PAT后面几个测试点过不去

迭代归并排序,自己使用步长1,2,4,8.....解决

# -*- coding : utf-8 -*-

def merge_sort(l,l2):
    i=2
    count=0
    while i<=len(l):
        result=[]
        for j in range(int(len(l)/i)):
            result+=merge(l[j*i:j*i+int(i/2)],l[j*i+int(i/2):j*i+i])
        result+=l[int(len(l)/i)*i:]
        l=result.copy()
        if result==l2:
            count=i*2
        if i==count:
            break
        i*=2
    return result
def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left
    result += right
    return result


_ = input()
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
# insert
insert = l1.copy()
merge_l = l1.copy()
insert_flag = False
count=0
for i in range(1, len(insert)):
    j = i - 1
    temp = insert[i]
    while j >= 0 and insert[j] > temp:
        insert[j + 1] = insert[j]
        j -= 1
    insert[j + 1] = temp
    if l2 == insert:
        insert_flag = True
        count=i+1
    if i==count:
        break

if insert_flag:
    print('Insertion Sort')
    print(' '.join([str(i) for i in insert]))
else:
    print('Merge Sort')
    merge = merge_sort(merge_l,l2)
    print(' '.join([str(i) for i in merge]))

	#pragma warning(disable:4996)



	#include <iostream>



	#include<algorithm>



	#include<string>



	#include<vector>



	usingnamespacestd;



	 



	vector<int> merge_sort(vector<int> res, intiter) {



	    intn = res.size(),i = iter;



	    for(intj = 0; j < n; ) {



	        if(pow(2, i) + j <= n) sort(res.begin() + j, res.begin() + j + pow(2, i));



	        if(j + pow(2, i) > n) {



	            sort(res.begin() + j, res.end()); break;



	        }



	        elsej += pow(2, i);



	    }



	    returnres;



	}



	 



	vector<int> operator+(vector<int>& vec1, vector<int>& vec2) {



	    intn = vec1.size() + vec2.size();



	    vector<int> res(n, 0);



	    for(inti = 0; i < n; i++) {



	        if(i < vec1.size()) res[i] = vec1[i];



	        elseres[i] = vec2[i - vec1.size()];



	    }



	    returnres;



	}



	 



	voidinsertion_sort(vector<int>& res, inttarget) {



	    vector<int> result;



	    if(res.size() == 1) {



	        if(target >= res[0]) { res.insert(res.begin()+1,1,target); }



	        else{ res.insert(res.begin(),1,target); }



	    }



	    else{//size>=2



	        boolflag = true;



	        for(inti = 0; i < res.size(); i++) {



	            if(res[i] >= target) {



	                flag = false;



	                res.insert(res.begin() + i, 1, target);



	                break;



	            }



	        }



	        if(flag) res.push_back(target);



	    }



	}



	 



	string vector_to_string(vector<int> res) {



	    string str = "";



	    for(auto&x : res) { str += to_string(x); }



	    returnstr;



	}



	intmain()



	{



	    intn, iter = 0, i = 0, j = 0, t; scanf("%d\n", &n);



	    vector<int> res(n, 0);string test = "";



	    while(pow(2, iter) < n) { iter++;}



	    while(i < n) { cin >> res[i]; i++; }



	    vector<int> res1; res1.assign(res.begin(), res.end());



	    while(j < n) { cin >> t; test += to_string(t); j++; }



	    //cout << test << endl;



	    for(inti = 1; i < iter; i++) { // 归并排序



	        string result = "";



	        res = merge_sort(res, i);



	        result = vector_to_string(res);



	        //for (auto&x : res) { result += to_string(x); }



	        //cout << result << endl;



	        if(test == result) {



	            cout << "Merge Sort"<< endl;



	            res = merge_sort(res, i + 1);



	            for(auto&x : res) cout << x << " ";



	            cin.get(); cin.get();



	            return0;



	        }



	    }



	    cout << "Insertion Sort"<< endl;



	    vector<int> res2, temp;



	    res2.push_back(res1[0]);



	    for(inti = 1; i < n; i++) { // 选择排序，n-1轮迭代



	        string result_choose = "";



	        insertion_sort(res2, res1[i]); //前面有序部分



	        if(res2[res2.size() - 1] <= res1[res2.size()]) { //前面有序时若待插入数，不影响子序列的有序性，直接插入该数，指针后移。



	            res2.push_back(res1[res2.size()]);



	            i++;



	        }



	        temp.assign(res1.begin() + i+1, res1.end()); //后面乱序部分



	        res1 = res2 + temp; //排序后得结果



	        result_choose = vector_to_string(res1);



	        if(result_choose == test) {



	            insertion_sort(res2, res1[i + 1]);



	            temp.assign(res1.begin() + i + 2, res1.end()); //后面乱序部分



	            res1 = res2 + temp; //排序后得结果



	            for(auto&x : res1) cout << x << " ";



	            cin.get(); cin.get();



	            return0;



	        }



	        //cout << result_choose << endl;



	    }



	    cin.get(); cin.get(); return0;



	}