#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[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]) == 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[i] 比较并处理
* 目的是判断 array[i] 应该分在左组还是右组,
* 同时还要把 array[begin] 的值放在分割线位置。
*
* 如果 array[i] 的值大于 array[begin]，则把 array[begin] 放在 i 前
* 也就是把 array[begin] 和 i 前的数换位
*/
if (array[i] > array[begin])
i--;
/* 把 array[begin] 放在 i 指向的位置 */
if (swap(&array[begin], &array[i]) == 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;
}
