/**/ /*
    标题：< <系统设计师> >应试编程实例-[分治法程序设计]
    作者：成晓旭
    时间：2002年09月18日(21:43:00-22:03:00)
          实现“快速排序算法”问题的分而治之算法函数
*/
#include     " stdio.h "
#include     " stdlib.h "

// :============================“快速排序算法”问题的分而治之算法===========================
/**/ /*
    时间：2002年09月18日(21:43:00-22:03:00)
          实现“快速排序算法”问题的分而治之算法函数
    问题描述:
            用分治法的思想实现快速排序算法。
    编程思想:
            快速排序算法的基本思想本身就是分治法。通过分割，将无序序列分成两部分，
        其中前一部分的元素值都小于后一部分的元素值。然后每一部分再各自递归进行上
        述过程，直到每一部分的长度为1为止。
            首先，在序列的第一个，中间一个，最后一个元素中选取中项，设为p[middle],
        并作temp = p[middle](保存中项);
            其次，将序列中的第一个元素移到p[middle]的位置上；
            然后，设两个指针i,j分别指向将排序序列的第一个元素和最后一个元素；
            重复以上两步，直到i = j为止；
            最后，将array[i] = temp(将tmep移到array[i])。
*/
#define     MAXN    20

void     Carve_up( int  array[], int  number, int   * m)
... {
    int i,j,k,middle,temp;
    i = 0;
    j = number - 1;
    k = (i + j) / 2;
    //在下标i,j,k的数组元素中选取中项
    if(array[i] >= array[j] && array[j] >= array[k])
        middle = j;        //Array[j]是中项
    else if(array[i] >= array[k] && array[k] >= array[j])
        middle = k;        //Array[k]是中项
    else
        middle = i;        //Array[i]是中项
    temp = array[middle];
    array[middle] = array[i];
    while(i != j)
    ...{
        while(i < j && array[j] >= temp)
            j --;    //j逐步减小，直到发现一个array[j] < temp为止
        if(i < j)
        ...{
            array[i] = array[j];
            i ++ ;
            while(i < j && array[i] <= temp)
                i ++ ;    //i逐步减小，直到发现一个array[i] > temp为止
            if(i < j)
            ...{
                array[j] = array[i];
                j --;
            }
        }
    }
    array[i] = temp;
    *m = i;
    return;
}
void     Quick_Sort( int  array[], int  number)
... {
    int i;
    if(number > 1)
    ...{
        Carve_up(array,number,&i);
        Quick_Sort(array,i);
        Quick_Sort(&array[i + 1],number - i - 1);
    }
    return;
}
void     Run_Quick_Sort()
... {
    int i,array[MAXN] = ...{1,9,3,7,18,2,20,4,16,5,15,6,14,7,13,6,12,8,11,10};
    Quick_Sort(array,MAXN);
    for(i = 0;i < MAXN;i++)
        printf("%3d",array[i]);
}
// :============================“快速排序算法”问题的分而治之算法===========================

int  main( int  argc,  char *  argv[])
... {
    Run_Quick_Sort();

    printf(" 应用程序运行结束！ ");
    return 0;
}