蓝桥杯算法提高-快速排序（C语言代码）（一定注意题干细节）

原题链接：[蓝桥杯][算法提高]快速排序

题目描述：用递归来实现快速排序（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); 

}