虽然“快速排序”被称为“拆分管理”，但很明显“拆分管理”这三个词不能很好地概括“快速排序”的所有步骤。 所以我对快速排序做了进一步的说明。 挖洞充填数分治法：
先看看实例吧。 定义请如下。 (如果能用自己的语言总结定义，将有助于代码的实现。
以排列为例，以区间的最初数量为基准数。
0123456789
7265788604283734885
初始情况下，i=0； j=9； X=a[i]=72
因为a[0]的数量已经存储在x中，所以可以理解为在数组a[0]中挖了一个洞，其他数据可以填充到这里。
从j开始先找比x小或等于x的数。 j=8时，满足条件，将a[8]挖出并填满前孔a[0]。 a[0]=a[8]； I； 这样就解决了坑a[0]，但有了新的坑a[8]。 我该怎么办？ 很简单。 再找个数字补上a[8]这个洞。 下次从I开始向后找大于x的数，i=3，满足条件后，挖出a[3]填满前面的洞。 a[8]=a[3]； j----；
数组如下所示。
0123456789
4865788604283738885
i=3； j=7； X=72
重复上面的步骤，先从后向前找，从前向后找。
从j开始找先，j=5，满足条件，挖出a[5]埋在前孔中，a[3]=a[5]； I；
从I开始找后面，i=5时，因为i==j退出。
此时，i=j=5，a[5]正好是上次挖的洞，所以把x填满a[5]。
数组如下所示。
0123456789
4865742607283738885
可见a[5]前面的数字都比它小，a[5]后面的数字都比它大。 因此，可以对a[0…4]和a[6…9]两个子区间重复上述步骤。
汇总了挖掘填充数的：
1.i=L； j=R； 挖出基准数形成第一个坑a[i]。
2.j--从后向前找一个比它小的数，找到后挖这个数埋在前孔a[i]中。
3.i从前到后找一个比那个大的数，找到后把这个数挖出来埋在前孔a[j]里。
重复执行2，3个步骤直到i==j，并将基准数填写在a[i]中。
根据这个总结，挖洞充填数的代码很容易实现：
intadjustarray(ints[]，intl，intr ) /返回调整后的基准数的位置({inti=l，j=r； intx=s[l]； //s[l]即s[i]为第一个凹坑while(I=x ) j----； if(I )
写再分配法的代码：
voidquick_sort1(ints[]，intl，intr ) {if ) l}
这样的代码显然不简洁。 整理一下那个组合吧。
//voidquick_sort(ints[]，intl，intr ) ) if ) l=x ) /从右向左小于第一个x的数量j----； if(I )
快速排序有很多改进版本，例如随机选择基准数，或者直接用其他方法对区间内的数据进行排序以减小递归深度。 感兴趣的奶酪可以更深入地研究。
注1、有些书是以中数为基准数的，实现这一点很方便。 直接把里面的数和第一个数交换就可以了。
作者： MoreWindows
译文： 3359 blog.csdn.net/more windows/article/details/6684558