实现快排算法

上学时学过的快排算法，不过还真没去好好看更没有把它用语言实现。

现在正好想补补算法，自己写了一个实现。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

我这个用的原地排序实现的，代码很短逻辑很简单而且我还添加了大量的注释。（如果发现代码或注释有问题告诉我啊）别被代码的这么长吓到，其实其中有 2/3 是注释。

#include "stdio.h"

/*
 * 显示数组
 * 只显示begin 到 end 下标间的数据到对应位置。
 * 如,数组为 13, 17, 12 并先后执行:
 *  show(array, 3, 0, 2);
 *  show(array, 3, 1, 2);
 *  show(array, 3, 1, 1);
 * 会显示为:
 *   13  17  12
 *       17  12
 *       17
 */
void show(int array[], long maxlen, int begin, int end)
{
    int i = 0;

    /* 不关心的数据用空格填充显示 */
    for(i=0; i<begin; i++)
        printf("    ");

    for(i=begin; i<=end; i++)
        printf("%4d", array);

    printf("\n");
}

/*
 * 两个数交换数值。
 * 返回为 1 时说明进行了交换。
 * 返回为 0 时说明两个数值相同没必要交换。
 * 此返回值可以用于只想打印结果变化的情况。
 */
int swap(int *i, int *j)
{
   int temp;

    if(*i == *j)
        return 0;

    temp = *i;
    *i = *j;
    *j = temp;

    return 1;
}

/*
 * 快速排序函数
 * 此函数只会对begin下标(包括begin )和end(包括end)下标间的数据进行排序
 */
void quicksort(int array[], int maxlen, int begin, int end)
{
    int i, j;

    if(begin < end) {
        /* 因为开始值作为基准值不用移动，所以需要比较的值是从 begin+1 开始 */
        i = begin + 1;
        j = end;

        /*
         * 此循环的作用：array[begin] 为基准对 array[begin+1] 和 array[end]
         * 之间的数进行初步分组，分组后的效果见循环后的描述
         *
         * 此处写 while(i != j) 是等价的，因为初始状态 i<=j 且每次i和j的
         * 相对变化值为 1 所以不会出现 i>j的情况
         */
        while(i < j) {
            /* 如果当前值大于 array[begin]，把当前值换到 j 指向的位置,换位后 j 下标前移 */
            if(array[i] > array[begin]) {
                if(swap(&array[i], &array[j]) == 1)
                    show(array, maxlen, begin, end); /* 只显示begin 到 end 下标间的数据 */
                j--;
            }
            /* 否则 i 下标向后移动,准备比较下一个数。*/
            else
                i++;
        }

        /*
         * 在此时: i=j, array还没有进行判断处理
         * 且 array[begin+1] ~ array[i-1] 都小于 array[begin]
         * 且 array[i+1] ~ array[end] 都大于 array[begin]
         *
         * 接着: 对 array[begin] 和 array 比较并处理
         * 目的是判断 array 应该分在左组还是右组,
         * 同时还要把 array[begin] 的值放在分割线位置。
         *
         * 如果 array 的值大于 array[begin]，则把 array[begin] 放在 i 前
         * 也就是把 array[begin] 和 i 前的数换位
         */
        if (array > array[begin])
            i--;

        /* 把 array[begin] 放在 i 指向的位置 */
        if(swap(&array[begin], &array) == 1)
            /* 只显示begin 到 end 下标间的数据
            show(array, maxlen, begin, end);

        /* 再从分割线位置 i 分组分别排序 */
        quicksort(array, maxlen, begin, i);
        quicksort(array, maxlen, j, end);
    }
}
int main(int argc, char* argv[])
{
    int array[10] = {49, 38, 65, 97, 48, 13, 27, 11, 56, 45};
    int maxlen = sizeof(array) / sizeof(int);

    show(array, maxlen, 0, maxlen-1); /* 打印初始顺序 */
    quicksort(array, maxlen, 0, maxlen-1);
    show(array, maxlen, 0, maxlen-1); /* 打印最终结果 */
    getchar();

    return 0;
}