前言
本节课程讲述的内容如下：
- 快速排序（quicksort）算法的起源
- 快速排序算法描述
- 快速排序算法性能
起源
快速排序算法（以下简称快排）是一个名为 Tony Hoare 的人提出的。他当时在开发一个将英文翻译为俄文的程序，具体的实现思路是在遇见一个英文单词时利用二分查找算法在字典中查找该英文单词对应的俄文单词并进行相应的替换。
在理想的情况下，如果字典的长度是D，那么执行一次二分查找的时间复杂度是$\Theta(logD)$，所以将N个英文单词翻译为对应俄文单词的时间复杂度就为$\Theta(NlogD)$（执行N次二分查找）。然而现实并没有这么理想，因为字典信息存储在磁带上，所以从后面的单词跳到前面的单词就需要移动磁带，这会花费一定的时间，所以执行二分查找的时间复杂度并不是$O(logD)$。解决这个问题的办法就是让磁带不会来回移动而是一直往后走，实现该目标的措施就是事先排序英文句子，所以Tone Hoare就需要找到一个能够排序英文句子的算法，这就引出了快排。
算法描述
快排的核心是一个称为分区（partition）的操作，分区指的是选中数组的某个元素（这个被选中的元素成为pivot），经过一些步骤使得pivot左边的元素都小于等于pivot，而pivot右边的元素都大于等于pivot（这个过程中pivot在数组中的位置可能会也可能不会改变）。
课后习题
问：找到快排一个最坏情况下的输入（假设总选择最左边的元素作为pivot）
答：最坏情况出现在pivot分区后总落在数组的第一个位置，这种情况对应的输入可以是 [1, 2, 3, 4, 5]
问：快排在最好、最坏、平均情况下的递归深度是多少？
答：分区的次数和递归深度相等，假设总选择最左边的元素作为pivot，那么：
- 最好情况：最好情况下会进行$O(log^n)$次分区，所以最好情况下的递归深度是$O(log^n)$
- 最坏情况：最坏情况下会进行N次分区，所以最坏情况下的递归深度是$O(n)$
- 平均情况：$O(log^n)$
问：假设采用的分区策略是将元素分为3类：
- 小于pivot
- 等于pivot
- 大于pivot
假设该分区策略的运行时间是$\Theta(N)$，证明一个快排对一个长为N但仅有7个不同元素的数组的运行时间是$\Theta(N)$。（比如[0, 1, 0, 0, 6, 6, 5, 5, 4, 2, 2, 0, 3, 0, 1, …, 2, 6]）
由于每次分区至少都会排除一个键的所有元素，所以最多会进行7次分区。
问：找到一个使得Arrays.sort 崩溃（crash）的整型数组。Arrays.sort(int[])使用的排序算法是快排。更多细节参阅 A Killer Adversary for Quicksort。
答：一个使得Arrays.sort崩溃的输入必然是由于快排的性能过差导致的，根据讲义可以知道，快排性能退化的原因是分区后pivot落在了导致左右两个子数组长度极不均衡的位置，这会导致分区次数的增加从而对性能产生影响。所以现在要找到一个使得分区落点不平衡的输入，关键的问题是如何找到？
之前的问题可以知道快排对近乎有序的数组性能很差，但在构造一个很大的有序数组并传给Arrays.sort后程序并没有崩溃，猜测内部做了一些优化。看起来必须依照论文给出的方法构造输入。