快速排序的基本原理就是取序列中的一个值，使用一定的移动策略，最终使此值左侧小于该值，右侧大于该值，然后以此值为分界点使用前面的方法进行分治。下面我们直接给出代码，
1 int partition(int table[], int l, int r) 2 { 3 int i = l; 4 int j = r; 5 int x = table[l]; // x 选取的策略可以变更 6 while (i < j) 7 { 8 // 从最右侧开始查找比 x 小的值 9 while (i < j && x <= table[j]) 10 j--; 11 // 一旦找到，将此值扔到那个最开始取 x 的那个位置上，不过此处就留下了一个位置 12 if (i < j) 13 { 14 table[i] = table[j]; 15 i++; 16 } 17 18 // 从最左侧开始查找比 x 大的值 19 while (i < j && x >= table[i]) 20 i++; 21 // 一旦找到，将此值扔到上面留下来的位置上 22 if (i < j) 23 { 24 table[j] = table[i]; 25 j--; 26 } 27 } 28 29 table[i] = x; 30 return i; 31 }
1 void quick_sort(int table[], int l, int r) 2 { 3 if (l < r) 4 { 5 int i = partition(table, l, r); 6 // i 的左右两侧进行分治 7 quick_sort(table, l, i-1); 8 quick_sort(table, i+1, r); 9 } 10 }
可见最终要的过程为上面的 partition 方法，下面就此描述下这个过程，
1.下面是 table 的初始状态，蓝色代表 i 的位置，红色代表 j 的位置
2.执行 9~16 行
3.执行 19~26 行
4.执行 9~16 行
5.执行 19~26 行
6.执行 9~16 行（i == j）
7.执行 29 行
8.返回下标 3
整个过程就是两边向中间逼近，最后把取出来的值放回去。
另外参考值的选取可以使用随机的方法选取，或者取中间的，以应对不同分布的源数据。而且这个算法是递归的，可以在 quick_sort 函数中判断 l 和 r 距离不是很大时采用其他非递归的排序算法，如插入排序或者冒泡排序，避免递归过深。
原文：http://www.cnblogs.com/wendellyi/p/4888370.html