有1个3分test和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 i, j, k;
	for (i = 1; i < n; i++) { //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置 for (j = i - 1; j >= 0; j--)
			if (s[j] < s[i]) break; //如找到了一个合适的位置 if (j != i - 1) { //将比a[i]大的数据向后移 int temp = s[i]; for (k = i - 1; k > j; k--)
				s[k + 1] = s[k];
			//将a[i]放到正确位置上
			s[k + 1] = temp;
			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();
			for(int i=0; i<n-1; i++) {
				cout<<s[i]<<" ";
			}
			cout<<s[n-1]<<endl;
		}
		delete arr,s;
	}
	return 0;
}

4 total views, 4 views today