原题链接：[蓝桥杯][算法提高]快速排序
题目描述：用递归来实现快速排序（quick sort）算法。快速排序算法的基本思路是：假设要对一个数组a进行排序，且a[0] = x。首先对数组中的元素进行调整，使x放在正确的位置上。同时，所有比x小的数都位于它的左边，所有比x大的数都位于它的右边。然后对于左、右两段区域，递归地调用快速排序算法来进行排序。
最初写的程序如下：
#include
#include
void qsort(int *a, int low, int high);
int main()
{
int N=10;
int *a=(int *)malloc(sizeof(int)*N);
int t;
int i=0;
scanf("%d", &t);
while(t!=0 )
{
a[i++]=t;
scanf("%d", &t);
}
int len=i; // 数组真正长度
qsort(a,0,len-1);
for(i=0;i<len;i++)
printf("%d ",a[i]);
free(a);
return 0;
}
void qsort(int *a, int low, int high){
if(low>=high) return;
int key=a[low];
int left=low, right=high;
while(low<high)
{
while((low
if(low<high)
{
a[low]=a[high];
low++;
}
while((low<high)&&(a[low]<=key)) low++;
if(low<high)
{
a[high]=a[low];
high--;
}
}
a[low]=key;
qsort(a,left,high-1);
qsort(a,high+1,right);
}
乍看起来非常完美，所以反复提交，不信邪地一遍又一遍运行，得到的结果依旧一样。实在找不到原因，花了89大洋买了刷题小能手，查看输出结果，终于找到原因。不是在快速排序那儿，而是在输入数据处。题干要求不超过10个数，没有做判断！！所以修改后代码如下(请注意红色部分)：
#include
#include
void qsort(int *a, int low, int high);
int main()
{
int N=10;
int *a=(int *)malloc(sizeof(int)*N);
int t;
int i=0;
scanf("%d", &t);
while(t!=0 && i<N)
{
a[i++]=t;
scanf("%d", &t);
}
int len=i; // 数组真正长度
qsort(a,0,len-1);
for(i=0;i<len;i++)
printf("%d ",a[i]);
free(a);
return 0;
}
void qsort(int *a, int low, int high){
if(low>=high) return;
int key=a[low];
int left=low, right=high;
while(low<high)
{
while((low
if(low<high)
{
a[low]=a[high];
low++;
}
while((low<high)&&(a[low]<=key)) low++;
if(low<high)
{
a[high]=a[low];
high--;
}
}
a[low]=key;
qsort(a,left,high-1);
qsort(a,high+1,right);
}
0.0分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复