从这里开始--有关快排

第一次从上写东西，希望能从这里找到我的一点点轨迹吧。

今天来说说有关快排，快速排序，C++中有sort，然而今天我想说的是C语言手敲快排。

C语言快排其实质实际上是递归调用的过程，过程如下：

例：排序数组【6 2 7 3 8 9】

数组下标 0 1 2 3 4 5

Step One：创建变量i、j。令i = 0（指向第一个数据即0），j ＝ 5（指向最后一个数据即n - 1）

创建关键数据变量key = 6。

Step Two：我们的目的是把所有比key小的数移动到key的左边，所以我们开始寻找比6小的数，从j开始，从右往左找，不断递减j的值，最终我们找到了比6小的值3，于是我们把3移到key（i）所在的位置。

于是数组变成这样

排序数组 【3 2 7 3 8 9】 key = 6 数组下标 0 1 2 3 4 5

Step Three：接下来，我们的目的是找比key（6）大的数，而且要从前往后找了。将变量i不断++，发现7是第一个比k大的，于是把7放到刚刚j所在位置，于是数组变成这样：

排序数组 【3 2 7 7 8 9】 key = 6 数组下标 0 1 2 3 4 5

Step Four：循环二、三步，直到左边的数都比key小，右边的数都比key大，直观来说就是i >= j。

Step Five：递归排序左右两部分，排序完整个数组。 即pai(a, z, i - 1, n); pai(a, i + 1, y, n);

以下是完整代码：

#include <stdio.h> #include <stdlib.h> void pai(int a[], int z, int y, int n) { int key = a[z], i = z, j = y; if(i > j) return; while(i < j) { while(i < j && a[j] >= key) { j--; } a[i] = a[j]; while(i < j && a[i] <= key) { i++; } a[j] = a[i]; for(i = 0; i <= n - 1; i++) { printf("%d ", a[i]); } printf("\n"); } a[i] = key; pai(a, z, i - 1, n); pai(a, i + 1, y, n); } int main() { int n, i, a[100]; scanf("%d", &n); for(i = 0; i <= n - 1; i++) { scanf("%d", &a[i]); } pai(a, 0, n - 1, n); for(i = 0; i <= n - 1; i++) { printf("%d ", a[i]); } printf("\n"); return 0; } /*5 2 4 3 5 1*/