该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 快速排序
1.1 思想
类似于merge sort，都是采用分而治之的思路。但是不同的是：
- 在归并排序中主要思考的问题是：给出两个用递归已经sort好的数组，如何合并？（首递归）
- 而对于快速排序而言，主要思考的问题在于：如何将给定的一个无序数组划分为两部分，使得这两部分相对来说有大小关系，然后再去递归。（尾递归）
1.2 如何划分(Partition)？
第一个问题：轴点（pivot）的选取
思路1：都取第一个。
思路2：随机洗牌之后取第一个。
思路2更好，因为在概率上更容易得到平衡划分。
第二个问题：如何根据轴点划分
两个指针两头逼近，必要时交换数据。
Partition
1.3 算法性能
- 不稳定
- 空间：常数
- 时间：与pivot的选取有关！
- 如果pivot的划分都很均衡，使得子问题都被划分为一半因此最好O(nlgn)。
- 如果pivot的划分都很不均衡，使得子问题的规模只被减少一点，因此最差O(n^2)
- 平均性能O(NlgN)
2. 排序引出的问题：选取问题
2.1 问题的特点
从一组大小可以相互比较的元素中，找到某一个满足某个条件的特殊元素。比如：
- 找第k个
- 找中位数median
- 找众数majority - 元素的个数超过总数一半
...
最naive的想法就是利用sorting，然后再进行选择。但是sort的效率算比较低的，最好也才O(nlgn)。因此需要更高效的方法！
2.2 求众数
思路一：利用中位数求众数
- 必要性：若存在众数，那它必然是中位数！
- 思路：求中位数 + 判断中位数是不是众数（遍历 + 统计个数）
- 问题：需要高效的求中位数方法
思路二：利用频繁数(mode)求中位数
- 必要性：若存在众数，那它必然是频繁数！
- 思路：求频繁数 + 判断频繁数是不是众数（遍历 + 统计个数）
- 问题：也需要高效的求频繁数方法
高效求解众数的思路：减而治之
- 关键：将求解众数问题规模减小
减而治之求众数
2.2 求第k个元素
思路一：排序
- 缺点：效率太低
思路二：利用一个极小堆MinHeap，不断取出。
- 思路：将所有元素建一个极小堆，然后一个一个取出，直到第k个
- 效率：也不高
min heap
思路三：利用一个极大堆MaxHeap，不断插入和移除。
- 思路：将k个元素建一个极大堆，然后在剩余的元素中一个先插入，再取出，直到最后一个插入。此时堆顶为全局第k大。
- 效率：取决于k的大小，也不高
-
理解：当第n次次插入时，堆顶元素是目前所见的倒数第n大数。因此当第n-k次插入时，堆顶为全局倒数第n - k大数，即顺数第k大。
max heap
思路四：利用一大一小堆
- 理解：利用堆顶比较之后的互换，保证在最后，有k - 1个元素不大于大堆顶的元素且有n-k个元素也不小于它。它即为第k大。
-
效率：worst case也还是不高
max heap + min heap
思路五：基于减而治之思想的quick-select
- 思想：利用quick select中的partition将问题规模减小
- 效率：最好O(n)，但是最差也会到O(n^2)
-
理解：最好每次问题规模可以减少一般(n + n/2 + n/4 + ... = O(n))；最坏每次问题规模只减少1(n + n-1 + n-2 + ... = O(n^2))
quick-select
思路六：基于减而治之思想的linear-select
- 思想：找中位数中的中位数！
- 效率：线性！
linear-select
3. 希尔排序
- 思路：根据步长序列(step sequence)，先进行大步长排序，再进行小步长排序，直到步长为1.
- 采用的基本排序方法：插入排序，因为其输入敏感性，对约有序的序列，效率越高。
- 步长序列的选择：
