本节介绍一个非常优秀且最常用的排序算法，快速排序算法。这个算法极其重要，初学者一定要掌握。
快速排序尤其适用于对大数据的排序，它的高速和高效无愧于“快速”两个字。虽然说它是“最常用”的，可对于初学者而言，用它的人却非常少。因为虽然很快，但它也是逻辑最复杂、最难理解的算法，因为快速排序要用到递归和函数调用。
快速排序所采用的思想是分治的思想。所谓分治，就是指以一个数为基准，将序列中的其他数往它两边“扔”。以从小到大排序为例，比它小的都“扔”到它的左边，比它大的都“扔”到它的右边，然后左右两边再分别重复这个操作，不停地分，直至分到每一个分区的基准数的左边或者右边都只剩一个数为止。这时排序也就完成了。
所以快速排序的核心思想就是将小的往左“扔”，将大的往右“扔”，只要能实现这个，就与快速排序的思想吻合。从初学者的角度，“小的往左扔大的往右扔”首先能想到的往往是小的往前插，大的往后插。这确实是一个思路，但我们知道，数组是不擅长插入的。这种思路虽然能吻合快速排序的思想，但实现起来就不是“快速”排序，而是“慢速”排序了。所以这种方法是不可行的。于是就有了下面的“舞动算法”。
“舞动算法”的思想是用交换取代插入，大大提高了排序的速度。下面首先详细地讲解一下数组快速排序的过程。
假设序列中有 n 个数，将这 n 个数放到数组 A 中。“舞动算法”中一趟快速排序的算法是： 1. 设置两个变量 i、j，排序开始的时候：i=0，j=n–1。
2. 以数组第一个元素为关键数据，赋给变量 key，即 key=A[0]。
3. 从 j 开始向前搜索，即由后开始向前搜索（j--），找到第一个小于 key 的值 A[j]，将 A[j] 和 A[i] 互换。
4. 然后再从 i 开始向后搜索，即由前开始向后搜索（++i），找到第一个大于 key 的 A[i]，将 A[i] 和 A[j] 互换。
5. 重复第 3、4 步，直到 i=j。此时就能确保序列中所有元素都与 key 比较过了，且 key 的左边全部是比 key 小的，key 的右边全部是比 key 大的。
第一轮比较后序列就以 key 为中心分成了左右两部分，然后分别对左右两部分分别递归执行上面几个步骤，直到排序结束。
下面列举一个简单的例子，比如对如下数组 a 中的元素使用快速排序实现从小到大排序：
35 12 37 -58 54 76 22
1) 首先分别定义 low 和 high 用于存储数组第一个元素的下标和最后一个元素的下标，即 low=0，high=6。
2) 然后定义 key 用于存放基准数，理论上该基准数可以取序列中的任何一个数。此处就取数组的第一个元素，即把 a[low] 赋给 key。
3) 然后 key 和 a[high] 比较，即 35 和 22 比较，35>22，则它们互换位置：
22 12 37 -58 54 76 35
4) 然后 low++==1，key 和 a[low] 比较，即 35 和 12 比较，12<35，则不用互换位置；继续 low++==2，然后 key 和 a[low] 比较，即 35 和 37 比较，37>35，则它们互换位置：
22 12 35 -58 54 76 37
5) 然后 high--==5，key 和 a[high] 比较，即 35 和 76 比较，35<76，则不用互换位置；继续 high--==4，然后 key 和 a[high] 比较，即 35 和 54 比较，35<54，则不用互换位置；继续 high--==3，然后 key 和 a[high] 比较，即 35 和 -58 比较，35>–58，则它们互换位置：
22 12 -58 35 54 76 37
6) 然后 low++==3，此时 low==high，第一轮比较结束。从最后得到的序列可以看出，35 左边的都比 35 小，35 右边的都比 35 大。这样就以 35 为中心，把原序列分成了左右两个部分。接下来只需要分别对左右两个部分分别重复上述操作就行了。
对于人类而言，这个过程确实比前面的排序算法复杂。但对于计算机而言，这个过程却没那么复杂。下面来写一个程序:
# include <stdio.h> void Swap(int *, int *); //函数声明, 交换两个变量的值 void QuickSort(int *, int, int); //函数声明, 快速排序 int main(void) { int i; //循环变量 int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500}; QuickSort(a, 0, 20); /*引用起来很简单, 0为第一个元素的下标, 20为最后一个元素的下标*/ printf("最终排序结果为:\n"); for (i=0; i<21; ++i) { printf("%d ", a[i]); } printf("\n"); return 0; } void Swap(int *p, int *q) { int buf; buf = *p; *p = *q; *q = buf; return; } void QuickSort(int *a, int low, int high) { int i = low; int j = high; int key = a[low]; if (low >= high) //如果low >= high说明排序结束了 { return ; } while (low < high) //该while循环结束一次表示比较了一轮 { while (low < high && key <= a[high]) { --high; //向前寻找 } if (key > a[high]) { Swap(&a[low], &a[high]); ++low; } while (low < high && key >= a[low]) { ++low; //向后寻找 } if (key < a[low]) { Swap(&a[low], &a[high]); --high; } } QuickSort(a, i, low-1); //用同样的方式对分出来的左边的部分进行同上的做法 QuickSort(a, low+1, j); //用同样的方式对分出来的右边的部分进行同上的做法 }
输出结果是：
最终排序结果为:
-234 -70 -58 1 2 3 4 5 7 8 9 32 34 43 56 76 532 543 635 900 2500
