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;
}
}
}