快速排序中的分割算法的解析与应用排序算法总结之快速排序

一，分割(partition)算法介绍

所谓分割算法，先选定一个枢轴元素，然后 将数组中的元素分成两部分：比枢轴元素小的部分都位于枢轴元素左边；比枢轴元素大的部分都位于枢轴元素右边

此时，枢轴元素在数组中的位置就被“永久地确定”下来了---将整个数组排序，该枢轴元素的位置不会变化。

另外，枢轴元素的选取对分割算法至关重要。一般而言，终极追求的是：将数组平分。因此，尽可能地让枢轴元素的选取随机化和靠近中位数。

这里采用“三数取中”法选取枢轴元素。

关于快速排序排序算法，可参考：http://www.cnblogs.com/hapjin/p/5518922.html

二，分割算法的实现

①第4行，枢轴元素是通过“三数取中”法选择的。在“三数取中”时，还做了一些优化：将 枢轴元素 放到 数组末尾的倒数第二个位置处。具体参考 media3()

需要注意的是：当输入的数组中长度为1 或者 2 时， partition会出现向下越界（但对快排而言，当数组长度很小的，其实可以不用 partition，而是直接用插入排序）。因此，可加入以下的修改。

再来看看，三数取中算法，这里也有个特殊情况：当数组中元素个数都没有3个时....怎么办？

这里提下第3-7行的两个if语句：当需要 “取中”的目标数组长度为1时，或者说 对数组中某些范围内[left, right]的元素进行“取中”时，若left=right，则根本就没有3个数，违背了“三数取中”的本意（随机地选取枢轴元素），故直接 return。

当数组中元素只有一个时，第18行会越界。为了防止这种情况，在第3-4行就先对数组长度进行判断。当数组中只有两个元素，其实就相当于 center=left，因此，程序也没问题。

三，分割算法的应用

给定一个数组，数组中某个元素出现的次数超过了数组大小的一半，找出这个元素。

比如输入：[2,5,4,4,5,5,5,6,5] ，输出 5

这个问题，其实可以转化成求解中位数问题。因为，当数组有序时，出现次数超过一半的那个元素一定位于数组的中间。

所谓中位数，就是 假设 数组是有序的情况下，中间那个元素。即 arr[arr.length/2]

而要求解中位数，当然可以先对数组进行排序，但排序的时间复杂度为O(NlogN)，那有没有更快的算法？

当然是有的。就是借助partition分割算法 来 实现。

上面算法不仅可以求解“找出超过一半的数字”，也可以求解任何一个数组的中位数。

这里递归表达式 T(N)=T(N/2)+O(N)，O(N)表示将数组 分成两部分所花的代价。

故时间复杂度为O(N)

四，参考资料

 整个完整代码

本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5587014.html，如需转载请自行联系原作者