/*  从小到大的排序
快速法定义了三个参数

数组首地址*a,
要排序数组起始元素下标i,
要排序数组结束元素下标j

它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，
把比它小的元素放到它的左边，比它大的放在右边。
然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序
*/

#include<stdio.h>
#define N 10

void in_array(int a[],int n)  //创建数组
{
    int i;
    printf("Please input some integer :\n");
    for(i=0;i<n;i++)
    {
        printf("a[%d] = ",i);
        scanf("%d",&a[i]);
    }
}

void out_array(int a[],int n)  //输出数组
{
    int i;
    printf("we will output the array :\n");
    for(i=0;i<n;i++)
        printf("a[%d] = %d\n",i,a[i]);
}


int k_array(int a[],int L,int R)  //快速排序法第一步：求得基数
{
    int i,j,k;
    i = L;
    j = R;
    k = a[0];

    while(i<j)   
    {
        if(i<j&&k<=a[j])    //从右到左，找到第一个比k小的
            j--;
        if(i<j)
        {
            a[i] = a[j];
            i++;
        }

        if(i<j&&k>a[i])    //从左到右，找到第一个比k大的
            i++;
        if(i<j)
        {
            a[j] = a[i];
            j--;
        }
    }

    a[i] = k;    //退出时将基数填在中间坑里面
    return i;
}

void quick_sort(int a[],int L,int R)  //对两边分别进行排序，随便用个简单的排序法
{
    int i,j,t;
    for(i=L;i<R-1;i++)
        for(j=i+1;j<R;j++)
            if(a[i]>a[j])
            {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
}

void main()
{

    int s[N];
    int k;
    in_array(s,N);
    out_array(s,N);
    k = k_array(s,0,N);
    quick_sort(s,0,k);
    quick_sort(s,k,N);
    quick_sort(s,0,N);
    out_array(s,N);
}

问题：取得中间数，分别对两边进行排序，中间数k反而吊在了中间，于是又把所有的进行了一次排序，不知道这样做有没有意义？

//参考网址：
//http://bbs.
//http://

经过研究用递归的方法对数组进行排序，以及重新修改代码，得到新的代码，如下和附件。


/*  从小到大的排序

快速法定义了三个参数

数组首地址*a,
要排序数组起始元素下标i,
要排序数组结束元素下标j

它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，
把比它小的元素放到它的左边，比它大的放在右边。
然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序
*/

#include<stdio.h>
#define N 10
void out_array(int a[],int n)  //输出数组
{
    int i;
    for(i=0;i<n;i++)
        printf("a[%d] = %d\n",i,a[i]);
}


int k_array(int a[],int L,int R)  //快速排序法第一步：求得基数下标
{
    int i,j,k;
    i = L;
    j = R;
    k = a[0];

    while(i<j)   
    {
        while(i<j&&k<=a[j])    //从右到左，找到第一个比k小的
            j--;
        if(i<j)
        {
            a[i] = a[j];
            i++;
        }

        while (i<j&&k>a[i])    //从左到右，找到第一个比k大的
            i++;
        if(i<j)
        {
            a[j] = a[i];
            j--;
        }
    }

    a[i] = k;    //退出时将基数填在中间坑里面
    return i;
}

void quick_sort(int a[],int L,int R)  //对基数两边分别进行排序，基数单独留出来。随便用个简单的排序法
{
    int i,j,t;
    for(i=L;i<R-1;i++)
        for(j=i+1;j<R;j++)
            if(a[i]>a[j])
            {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
}

void main()
{

    int s[N] = {99,58,2,61,49,108,28,76,38,44};
    int k;

    printf("the first output array :\n");
    out_array(s,N);

    printf("the sceond output array :\n");
    k = k_array(s,0,N);
    out_array(s,N);
    printf("\n");
    printf("k = %d\n",k);

    quick_sort(s,0,k-1);
    quick_sort(s,k+1,N);

    printf("the third output array :\n");
    out_array(s,N);

}