归并排序40分,求助
查看原帖
归并排序40分,求助
1083525
ZeRo2X楼主2024/8/9 12:17

wa了2,3,4三个点
写了对数器和sort对比
但对数器里都是对的

#include<bits/stdc++.h>
using namespace std;

int N;
int arr[100010], cpy[10010];

int test1[100010], test2[100010];	//test1原始数据,test2快排结果
int t;	//测试长度

void mergeSort(int l, int r);
void merge(int l, int m, int r);
void test(int max);

int main()
{
	/*
	cin>>t;
	test(t);
	*/
	
	cin>>N;
	for (int i = 0; i < N; i++)
	{
		cin>>arr[i];
	}
	mergeSort(0,N-1);
	for (int i = 0; i < N; i++)
	{
		cout<<arr[i]<<' ';
	}
	return 0;
}

void mergeSort(int l, int r)
{
	if (l == r)
	{
		return ;
	}
	else
	{
		int m = l + (r - l) / 2;
		mergeSort(l, m);
		mergeSort(m + 1, r);
		merge(l, m, r);
	}
}

void merge(int l, int m, int r)
{
	int a = l, b = m + 1, i = l;
	while (a <= m && b <= r)
	{
		cpy[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
	}
	while (a <= m)
	{
		cpy[i++] = arr[a++];
	}
	while (b <= r)
	{
		cpy[i++] = arr[b++];
	}
	for (i = l; i <= r; i++)
	{
		arr[i] = cpy[i];
	}
}

void test(int max)
{

	for (int i = 1; i <= 1000; i++)
	{	
		srand(time(NULL));
		for (int j = 1; j <= max; j++)
		{
			arr[j] = test1[j] = test2[j] = rand();
		}
		mergeSort(1, max);
		sort(test2+1, test2+max+1);
		bool b = true;
		for (int j = 1; j <= max; j++)
		{
			if (arr[j] != test2[j])
			{
				b=false;
			}
		}
		if (!b)
		{
			for (int j = 1; j <= max; j++)
			{
				cout<<test1[j]<<' ';
			}
			cout<<endl;
			for (int j = 1; j <= max; j++)
			{
				cout<<arr[j]<<' ';
			}
			cout<<endl;
			for (int j = 1; j <= max; j++)
			{
				cout<<test2[j]<<' ';
			}
			cout<<endl;
			cout<<"false!"<<endl;
		}
	}
}
2024/8/9 12:17
加载中...