算法和数据结构2.6快速排序

快速排序

快速排序会在序列中随机选择一个基准值（pivot）,然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成如下的形式。

[比基准值小的数] 基准值 [比基准值大的数]

接下来对两个[]中的数据也按照这个方法来进行排序之后，整个排序就完成了。

基本步骤：

比如要对 如下数据进行排序

3 5 8 1 2 9 4 7 6

在序列中随机选择一个基准值4.

将所有数字和4 进行比较，小于基准值的左移，大于基准值的右移。

首先3 < 4

5 8 1 2 9 4 7 6

[3]  4  [ ]

5 > 4

8 1 2 9 4 7 6

[3]  4  [5  ]

8 > 4

1 2 9 4 7 6

[3]  4  [5  8 ]

1 < 4

2 9 4 7 6

[3 1]  4  [5  8 ]

排序中...

[3 1 2] 4 [5 8 9 7 6]

接下来看左边的数字序列

[3  1  2]

随机选择一个基准值3

[1,2]
[] 3 []

因为1 < 3 ，

[2]
[1] 3 []

因为2 < 3,

[1 2] 3 [] 

接下来排序下面序列

[1,2]

随机选择一个基准值1

[2]
[]1[]

因为2> 1

[]1[2]

左侧排序完成

[[]1[2]] 3 []

同理可以得到右侧的排序结果。

整体的排序工作就完成了。

快速排序是一种分治法。它将原本的问题分成两个子问题。比基准值小的数和比基准值大的数然后再分别解决这两个问题。子问题，也就是子序列完成排序之后，再合并成一个序列，那么对原始序列的排序就完成了。

解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。

算法内部继续使用该算法的现象被称为“递归”。

时间计算：

分割子序列需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原来的一半，那么快速排序和归并排序的时间一样，都为O（nlogn）。

和归并排序类似，将序列对半分割log₂n次之后，子序列里便只剩下一个数据，这时子序列的排序就完成了。

因此，如果一行行的展示根据基准值来分割序列的过程，那么总共会有log₂行。

每行中每个数字都要和基准值比较大小，因此每行所需要的运行时间为O(n)。由此可知，整体的时间复杂度为O(nlogn).

如果运气不好，每次选择最小的值作为基准值，那么每次都需要把其他数据移动到基准值的右边，递归执行n行，运行时间也就成了O(n²).
这就相当于每次都选出最小值，并把它移动到左边，这个操作也就和选择排序一样了。

此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间就是O(nlogn).