PTA 数据结构与算法 7-12 排序
如有不对，请指正
给出题目：
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题考察各种排序算法的表现；各组测试数据具有不同的特性
仅包含单一元素的数据集；
包含11个互不相同的整数的数据组用于验证基本正确性；
生成了包含103个随机整数值的数据集；
包含了104个随机生成的正偶数值的测试样本；
生成了一个拥有105个完全独立均匀分布的正奇数值集合；
按升序排列的连续正奇数组成的基础测试用例；
按降序排列的连续正奇数组成的关键性能指标测试案例；
近似有序排列的连续正奇数组成的核心算法验证样本；
生成了包含上限值限制在千位范围内的均匀分布正奇数值集合。
输入第一行为一个正整型数值（其值不超过10^5），随后下一行呈现N个超出常规整数范围的数值（长整型范围内），这些数值之间以逗号分隔
输出格式:
在一行中呈现按升序排列的结果，并用一个空格分隔各数字；确保行末无多余空格
输入样例:
11
4 981 10 -17 0 -20 29 50 8 43 -5
输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981
这就是一道常见的排序问题 因为当变量N达到10^5数量级时 采用低时间复杂度的排序算法就足够了 我选择了快速排序算法
#include<stdio.h>
void QuickSort(long *array,int left,int right);
int main(void)
{
int N,i;
scanf("%d",&N);
long array[N];
for(i=0;i<N;i++)
scanf("%ld",array+i);
QuickSort(array,0,N-1);
for(i=0;i<N-1;i++)
printf("%ld ",array[i]);
printf("%ld",array[i]);
return 0;
}
void QuickSort(long *array,int left,int right)
{
if(left>=right)
return ;
int i,j;
long temp;
i=left;
j=right;
while(i<j){
while(array[j]>=array[left]&&i<j)
j--;
while(array[i]<=array[left]&&i<j)
i++;
if(i<j){
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
temp=array[left];
array[left]=array[i];
array[i]=temp; //基数归位
QuickSort(array,left,i-1);
QuickSort(array,i+1,right);
return ;
}
//快速排序这里我们探讨一个常见问题：快速排序是否必须从右侧启动？我们通常看到的版本都是从右侧开始的[1]；然而，并非一定要从右侧开始[2]；关键在于确保交换操作中基数的位置与排序起点处于相反方向[3]；参考这篇详细文章快排为什么一定要从右边开始可以获得更多信息；不过我认为这种做法稍显繁琐；特别是在处理大数据量时；为了避免有序数组的情况影响效率；通常会采用三数取中法选择基准值（qsort另算）[4]；这种方法的核心在于确保基准值与排序起点位置相反即可；为此我们可以引入一个标记变量来判断左端点是否被交换位置；因为快速排序的基本思想就是在确定基准值位置的同时实现逆序对交换[5]；如果未进行左端点交换就意味着基准值已经处于正确位置[6]；以下以上述文章中的数据为例：序列 2 1 4 9 我们设定left=0,right=3 进行快速排序时，默认是从数组右边开始处理 我们发现第一轮后left指针指向了2 right指针也指向了2 然而在这段过程中没有进行逆序对的交换 因此无需将基准值与左端点互换位置 下一轮则需要重新设定left=0 right=1 进行后续排序 这种做法解决了基准值与排序起点必须相反的问题