快速排序

文章目录

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

分而治之思想 (Divide and Conquer)

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

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

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

概念

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

原理

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

图示

快速排序算法

复杂度

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

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

TODO

  • 三分法排序

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

  • 三路基数快排

更多

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