该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 快速排序
1.1 思想
类似于merge sort,都是采用分而治之的思路。但是不同的是:
- 在归并排序中主要思考的问题是:给出两个用递归已经sort好的数组,如何合并?(首递归)
- 而对于快速排序而言,主要思考的问题在于:如何将给定的一个无序数组划分为两部分,使得这两部分相对来说有大小关系,然后再去递归。(尾递归)
1.2 如何划分(Partition)?
第一个问题:轴点(pivot)的选取
思路1:都取第一个。
思路2:随机洗牌之后取第一个。
思路2更好,因为在概率上更容易得到平衡划分。
第二个问题:如何根据轴点划分
两个指针两头逼近,必要时交换数据。
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个
- 效率:也不高
思路三:利用一个极大堆MaxHeap,不断插入和移除。
- 思路:将k个元素建一个极大堆,然后在剩余的元素中一个先插入,再取出,直到最后一个插入。此时堆顶为全局第k大。
- 效率:取决于k的大小,也不高
-
理解:当第n次次插入时,堆顶元素是目前所见的倒数第n大数。因此当第n-k次插入时,堆顶为全局倒数第n - k大数,即顺数第k大。
思路四:利用一大一小堆
- 理解:利用堆顶比较之后的互换,保证在最后,有k - 1个元素不大于大堆顶的元素且有n-k个元素也不小于它。它即为第k大。
-
效率:worst case也还是不高
思路五:基于减而治之思想的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))
思路六:基于减而治之思想的linear-select
- 思想:找中位数中的中位数!
- 效率:线性!
3. 希尔排序
- 思路:根据步长序列(step sequence),先进行大步长排序,再进行小步长排序,直到步长为1.
- 采用的基本排序方法:插入排序,因为其输入敏感性,对约有序的序列,效率越高。
- 步长序列的选择: