快速排序

文章目录

1. 1. 分而治之思想 (Divide and Conquer)
2. 2. 概念
3. 3. 原理
4. 4. 图示
5. 5. 复杂度
6. 6. TODO
7. 7. 更多

在了解快排之前，先了解一种思想——分而治之。

分而治之思想 (Divide and Conquer)

很多有用的算法结构上是递归的，为了解决一个特定问题，算法一次或者多次递归调用其自身以解决若干子问题。 这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但是类似于原问题的子问题，递归求解这些子问题， 然后再合并这些问题的解来建立原问题的解。

分治法在每层递归时有三个步骤：

1. 分解原问题为若干子问题，这些子问题是原问题的规模最小的实例
2. 解决这些子问题，递归地求解这些子问题。当子问题的规模足够小，就可以直接求解（大白话来说就是一眼可以看出来结果的）
3. 合并这些子问题的解成原问题的解

概念

简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

原理

先找到一个比较基准，然后将列表中剩余元素与这个基准进行比较，如果小于该基准，则放在左边的序列；大于基准则放在右边；最后把三个序列按顺序连接起来。

图示

复杂度

最糟糕复杂度：O(n^2)；平均复杂度：O(n*log n)

由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

TODO

• 三分法排序

我们可以通过使用一种名为“三点取样”的方法，来尝试着降低不均匀分割的可能性。为了选择中值，我们要考虑列表中第一个、中间一个以及最后一个三个元素。这种方法在于当列表的第一项不趋于处于列表中间位置时，三个值的中间值将会是一个更好的中值选择。

• 三路基数快排

更多

快速排序最好，最坏，平均复杂度分析