原文地址：快速排序优化详解
正如它的名字所体现，快速排序是在实践中最快的已知排序算法，平均运行时间为O(NlogN)，最坏的运行时间为O(N^2)。算法的基本思想很简单，然而想要写出一个高效的快速排序算法并不是那么简单。基准的选择，元素的分割等都至关重要，如果你不清楚如何优化快速排序算法，本文你不该错过。
算法思想
快速排序利用了分治的策略。而分治的基本基本思想是：将原问题划分为若干与原问题类似子问题，解决这些子问题，将子问题的解组成原问题的解。
那么如何利用分治的思想对数据进行排序呢？假如有一个元素集合A：
- 选择A中的任意一个元素pivot，该元素作为基准
- 将小于基准的元素移到左边，大于基准的元素移到右边（分区操作）
- A被pivot分为两部分，继续对剩下的两部分做同样的处理
- 直到所有子集元素不再需要进行上述步骤
可以看到算法思想比较简单，然而上述步骤实际又该如何处理呢？
如何选择基准
实际上无论怎么选择基准，都不会影响排序结果，但是不同的选择却可能影响整体排序时间，因为基准选择不同，会导致分割的两个集合大小不同，如果分割之后，两个集合大小是几乎相等的，那么我们整体分割的次数显然也会减少，这样整体耗费的时间也相应降低。我们来看一下有哪些可选择策略。
选择第一个或者最后一个
如果待排序数是随机的，那么选择第一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就会产生一个很糟糕的分割。几乎所有的数据都被分割到一个集合中，而另一个集合没有数据。这样的情况下，时间花费了，却没有做太多实事。而它的时间复杂度就是最差的情况O(N^2)。因此这种策略是绝对不推荐的。
随机选择
随机选择基准是一种比较安全的做法。因为它不会总是产生劣质的分割。
C语言实现参考：
ElementType randomPivot(ElementType A[],int start,int end)
{
srand(time(NULL))
int randIndex = rand()%(end -start)+start;
return A[randIndex];
}
选择三数中值
从前面的描述我们知道，如果能够选择到数据的中值，那是最好的，因为它能够将集合近乎等分为二。但是很多时候很难算出中值，并且会耗费计算时间。因此我们随机选取三个元素，并用它们的中值作为整个数据中值的估计值。在这里，我们选择最左端，最右端和中间位置的三个元素的中值作为基准。
假如有以下数组：
1 9 10 3 8 7 6 2 4
左端元素为1，位置为0，右端元素为4，位置为8，则中间位置为[0+8]/2=4，中间元素为8。那么三数中值就为4（1，4，8的中值）。
如何将元素移动到基准两侧
选好基准之后，如何将元素移动到基准两侧呢？通常的做法如下：
- 将基准元素与最后的元素交换，使得基准元素不在被分割的数据范围
- i和j分别从第一个元素和倒数第二个元素开始。i在j的左边时，将i右移，直到发现大于等于基准的元素，然后将j左移，直到发现小于等于基准的元素。i和j停止时，元素互换。这样就把大于等于基准的移到了右边，小于等于基准的移到了左边
- 重复上面的步骤，直到i和j交错
- 将基准元素与i所指向的元素交换，使得基准元素将整个元素集合分割为小于基准和大于基准的元素集合
在们采用三数中值得方法选择基准的情况下，既然基准是中值，实际上只要保证左端，右端，中间值是从小到大即可。还是以前面提到的数组为例，我们找到三者后，对三者进行排序如下：
排序前
| ↓ | ↓ | ↓ | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 9 | 10 | 3 | 8 | 7 | 6 | 2 | 4 |
排序后
| ↓ | ↓ | ↓ | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 9 | 10 | 3 | 4 | 7 | 6 | 2 | 8 |
如果是这样的情况，那么实际上不需要把基准元素和最后一个元素交换，而只需要和倒数第二个元素交换即可，因为最后一个元素肯定大于基准，这样可以减少交换次数。
如果前面的描述还不清楚，我们看一看实际中一趟完整的流程是什么样的。
第一步，将左端，右端和中间值排序，中值作为基准：
| ↓ | ↓ | ↓ | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 9 | 10 | 3 | 4 | 7 | 6 | 2 | 8 |
| 基准 |
第二步，将中值与倒数第二个数交换位置：
| 交 | 换 | 位 | 置 | |||||
|---|---|---|---|---|---|---|---|---|
| ↓ | ↓ | |||||||
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| 基准 |
第三步，i向右移动，直到发现大于等于基准的元素9：
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基准 |
第四步，j向左移动，直到发现小于等于基准的元素2：
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基准 |
第五步，交换i和j：
| 1 | 2 | 10 | 3 | 9 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | 交 | 换 | j | 基准 |
第六步，重复上述步骤，i右移，j左移：
| 1 | 2 |
| 首页 上一页 1 2 3 4 5 6 7 下一页 尾页 1/7/7 | |
| 【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】 | |
| 上一篇：我们对于年轻人的无奈，那些米上.. | 下一篇：循环左移 |