快速排序

快速排序是一种常用的排序算法，比选择排序快得多。快速排序也用上了之前讲的 D&C 方法。

算法说明

下面将使用快速排序对包含一系列数字元素的数组进行排序。

• 假设数组为空或包含 1 个元素： 对于排序算法来说，最简单的数组就是空数组或者包含 1 个元素的数组。因为不需要对其进行任何操作就完成了排序的工作。所以可以将这种情况作为基线条件。

def quickSort(array):
    if len(array) < 2: # 基线条件
        return array

• 假设数组包含 2 个元素： 当数组包含 2 个元素时，排序也是简单的。只需要检查第一个元素是否比第二个元素小，如果不比第二个元素小，就交换两者位置。
• 假设数组包含 3 个元素： 当数组包含 3 个元素时，要怎么进行排序呢？此时可以应用 D&C，将数组拆解，直到符合基线条件。下面具体讲讲快速排序的工作原理。假设数组为 [33, 15, 10] 。 首先，从数组中选择 一个元素，这个元素被称为 基准值（pivot）。对于如何选择基准值，后面会再说明。暂时将数组的第一个元素作为基准值，即拿 33 作为基准值。 接下来，找出比基准值小的元素和比基准值大的元素。这时候被称为分区（partitioning）。现在有：
  • 一个由所有小于基准值的数字组成的子数组；- [15, 10]
  • 基准值；- [33]
  • 一个由所有大于基准值的数字组成的子数组。- [ ]，空数组

  这里只是进行了分区，得到的两个子数组还是无序的。如果这两个子数组都是有序的话，将会非常容易得到排序结果。此时排序方法为：左边的数组 [10, 15] + 基准值 [33] + 右边的数组 [ ]，得到最终结果为：[10, 15, 33]。但是如何对两个子数组进行排序呢？此时可以发现递归调用快速排序方法，就可以快速知道结果。

quickSort([15, 10]) + [33] + quickSort([ ])
> [10, 15, 33]

综上，对 3 个元素的数组进行快速排序的步骤如下： （1）选择基准值 （2）将数组分为两个子数组：小于基准值的数组和大于基准值的数组 （3）对这两个子数组进行快速排序

• 假设数组包含 3 个以上元素 根据归纳证明的原理，3 个元素以上的数组的快速排序方法也和 3 个元素的方法一样： （1）选择基准值 （2）将数组分为两个子数组：小于基准值的数组和大于基准值的数组 （3）对这两个子数组进行快速排序

Python 实现代码

def quickSort(array):
    if len(array) < 2:
        return array 
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        
        return quickSort(less) + [pivot] + quickSort(greater)

-------------------------------------------------------------
>>> quickSort([33, 15, 10])
[10, 15, 33]