快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
1. 从序列中挑出一个元素，作为"基准"(pivot).
2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3. 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
#include <stdio.h> // 交换函数 void swap (int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } // 打印数组 void printA (int *a, int len) { int i; for (i = 0; i < len; i++) { printf ("M", a[i]); } printf ("\n"); } // 分区操作，返回基准值的下标 int partition(int *a, int left, int right) { int pivot = a[right]; int index = left; // 如果找到一个比基准值小的元素，与下标为index的元素交换 int i; for (i = left; i < right; i++) { if (a[i] < pivot) { swap (a, i, index); index++; } } swap (a, index, right); return index; // 基准值所在位置下标 } void qSort(int *a, int left, int right) { if (left < right) { int pivot = partition(a, left, right); // 进行分区操作，找基准值下标 qSort (a, left, pivot-1); // 对左边部分进行快速排序 qSort (a, pivot+1, right); // 对右边部分进行快速排序 } } int main() { int a[10] = {9,6,8,0,3,1,2,4,7,5}; int len = sizeof(a) / sizeof(a[0]); qSort (a, 0, len-1); printA (a, len); return 0; }
