比较排序

对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:
批注 2019-09-04 010631.jpg

每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。

n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)

2^(h+1) ≥ n!  
h + 1 ≥ log2(n!)

log(n!) = O(nlogn)

证明:

不等式缩放

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

Stirling 近似

76029ac06006a23f29011873c13a7a64541c6acd.svg

a35e8e0205988cf8552eec558d121f764d7e4021.svg

计数排序

计数排序的思想是:在待排序序列中,如果我们能统计出有多少元素小于或等于某一个元素,我们也就知道了该元素的正确位置。
例如:有五个元素小于x,那么就把x放到第六位(对于相同的元素我们认为最早遇到小于后面遇到的)。

实现该算法我们需要三个数组,初始input,结果output和表示元素统计数的count数组。
下面为算法的伪代码:

count = array of k+1 zeros
for x in input:
   count[key(x)] += 1

total = 0
for i in 0, 1, ... k:
   count[i], total = total, count[i] + total

output = array of the same length as input
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1

return output

算法可视化

时间复杂度分析:假设在[0,k]的n个元素,数组初始化O(k),构造统计数组C是O(n),统计数累加O(k),排序是O(n)
所以总共时间复杂度为O(k+n)

计数排序是一种典型空间换时间的算法。

性能比较

下面是JS中的性能对比:

Array with 10000000 elements:
n log(n) takes 15.611 seconds
Linear takes 3.896 seconds

参考文章:
https://medium.com/free-code-camp/my-favorite-linear-time-sorting-algorithm-f82f88b5daa1