排序笔记

排序分为两种，一种是基于比较的排序，如插入排序、快速排序、归并排序等等，这类算法比较常见，但他们的时间复杂度都无法突破下界 O(nlgn)。



另外一种是非基于比较的算法，如计数排序、基数排序、桶排序，他们的时间复杂度可以达到 O(n)，是因为算法假设了数据拥有某种分布特性，如范围，如均匀分布等等。



基于比较的排序，时间复杂度的下界是O(nlgn)



快速排序



• 最坏运行时间复杂度是 Θ(n2)，期望运行时间复杂度是 Ο(nlgn) ，并且隐含的常数因子非常小，随机算法的运行时间成为期望运行时间

• 快速排序是原址的（即空间复杂度为 O(1) ）

• 快速排序是不稳定的

• 核心思想是分治法

• 运行时间依赖于划分是否平衡，而划分是否平衡又依赖于用于划分的元素如果划分是最坏情况时（数组本身已经是完全有序的，会被划分成两个分别包含了 n-1 个 元素 和 0 个元素的数组），快速排序的复杂度将是 Θ(n2)，而同样情况下，插入排序的运行时间复杂度却只有 Ο(n)其余情况，不管是完全平均的划分，还是是9：1的划分，任何一种常数比例的子问题划分都会产生深度为 Θ(lgn) 的递归树，每一层的时间代价都是 Ο(n)。因此，只要划分是常数比例的，算法的运行时间总是 Ο(nlgn)

• 我们无法控制算法的输入情况，但我们可以让随机发生在算法中。显式地对输入进行重新排列，使得算法实现随机化。因此，出现最坏情况的可能性几乎为 0。随机化的方式是主元不再一直选取子问题数组中的最后一个元素，而是先将最后一个元素与其它一个随机元素进行交换。



归并排序



• 将数组平均拆成左右两个子数组，依次递归调用自己，直到子数组长度为 1 ，之后再合并子数组。

• 归并排序是稳定的

• 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为 O(n)

• 对于最后的几个递归，可以进行优化。在子数组只有若干个元素的时候，直接使用插入排序而不是继续递归，能够略微提升性能。



堆排序

• 堆排序是不稳定的

• 堆是一个近似的完全二叉树，出了最底层，该树是完全充满的

• 保持一个树高为 h 的节点来说，保持这个节点的性质的时间复杂度是 O(h)

• 将一个数组构造成一个堆，需要 O(n) 次调用上述保持节点性质的方法，因此总时间复杂度是 O(nlgn)，但转换不是个紧确的上界，大部分节点实际的高度都很小，，因此将一个数组构建成堆（自底向上），更紧确的上界是 O(n)，证明：《算法导论 原书第三版》p88

• 堆排序是原址的

• 首先将数组构建成堆，之后每次交换堆顶元素和最后一个元素交换位置，再保持堆顶元素的性质，直至堆大小为 1 。（画外音：只需要完全建一次堆）





非基于比较的排序，需要数据拥有某种特性

计数排序

• 计数排序是稳定的

• 适用于n个输入都是 0 到 k 区间的整数，k是个正整数

• 需要一个临时数组 c[k]存放每个元素的出现次数，和一个输出数组b[n]，不会改变原数组

• 计数排序的时间复杂度是 O(k + n)，k 为初始化c[k] 的耗时

• 在工程上，当 k = O(n) 时一般使用计数排序，此时运行时间为 O(n)

• 计数排序不能排序负数，可以每个数都加上一个数使之成为正数，但意义不大

基数排序

• 基数排序是以计数排序为基础的，为了排序正确，计数排序必须是稳定的

• 从右往左按照数字的每一位进行排序，最大的数字有多少位，就需要进行多少轮排序

• n 个 k 位数，其中每一个数位有 k 个可能的取值 （k <= 10）。每一轮计数排序的耗时为 Θ(n + k)，那么基数排序就可以在 Θ( d(n + k) ) 时间内完成

桶排序

• 适用于数据服从均匀分布的情况，则平均情况下时间代价为O(n)

• 将数据按照范围均匀的分布在每一个桶中，然后对桶中的数据进行排序后再依次取出。每个桶可以选择自己的排序算法

• 桶内排序算法是稳定的，则桶排序就是稳定的

• 比较优秀的排序算法时间复杂度为O(nlgn)，使用 k 个桶，平均每个桶 n/k 个数据。O(n) 的时间找出数据的最大值最小值，从而判断各个桶的范围；O(n) 的时间将数据放到对应的桶中；k * O(n/k lg(n/k)) 的排序时间，O(n) 的时间将桶中的数据取出放到数组中。因此整体时间复杂度为 O(3n) + k * O(n/k lg(n/k))，k越大，复杂度越低，当 k = n 时，复杂度最低 为 O(3n) 即 O(n)，此时和计数排序也没什么区别了。