快速排序（C语言版）

QuickSort.c

#include <stdio.h>

int main() {
    printf("Hello, World!\n");

    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;
}

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[i]);
    }
    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])) {
                    /* 只显示begin 到 end 下标间的数据 */
                    show(array, maxlen, begin, end);
                }
                j--;
            } else { /* 否则 i 下标向后移动,准备比较下一个数。*/
                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[i] > array[begin]) {
            i--;
        }

        /* 把 array[begin] 放在 i 指向的位置 */
        if (swap(&array[begin], &array[i])) {
            show(array, maxlen, begin, end);
        }

        quickSort(array, maxlen, begin, i);
        quickSort(array, maxlen, j, end);
    }
}

打印输出.txt

   49  38  65  97  48  13  27  11  56  45
   49  38  45  97  48  13  27  11  56  65
   49  38  45  56  48  13  27  11  97  65
   49  38  45  11  48  13  27  56  97  65
   49  38  45  11  48  13  27  56  97  65
   27  38  45  11  48  13  49  56  97  65
   27  38  45  11  48  13  49
   27  49  45  11  48  13  38
   27  13  45  11  48  49  38
   27  13  48  11  45  49  38
   27  13  11  48  45  49  38
   27  13  11  48  45  49  38
   11  13  27  48  45  49  38
   11  27  13
    13  27
     27  38  45  49  48
     27  49  45  38  48
     27  45  49  38  48
      45  48  38  49
      45  38  48  49
      38  45  48  49
       45  49  48
        48  49
         49  65  97  56
         49  97  65  56
          56  65  97
          56  97  65
           65  97
   11  13  27  38  45  48  49  56  65  97