题目地址
https://pta.patest.cn/pta/test/15/exam/4/question/720
5-12 排序 (25分)
给定NN个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据1：只有1个元素；
- 数据2：11个不相同的整数，测试基本正确性；
- 数据3：103个随机整数；
- 数据4：104个随机整数；
- 数据5：105个随机整数；
- 数据6：105个顺序整数；
- 数据7：105个逆序整数；
- 数据8：105个基本有序的整数；
- 数据9：105个随机正整数，每个数字不超过1000。
输入格式:
输入第一行给出正整数NN（\le 10^5≤105），随后一行给出NN个（长整型范围内的）整数，其间以空格分隔。
输出格式:
在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
输入样例:
11 4 981 10 -17 0 -20 29 50 8 43 -5输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981
这个题是帮你计时用的。。
/*
给定NN个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
数据6：105个顺序整数；
数据7：105个逆序整数；
数据8：105个基本有序的整数；
数据9：105个随机正整数，每个数字不超过1000。
此题本身是用来比较排序算法速度用的，不过用快排综合水平挺快的。
写完算了
快排的结果
时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-07-05 21:16 答案正确 25 5-12 gcc 52 2
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 1/1 1 1
测试点2 答案正确 10/10 2 1
测试点3 答案正确 2/2 2 1
测试点4 答案正确 2/2 7 1
测试点5 答案正确 2/2 49 2
测试点6 答案正确 2/2 52 2
测试点7 答案正确 2/2 47 2
测试点8 答案正确 2/2 41 2
测试点9 答案正确 2/2 47 1
另，快排把cutoff从3改为100后，速度稍微快了一些
评测结果
时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-07-05 21:20 答案正确 25 5-12 gcc 48 2
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 1/1 2 1
测试点2 答案正确 10/10 2 1
测试点3 答案正确 2/2 2 1
测试点4 答案正确 2/2 8 1
测试点5 答案正确 2/2 48 2
测试点6 答案正确 2/2 39 2
测试点7 答案正确 2/2 41 2
测试点8 答案正确 2/2 42 2
测试点9 答案正确 2/2 44 1
插排的结果
评测结果
时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-07-05 21:19 答案正确 25 5-12 gcc 7915 2
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 1/1 2 1
测试点2 答案正确 10/10 2 1
测试点3 答案正确 2/2 2 1
测试点4 答案正确 2/2 26 1
测试点5 答案正确 2/2 3495 2
测试点6 答案正确 2/2 40 2
测试点7 答案正确 2/2 7915 2
测试点8 答案正确 2/2 63 2
测试点9 答案正确 2/2 3587 1
*/
#include<stdio.h>
#define CUTOFF 100
int T[100000];
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int median3(int a[],int left,int right)
{
// printf("median3 got %d as left,%d as right\n",left,right);
int middle=(left+right)/2;
if(a[left]>a[right])
swap(&a[left],&a[right]);
if(a[left]>a[middle])
swap(&a[left],&a[middle]);
if(a[middle]>a[right])
swap(&a[middle],&a[right]);
swap(&a[middle],&a[right-1]);
// printf("median3 got %d as a pivot,middle=%d\n",a[right-1],middle);
return a[right-1];
}
void InsertionSort(int a[],int left ,int right)
{
int i,j,temp;
for(i=left;i<right;i++)
{
temp=a[i+1];
for(j=i+1;j>left;j--)
{
if(temp<a[j-1])
a[j]=a[j-1];
else break;
}
a[j]=temp;
}
}
void quicksort(int a[],int left,int right)
{
int low,high,pivot;
low=left;
high=right-1;
if(right-left<=CUTOFF)
{
InsertionSort(a,left,right);
return;
}
pivot=median3(a,left,right);
while(1)
{
while(a[++low]<pivot);
while(a[--high]>pivot);
if(low<high)
swap(&a[low],&a[high]);
else break;
}
swap(&a[low],&a[right-1]);
quicksort(a,left,low-1);
quicksort(a,low+1,right);
}
int main()
{
int i,N;
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&T[i]);
}
quicksort(T,0,N-1);
for(i=0;i<N;i++)
{
printf("%d",T[i]);
if(i!=N-1)
printf(" ");
}
}