有1个1分test 怎么都过不去，不搞了，代码先备着。

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int *arr,*s;
int ismerge=0;
bool check() {
	for(int i=0; i<n; i++) {
		if(arr[i]!=s[i]) return false;
	}
	return true;
}

void insert_once(int a[],int n) { //进行一次插入排序
	int op;
	for(int i=1; i<n; i++)
		if(a[i-1]>a[i]) {
			op=i;
			break;
		}
	for(int j=op-1; j>=0&&a[j]>a[j+1]; j--)
		swap(a[j],a[j+1]);
	return;
}
void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex) {
	int mLength = eIndex - bIndex;
	int i = 0;
	int j = bIndex;
	int k = mIndex;

	while (j < mIndex && k < eIndex) {
		if (pDataArray[j] <= pDataArray[k]) {
			pTempArray[i++] = pDataArray[j];
			j++;
		} else {
			pTempArray[i++] = pDataArray[k];
			k++;
		}
	}

	if (j == mIndex)
		while (k < eIndex)
			pTempArray[i++] = pDataArray[k++];
	else
		while (j < mIndex)
			pTempArray[i++] = pDataArray[j++];

	for (i = 0; i < mLength; i++)
		pDataArray[bIndex + i] = pTempArray[i];
}
void BottomUpMergeSort(int* pDataArray, int iDataNum) {
	int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);
	int length = 1;
	while (length < iDataNum) {
		if(check()) ismerge=1;
		int i = 0;
		for (; i + 2*length < iDataNum; i += 2*length)
			Merge(pDataArray, pTempArray, i, i + length, i + 2*length);
		if (i + length < iDataNum) Merge(pDataArray, pTempArray, i, i + length, iDataNum);
		length *= 2;
		if(ismerge==1) {
			free(pTempArray);
			return;
		}
	}
	free(pTempArray);
}
int main(int argc, char** argv) {
	while(cin>>n) {
		arr= new int[n+1];
		s  = new int[n+1];
		for(int i=0; i<n; i++) {
			cin>>arr[i];
		}
		for(int i=0; i<n; i++) {
			cin>>s[i];
		}
		BottomUpMergeSort(arr,n);
		if(ismerge == 1) {
			cout<<"Merge Sort"<<endl;
			for(int i=0; i<n-1; i++) {
				cout<<arr[i]<<" ";
			}
			cout<<arr[n-1]<<endl;
		} else {
			cout<<"Insertion Sort"<<endl;
			insert_once(s,n);
			for(int i=0; i<n-1; i++) {
				cout<<s[i]<<" ";
			}
			cout<<s[n-1]<<endl;
		}
		delete arr,s;
	}
	return 0;
}

739 total views, no views today