假设现在对“612 79345 108”这10个数进行了排序。 首先，在这个序列中适当地找数量作为基准数。 (请不要被这个名词吓到。 是为了参照的数量。 我知道以后有什么用。 为了方便，以最初的数6为基准数吧。 然后，必须将此序列中大于基准数的所有数置于6的右侧，将小于基准数的数置于6的左侧。 如下排列。
312 5469 7108
在初始状态下，数字6位于序列的第一位。 我们的目标是假设这个位置是k，将6移动到序列中间的某个位置。 我现在需要找这个k。 并且，以第k个为边界点，左边的数都在6以下，右边的数都在6以上。 想想看。 你有办法做那个吗？
给你个提示吧。 请记住泡沫排序是如何通过“交换”一步一步地返回数量的。 这时也可以用“交换”的方法达到目的。 具体怎么一步一步地交换？ 怎么交换方便省时间？ 请先不要着急往下看，拿出钢笔，试着在纸上画画。 高中时代第一次学习泡沫排序算法时，我觉得泡沫排序很浪费时间。 每次只能比较相邻的两个数。 这显然是不合理的。 所以我想了一个方法。 后来我知道这是“快速排序”。 请让我小不点自恋(^o^ )。
方法很简单。 分别从初始排列“612 79345 108”的两端进行“探测”。 先从右向左找小于6的数，然后从左向右找大于6的数，交换他们。 其中，两个变量I和j可以分别指向序列的最左侧和最右侧。 我们给这两个变量取个好名字“哨兵I”和“哨兵j”。 gddfj向哨兵I指向序列的最左边(即i=1)，指向数字6。 使哨兵j指向序列的最右边(即j=10 )，指向数字8。
首先哨兵j开始出动了。 这里设定的基准数是最左边的数，所以哨兵j需要先出动是非常重要的(请自己想想为什么)。 哨兵j一步一步向左移动，直到找到不足6的数量为止。 然后哨兵I再向右移动一步，直到找到数量大于6的数字(即I )。 最后哨兵j停在数字5之前，哨兵I停在数字7之前。
现在交换哨兵I和哨兵j所指要素的值。 更换后的顺序如下。
61259 347108
第一次交换到此结束。 接下来哨兵j继续向左移动。 (友情提醒，每次哨兵j必须先出发。 他发现4 (小于标准数6，满足要求)就停下来了。 哨兵I也继续向右移动，他发现9 (大于标准数6，符合要求)就停下来了。 此时再次进行更换，更换后的顺序如下。
612 54397 108
第二次交换结束，“探测”继续。 哨兵j继续向左移动，他发现3 (小于标准数6，符合要求)又停下来了。 哨兵I继续向右移动，很辛苦！ 哨兵I和哨兵j相遇时，哨兵I和哨兵j都走到3前面。 表示“探测”在此时结束。 交换基准数6和3。 更换后的顺序如下。
31 25469 7108
第一次“勘探”到此真的结束了。 此时，以基准数6为边界点，6的左边的数量都在6以下，6的右边的数量都在6以上。 回顾刚才的过程，其实哨兵j的使命是寻找比标准数小的数，哨兵I的使命是寻找比标准数大的数直到I和j见面。
OK，说明结束了。 现在，基准数6已经就位，它正好位于序列的第6位。 此时，我们以6为边界点将原数组分割为两个数组。 左边的数组为“31 254”，右边的数组为“97108”。 必须分别处理这两个序列。 6因为左边和右边的序列至今仍很混乱。 但是没关系。 我们掌握了方法。 接下来模拟刚才的方法分别处理6的左边和右边的排列就可以了。 首先，让我们处理6的左边序列。
左边的序列是“312 54”。 请以该系列为3为基准数，调整为3的左边数均在3以下，3的右边数均在3以上。 好的，蘸钢笔吧。
如果模拟没有错误，则调整完成后的序列顺序为。
21354
好了，现在
在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下。1 2 3 4 5 6 9 7 10 8
对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下。
1 2 3 4 5 6 7 8 9 10
到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
#include <stdio.h>int a[101],n;//定义全局变量，这两个变量需要在子函数中使用void quicksort(int left, int right) {int i, j, t, temp;if(left > right)return; temp = a[left]; //temp中存的就是基准数 i = left; j = right; while(i != j) { //顺序很重要，要先从右边开始找 while(a[j] >= temp && i < j) j--; while(a[i] <= temp && i < j)//再找右边的 i++; if(i < j)//交换两个数在数组中的位置 { t = a[i]; a[i] = a[j]; a[j] = t; } } //最终将基准数归位 a[left] = a[i]; a[i] = temp; quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程 quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程}int main() {int i; //读入数据scanf("%d", &n);for(i = 1; i <= n; i++)scanf("%d", &a[i]); quicksort(1, n); //快速排序调用 //输出排序后的结果 for(i = 1; i < n; i++) printf("%d ", a[i]); printf("%dn", a[n]); return 0;}原文链接：
http://www.cnblogs.com/ahalei/p/3568434.html