《算法图解》读书笔记 第四章 快速排序

分而治之

分而治之（D&C）是一种通用的问题解决方法。

D&C并非可用于解决问题的算法，而是一种解决问题的思路。我们经常用递归算法来实现分而治之。

使用D&C解决问题的过程包括两个步骤。

1. 找出基线条件，这种条件必须尽可能简单。
2. 不断将问题分解（或者说缩小规模），直到符合基线条件。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

快速排序

快速排序使用了D&C的策略。

快速排序是一种常用的排序算法，比选择排序快得多。

基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。

快速排序的步骤：

1. 选择基准值。
2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
3. 这两个子数组进行快速排序。

快速排序的代码：

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)

排序算法的运行时间比较：

• 选择排序的运行时间为O(n²)，速度非常慢。

• 合并排序的运行时间为O(n log n)。

• 快速排序在在平均情况下的运行时间为O(n log n)，在最糟情况下的运行时间为O(n²)。它遇上平均情况的可能性要比最糟情况大得多。

有时候，常量的影响可能很大，对快速排序和合并排序来说就是如此。快速排序和合并排序的运行时间都为O(n log n)，但快速排序的常量比合并排序小，因此快速排序的速度将更快。（为什么快速排序的常量比归并排序小？）

小结

• D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
• 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)快得多。