快速排序里的学问：枢纽元选择与算法效率

每一练习都是一次积淀，终将成就不一样的自己。下面是小编整理的快速排序里的学问之枢纽元选择与算法效率，希望对大家有用，更多消息请关注应届毕业生网。

选择首尾元素做枢纽元

通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。选择第一个元素作为枢纽元的程序例子可以参考专题的前一篇《快速排序里的学问：霍尔快排的实现》，而选择最后一个元素用作枢纽元的程序例子则可以参考《快速排序里的学问：快速排序的过程》这个算法导论里的例子。

选择最后一个元素作为枢纽元的排序过程是这样的：

如果输入是随机的，那么这是可以接受的，但是如果输入是预排序的或者是反序的，那么这样的枢纽元就产生一个劣质的分割，因为所有的元素不是被划入S1就是被划入S2。更有甚者，这种情况发生在所有的递归调用中。

实际上，如果第一个元素用作枢纽元而且输入是预先排序的，那么快速排序所花费的时间将是二次的。然而，预排序的输入(或者有一大段预排序数据的输入)也是相当常见的，因此，使用第一个元素作为枢纽元的算法效率不是很高的。

另一种想法是选取前两个互异的键中的较大者作为枢纽元，但这和只选取第一个元素作为枢纽元效率也差不多。

随机选取枢纽元

一种安全的方针是随机选取枢纽元。

一般来说这种策略非常安全，除非随机数生成器有问题，因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面，随机数的生成一般是昂贵的，根本减少不了算法其余部分的平均运行时间。

三数中分割法

一组N个数的中值是第[N/2]个最大的数。枢纽元的最好的选择是数组的中值。

可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机*并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形。

这种枢纽元选择的的快排，效率可是相当高的。

快速排序还很有很多各种变种，我们这里只研究几个有代表*的算法。

• c#快速排序算法

  大家知道c#快速排序算法是怎么样的吗？下面小编为大家整理了c#快速排序算法，希望能帮到大家！快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。步骤为：1.从数列中挑出一个...

• C#排序算法之快速排序

  C#排序算法怎样快速排序呢？下面小编为大家整理了C#排序算法之快速排序，希望能帮到大家！快速排序实现:复制代码代码如下:namespaceQuickSort{classQuickSort{publicstaticvoidSort(int[]...

• PHP快速排序算法解析

  天才是百分之一的灵感，百分之九十九的血汗。以下是小编为大家搜索整理的PHP快速排序算法解析，希望能给大家带来帮助!更多精彩内容请及时关注我们应届毕业生考试网!快速排序算法是对冒泡算法的一个优化。他的思想是先对数组进行分割，把大的元素数值放到...

• PHP 快速排序算法解析

  快速排序之所以称之快速是因为冒泡排序是每次对比只交换相邻的两个值的位置，这样每个值要移动到它最终的排序结果中所对应的位置，可能需要很多次位置的变化。下面小编给大家讲述的是PHP快速排序算法，欢迎阅读，更多详情请关注应届毕业生考试网。快速排序...

• C++选择排序算法实例

  选择排序是一种简单直观的排序算法，下面小编为大家整理了C++选择排序算法实例，希望能帮到大家！选择排序是一种简单直观的排序算法，它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续...