我觉得冒泡排序是比较简单的；所以今天我们实现一个叫做快速排序的；

Problem

你想要将（4，3，5，1，2）排序成（1，2，3，4，5）

你决定使用最简单的快速排序；

Solution

首先，打开你的terminal，我写得C代码通常都是用vi编辑，gcc编译；

vim quickSortSample.c

因为，快速排序需要对数据进行分割然后处理，再分割再处理；

显然需要一个递归的过程；

所以，我们先把递归结束条件写好；

#include

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
}

也就是说，当输入只有一个数字就没有必要排序啦！直接返回；

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? p = a[n / 2];? // Get the middle element as pivot ..? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? for ( i = 0, j = n -1;; i++, j--) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? //TODO ...

? ? }? ? ?
}

注意： p = a[n / 2];的目地是获取数组中得中间位置的数据；

我们都知道，数组下标是整数，因此，如果n=3那么n/2应该是1，此时正好平分数组；

若是，n=4那么n/2应该是2,而此时它们就不完全是平分数组啦；

for循环的作用是为了从前后两个方向分别遍历；

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? p = a[n / 2];? // Get the middle element as pivot ..? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? for ( i = 0, j = n -1;; i++, j--) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? while (a[i] < p)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? i++;
? ? ? ? while (p < a[j])? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? j--;
? ? }? ? ? ? ?
}

注意：我们在for循环中又进行啦while循环；

它的作用是对元素进行遍历，假设左边的数据没有p中保存的元素大，那么继续寻找，并且把i自增；

当找到比p大的或者相等得则停止第一个while循环；

例如：如果数组(2,5,3,1,4)那么p显然是3,当while循环发现5大于3时停止循环，此时i=1；

同理，第二个while循环中，p依然是3，当while循环第一次发现4大于3则继续循环此时j=4；

当while循环到j=3时，得到的元素是1，1不大于3所以停止循环，此时得到的j=3；

好啦！那么我们知道在for循环中没有明确指定循环停止条件；

它该什么时候停止呢？

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? p = a[n / 2];? // Get the middle element as pivot ..? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? for ( i = 0, j = n -1;; i++, j--) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? while (a[i] < p)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? i++;
? ? ? ? while (p < a[j])? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? j--;
? ? ? ? if ( i >= j)
? ? ? ? ? ? break;
? ? }?
}

注意：当i>=j意味着此时数据已经全部遍历完了；

因为i与j分布在数组左右两部分，当它们重合，当然也就表明它们遍历完啦；

刚才，我们的两个while循环分别找到啦一个左边比p大得元素，和一个右边比p小的数字；

显然这两个元素应该交换位置的；

那么怎么实现呢；

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? p = a[n / 2];? // Get the middle element as pivot ..? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? for ( i = 0, j = n -1;; i++, j--) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? while (a[i] < p)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? i++;
? ? ? ? while (p < a[j])? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? j--;
? ? ? ? if ( i >= j)
? ? ? ? ? ? break;
? ? ? ? tmp = a[i]; a[i] = a[j]; a[j] = tmp;? ? //swap both ..? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? }?
}

我们看到了，在冒泡排序中也用到得交换语句；

此时我们完全遍历了一遍数组；

我们在main函数中测试一下；

#include

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;

? ? p = a[n / 2];? // Get the middle element as pivot ..

? ? for ( i = 0, j = n -1;; i++, j--) {
? ? ? ? while (a[i] < p)
? ? ? ? ? ? i++;
? ? ? ? while (p < a[j])
? ? ? ? ? ? j--;
? ? ? ? if ( i >= j)
? ? ? ? ? ? break;
? ? ? ? tmp = a[i]; a[i] = a[j]; a[j] = tmp;? ? //swap both ..
? ? }?
}

int main(void)
{
? ? int a[] = { 2, 5, 3, 1, 4};
? ? int n = sizeof a /sizeof a[0];
? ? int i;
? ? for (i = 0; i < n; i++)
? ? ? ? printf("%d%s", a[i], i == n -1 ? "\n" : " ");
? ? quick_sort(a, n);
? ? for (i = 0; i < n; i++)
? ? ? ? printf("%d%s", a[i], i == n -1 ? "\n" : " ");
? ?
? ? return 0;
}

main函数的语句都非常容易懂，就不解释啦；

看看编译运行的结果：

显然，运行的结果是我们预期的；

3左边的都比3小啦！那若果数据多一些呢；

比如{ 2, 5, 7, 3, -1, 1, 4}我们会发现左边有两个元素都比3大，理论上要进行两次交换；

显然当它交换完[1]与[5]元素后，它又是怎么继续的我们关心这个问题；

显然交换完数据后，又进入for循环；

for循环没有结束条件，因此，i++,j--完成后，此时i=2,j=4；

接下来执行两个while发现，第一个while发现a[2]是7 不小于p此时不执行i++；

同样在第二个while中也发现a[4]是-1不大于p此时不执行j--；

然后到if语句不成立，因此继续进行数据交换；

测试如下数据；

#include

void quick_sort( int *a, int n)
{
? ? int i, j, p, tmp;
? ? if (n < 2)? return;

? ? p = a[n / 2];? // Get the middle element as pivot ..

? ? for ( i = 0, j = n -1;; i++, j--) {
? ? ? ? while (a[i] < p)
? ? ? ? ? ? i++;
? ? ? ? while (p < a[j])
? ? ? ? ? ? j--;
? ? ? ? if ( i >= j)
? ? ? ? ? ? break;
? ? ? ? tmp = a[i]; a[i] = a[j]; a[j] = tmp;? ? //swap both ..
? ? }
}

int main(void)
{
? ? int a[] = { 2, 5, 7, 3, -1, 1, 4};
? ? int n = sizeof a /sizeof a[0];
? ? int i;
? ? for (i = 0; i < n; i++)
? ? ? ? printf("%d%s", a[i], i == n -1 ? "\n" : " ");
? ? quick_sort(a, n);
? ? for (i = 0; i < n; i++)
? ? ? ? printf("%d%s", a[i], i == n -1 ? "\n" : " ");

? ? return 0;
}

我们会得到如下结果：