Insert or Merge (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;
}

/*先判断是否是归并排序
    *枚举间隔，看间隔内的数是否是有序且和原序列的数相同；
    *只有此间隔下所有集合有序且与原数组元素相符才能判断是归并；
    *若是归并，则扩大间隔，每个间隔内排序即得下步；
    *若是插入，则直接寻址不符合有序的一个元素向前插入到适合位置即可。
*/
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e2 + 66 ;
int n ;
map<int,int>mp;
int a[AX];
int b[AX];
int ans ; 
bool check_sort( int l , int r ){
	int ans = 0 ;
	mp.clear() ; 
	for( int i = l ; i <= r ; i++ ){
		mp[a[i]] ++ ;
	}
	for( int i = l ; i < r ; i++ ){
		mp[b[i]] -- ; 
		if( b[i+1] < b[i] ) return false ;
	}mp[b[r]] -- ;
	for( auto i : mp ){
		if( i.second ) return false ; 
	}
	return true ; 
}
int check_merge(){
	for( int d = 2 ; d <= n ; d *= 2 ){
		int f = 1 ; 
		for( int i = 0 ; i < n ; i += d ){
			if( !check_sort( i , min( n - 1 , i + d - 1 ) ) ){
				f = 0 ; break ;  
			}
		}
		if( f ) { ans = d ; return true ; }
	}
	return false ; 
}
int main() {
	scanf("%d",&n);
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%d",&a[i]);
	}
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%d",&b[i]);
	}
	if( check_merge()  ) {
		printf("Merge Sort\n");
		ans *= 2 ; 
		for( int i = 0 ; i < n ; i += ans ){
			sort( b + i , b + min( n , i + ans ) );
		}
	}else{
		printf("Insertion Sort\n");
		for( int i = 1 ; i < n ; i++ ){
			if( b[i] < b[i-1] ){
				while(b[i] < b[i-1]){
					swap( b[i] , b[i-1] );
					i -- ; 
				}
				break ;
			}
		}
	}
	for( int i = 0 ; i < n ; i++ ){
		printf("%d",b[i]);
		if( i != n - 1 ) printf(" ");
	}
	return 0 ;
}

通不过的一例解决办法用😅做标记帮大家标了出来。
#include<bits/stdc++.h>
using namespace std;

const int Max=110;
int a[Max],b[Max],c[Max];
int n;

bool cmp(int* b,int* c) {
	for(int i=0; i<n; i++) {
		if(b[i]!=c[i]) {
			return 0;
		}
	}
	return 1;
}

void Printf(int* b) {
	for(int i=0; i<n; i++) {
		cout<<b[i];
		if(i<n-1) cout<<" ";
	}
	cout<<endl;
	return ;
}

bool Insertsort() {
	bool flag=0;
	for(int i=1; i<n; i++) {
		if(i!=1&&cmp(b,c)) {
			flag=1;
		}
		int temp=b[i],j=i;
		while(j>0&&b[j-1]>temp) {
			b[j]=b[j-1];
			j--;
		}
		b[j]=temp;
      😅if(b[i]==temp){
            continue;
        }😅
		if(flag) {
			return 1;
		}
	}
	return 0;
}

void Mergesort() {
	bool flag=0;
	for(int step=2; step<=n; step*=2) {
		if(step!=2&&cmp(a,c)) {
			flag=1;
		}
		for(int i=0; i<n; i+=step) {
			sort(a+i,a+min(i+step,n));
		}
		if(flag) {
			Printf(a);
			return ;
		}
	}
}

int main() {
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a[i];
		b[i]=a[i];
	}
	for(int i=0; i<n; i++) {
		cin>>c[i];
	}
	if(Insertsort()) {
		cout<<"Insertion Sort"<<endl;
		Printf(b);
	} else {
		cout<<"Merge Sort"<<endl;
		Mergesort();
	}
	return 0;
}

a,i = int(input()),0
b = list(map(int,input().split()))
c = list(map(int,input().split()))
while c[i] <= c[i + 1]:
    i += 1
if c[i + 1:] == b[i + 1:]:
    print("Insertion Sort")
    print(' '.join(map(str,sorted(c[:i + 2]) + c[i + 2:])))
else:
    print("Merge Sort")
    d,j = c.copy(),2
    while d == c:
        for i in range(a // j + 2):
            c[i * j:(i + 1) * j] = sorted(c[i * j:(i + 1) * j])
        j *= 2
    print(' '.join(map(str,c)))

#include <bits/stdc++.h>
using namespace std;
constintmaxn = 1e2 + 5;
vector<int> init;
vector<int> statu;
vector<int> insert;
vector<int> merges;
inta[maxn];
bool ins() {
    bool flag = false;
    inti;
    insert = init;
    for(i = 1; i < insert.size(); ++i) {
        intval = insert[i];
        insert.erase(insert.begin() + i);
        auto p = lower_bound(insert.begin(), insert.begin() + i, val);
        insert.insert(p, val);
        if(insert == statu) {
            flag = true;
            break;
        }
    }
    if(flag) {
        cout << "Insertion Sort"<< endl;
        while(insert == statu) {
            i++;
            intval = insert[i];
            insert.erase(insert.begin() + i);
            auto p = lower_bound(insert.begin(), insert.begin() + i, val);
            insert.insert(p, val);
        }
        for(inti = 0; i < insert.size(); ++i) {
            if(i)
                cout << " ";
            cout << insert[i];
        }
        cout << endl;
        returntrue;   
    }
    returnfalse;
}
voiddomerge(intlef, intmid, intrig) {
    intl = lef, r = mid;
    intpos = lef;
    while(l < mid && r <= rig) {
        if(merges[l] < merges[r])
            a[pos++] = merges[l++];
        else
            a[pos++] = merges[r++];
    }
    while(l < mid)
        a[pos++] = merges[l++];
    while(r <= rig)
        a[pos++] = merges[r++];
    for(inti = lef; i <= rig; ++i)
        merges[i] = a[i];
}
voidmer() {
    merges = init;
    intsz = 1;
    for(sz = 1; sz < merges.size(); sz *= 2) {
        inti;
        for(i = 0; i + sz * 2- 1< merges.size(); i += sz * 2) {
            domerge(i, i + sz, i + sz * 2- 1);
        }
        if(i + sz < merges.size())
            domerge(i, i + sz, merges.size() - 1);
        if(merges == statu) {
            break;
        }
    }
    cout << "Merge Sort"<< endl;
    sz *= 2;
    inti;
    for(i = 0; i + sz * 2- 1< merges.size(); i += sz * 2) {
        domerge(i, i + sz, i + sz * 2- 1);
    }
    if(i + sz < merges.size())
        domerge(i, i + sz, merges.size() - 1);
    for(inti = 0; i < merges.size(); ++i) {
        if(i)
            cout << " ";
        cout << merges[i];
    }
    cout << endl;
}
intmain() {
    std::ios::sync_with_stdio(false);
    intn;
    cin >> n;
    init.resize(n);
    statu.resize(n);
    for(inti = 0; i < n; ++i)
        cin >> init[i];
    for(inti = 0; i < n; ++i)
        cin >> statu[i];
    if(!ins()) {
        mer();
    }
    return0;
}

def merge(a):
    if len(a)==1:
        return
    con = len(a)//2
    temp =[]
    telst = []
    for i in range(0,con):
        tem = a[2*i]+a[2*i+1]
        tem.sort()
        telst.append(tem)
        temp = temp+tem
    for i in a[2*(con-1)+2:]:
        temp = temp+i
    if a[2*(con-1)+2:]:
        telst.extend(a[2*(con-1)+2:])
    merger.append(temp)
    merge(telst)

def insert(a):
    tem = []
    for i in range(0,len(a)):
        tem = tem + [a[i]]
        tem.sort()
        if tem+a[i+1:] not in inser:
            inser.append(tem+a[i+1:]) 
inser,merger = [],[]
n = input()
n = int(n)
lst = list(map(int,input().split()))
b = list(map(int,input().split()))
insert(lst)
merge([[i] for i in lst])
if b in inser:
    print("Insertion Sort")
    print(' '.join(map(str,inser[inser.index(b)+1])))
else:
    print("Merge Sort")
    print(' '.join(map(str,merger[merger.index(b)+1])))

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 110
int n,original[maxn],target[maxn];
bool merge_sort(int a[]){
	int num=2;
	bool flag=false;
	while(1){
		int left=0;
		for(;left<n;left+=num){
			int end=left+num;
			end=end>n?n:end;
			sort(a+left,a+end);
		}
		if(flag){
			printf("Merge Sort\n");
			for(int i=0;i<n;i++){
				printf("%d",a[i]);
				if(i<n-1)printf(" ");
			}
			break;
		}
		int k;
		for(k=0;k<n;k++)if(a[k]!=target[k]){
			break;
		}
		if(k>=n)flag=true;
		if(num>n)break;
		num*=2;
	}
	return flag;
}
void insertion_sort(int b[]){
	bool flag=false;
	for(int num=2;num<=n;num++){//num从2开始，否则测试点2的数据通不过
		sort(b,b+num);
		if(flag){
			printf("Insertion Sort\n");
			for(int i=0;i<n;i++){
				printf("%d",b[i]);
				if(i<n-1)printf(" ");
			}
			break;
		}
		int k;
		for(k=0;k<n;k++)if(b[k]!=target[k]){
			break;
		}
		if(k>=n)flag=true;
	}
}
int main(){
	//freopen("A1089.txt","r",stdin);
	int a[maxn],b[maxn];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&original[i]);
		a[i]=original[i];
		b[i]=original[i];
	}
	for(int i=0;i<n;i++)scanf("%d",&target[i]);
	if(merge_sort(a))return 0;
	insertion_sort(b);
	return 0;
}

public class Main{
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int[] pre = new int[n];
		int[] cur = new int[n];
		for(int i=0; i<n; ++i)
			pre[i] = s.nextInt();
		for(int i=0; i<n; ++i)
			cur[i] = s.nextInt();
		int index =0;
		String str = "Insertion";
		for(int i=1; i<n; ++i){
			if(cur[i-1]>cur[i]){
				index = i;
			for(;i<n; ++i){
				if(pre[i]!=cur[i]){
					str = "Merge";
				}
			}
			}
			if("Merge".equals(str))
				break;			
		}
		if("Insertion".equals(str)){
			System.out.println(str+" Sort");
			int num = cur[index];
			int flag =1;
			for(int i=index-1; i>-1; --i){
				if(num>cur[i]){
					cur[i+1] = num;
					flag = 0;
					break;
				}else{
					cur[i+1] = cur[i];
				}
			}
			if(flag!=0){
				cur[0] = num;
			}
		}else{
			System.out.println("Merge Sort");
			index = index*2;
			for(int i=0; i<n; i+=index){
				int end = i+index>n ? n :(i+index);
				Arrays.sort(cur,i,end);
			}
		}
		for(int i=0; i<n; ++i){
			if(i==n-1)
				System.out.print(cur[i]);
			else
				System.out.print(cur[i]+" ");
		}
			
	}
}

#include <stdio.h>
#include <algorithm>

using namespace std;

int buf1[110];
int buf2[110];
int temp[110];

bool IsSame(int a[],int b[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i] != b[i]) return false;
	}
	
	return true;
}

int InsertSort(int a[],int n)
{
	int i,j,tmp;
	int flag = 0;
	for(i=1;i<n;i++)
	{
		if(a[i] < a[i-1])
		{
			if(IsSame(a,buf2,n))
			{
				flag = 1;
			}
			
			tmp = a[i];
			for(j=i-1;a[j]>tmp && j>=0;j--)
			{
				a[j+1] = a[j];
			}
			
			a[j+1] = tmp;
		}
		
		if(flag == 1)
		{
			return 1; //is insertsort
		}
	}
	
	return 0;
}

void output(int a[],int n)
{
	int i;
	for(i=0;i<n;i++)
    {
    	printf("%d",a[i]);
    	if(i != n-1)
    	{
    		printf(" ");
    	}
    }
    printf("\n");
}

void MergeSort(int a[],int n)
{
	int step,i,j;
	int flag = 0;
	for(step=2;step/2<=n;step*=2)
	{
		if(IsSame(a,buf2,n))
		{
			flag = 1;
		}
		for(i=0;i<n;i+=step)
		{
			sort(a+i,a+min(i+step,n));
		}
		
		
		if(flag == 1) return;
	}
}

int main()
{
#if 0 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);    
#endif    

    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    	scanf("%d",&buf1[i]);
    	temp[i] = buf1[i];
    }
    
    for(i=0;i<n;i++)
    {
    	scanf("%d",&buf2[i]);
    }
    
    if(InsertSort(buf1,n) == 1)
	{
		printf("Insertion Sort\n");
		output(buf1,n);
	}
	else //merge sort
	{
		MergeSort(temp,n);
		printf("Merge Sort\n");
		output(temp,n);
	}

    return 0;
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <string>
#include <set>
#include <string>
#include <functional>
#include <algorithm>
#include <assert.h>
#include <fstream>
#include <map>
#include <stack>

using namespace std;

int get_i(int x)
{
	int t = 32;
	while (x<0)
	{
		t--; x <<= 1;
	}
	return t;
}
typedef vector<int>::iterator it;
void merge_sort(it b, it e, int n)
{
	while (true)
	{
		if (e - b < n) break;
		it p1 = b, p2 = b + n;
		int i = 0;
		auto l = e;
		if (e - b > n + n)
			l = b + n + n;

		inplace_merge(b, b + n, l);
		b = l;
	}
}
int main()
{
#ifdef _DEBUG
	freopen("data.txt", "r", stdin);
#endif // _DEBUG
	int n;
	cin >> n;
	vector<int> src(n), s(n);
	for (int i = 0; i < n; i++)
		cin >> src[i];
	for (int i = 0; i < n; i++)
		cin >> s[i];
	int j = n - 1;
	for (; j>0 && src[j] == s[j]; j--);


	map<int, int> index;
	int r;
	unsigned int c;
	if (j < n - 1)
	{
		int i = 1;
		for (; i<n&&s[i] >= s[i - 1]; i++);
		assert(i < n);
		vector<int> a(src.begin() + i, src.end()),
			b(s.begin() + i, s.end());
		if (a == b)
		{
			cout << "Insertion Sort" << endl;
			sort(s.begin(), s.begin() + i + 1);
			goto PRINT;
		}
	}


	for (int i = 0; i < n; i++)
		index[src[i]] = i;

	c = 0;
	for (int i = 0; i < n; i++)
	{
		unsigned int  a = (i), b = (index[s[i]]);
		c = max((a^b), c);
	}
	r = get_i(static_cast<unsigned int> (~c));
	merge_sort(s.begin(), s.end(), pow(2, r));
	cout << "Merge Sort" << endl;

PRINT:
	int i = 0;
	for (; i < n - 1; i++)
	{
		cout << s[i] << " ";
	}
	cout << s[i] << endl;
	return 0;
}

	#include<stdio.h>



	#include<algorithm>



	#include<vector>



	using namespace std;



	intmain(){



	    intN,i,j;



	//  freopen("input.txt","r",stdin);



	    while(scanf("%d",&N)!=EOF){



	        vector<int> a1(N),a2(N);



	        for(i=0;i<N;i++) scanf("%d",&a1[i]);



	        for(i=0;i<N;i++) scanf("%d",&a2[i]);



	        for(i=1;i<a2.size();i++)



	            if(a2[i]-a2[i-1]<0)



	                break;



	        intflag=1;



	        for(j=i;j<a2.size();j++)



	            if(a1[j]!=a2[j]){



	                flag=0;



	                break;



	            }



	            if(flag==1){



	                printf("Insertion Sort\n");



	                sort(a2.begin(),a2.begin()+i+1);



	                for(i=0;i<a2.size()-1;i++)



	                    printf("%d ",a2[i]);



	                printf("%d\n",a2[i]);



	            }else{



	                printf("Merge Sort\n");



	                if(i%2!=0) i--;



	                i*=2;



	                for(j=0;j+i<=a2.size();j+=i) sort(a2.begin()+j,a2.begin()+j+i);



	                for(i=0;i<a2.size()-1;i++)



	                    printf("%d ",a2[i]);



	                printf("%d\n",a2[i]);



	            }



	    }



	}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    // 读入数据
    int N; cin >> N;
    vector<int> startState(N), midState(N);
    for(int i=0; i<N; i++) {
        cin >> startState[i];
    }
    for(int i=0; i<N; i++) {
        cin >> midState[i];
    }

    // 判断哪种排序
    bool isInsertion = true; int idx = N-1;
    while(midState[idx]==startState[idx]) {idx--;}
    while(idx>0) {
        if(midState[idx] < midState[idx-1]) {
            isInsertion = false; break;
        }
        idx--;
    }

    // 获取下一状态
    if(isInsertion) {
        for(idx=1; idx<=N; idx++) {
            sort(startState.begin(), startState.begin()+idx);
            if(startState == midState) {break;}
        }
        for(idx++; idx<=N; idx++) {
            sort(startState.begin(), startState.begin()+idx);
            if(startState != midState) {break;}
        }
        cout << "Insertion Sort" << endl;
    } else {
        for(idx=1; idx<=N; idx*=2) {
            int i=0;
            for(; i+idx<=N; i+=idx) {
                sort(startState.begin()+i, startState.begin()+i+idx);
            }
            if(i<N) sort(startState.begin()+i, startState.end());
            if(startState == midState) break;
        }
        for(idx*=2; idx<=N; idx*=2) {
            int i=0;
            for(; i+idx<=N; i+=idx) {
                sort(startState.begin()+i, startState.begin()+i+idx);
            }
            if(i<N) sort(startState.begin()+i, startState.end());
            if(startState != midState) break;
        }
        cout << "Merge Sort" << endl;
    }
    for(int i=0; i<N; i++) {
        if(i) cout << " ";
        cout << startState[i];
    }
    return 0;
}