TsingHuaDSA-排序

该文章为清华大学数据结构与算法设计MOOC课程读书笔记.

1. 快速排序

1.1 思想

类似于merge sort，都是采用分而治之的思路。但是不同的是：

1. 在归并排序中主要思考的问题是：给出两个用递归已经sort好的数组，如何合并？（首递归）
2. 而对于快速排序而言，主要思考的问题在于：如何将给定的一个无序数组划分为两部分，使得这两部分相对来说有大小关系，然后再去递归。（尾递归）

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.
• 采用的基本排序方法：插入排序，因为其输入敏感性，对约有序的序列，效率越高。
• 步长序列的选择：