学步园

1.决策树模型

比较排序的过程可以被抽象地视为决策树。一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较。排序算法的执行对应于遍历一条从树的根到叶节点的路径。每个内结点对应一个比较ai&aj，左子树决定着ai<=aj以后的比较，右子树决定着ai>aj以后的比较。当到达一个叶节点时，排序算法就已确定。排序算法能够正确工作的的必要条件是，n个元素的n！种排列都要作为决策树的一个叶节点出现。设决策树的高度为h，叶子数目为l，那么有 2^h>=l>=n!，于是有 h>lgn!
= Ω(nlgn)。 这说明比较排序的最坏时间复杂度为Ω(nlgn)。这也说明合并排序和堆排序的复杂度已经渐进最优了。

2.计数排序

假设n个输入元素的每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为Θ(n)。 计数排序的思想就是对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以把x直接放到最终输出数组的位置上。

假定输入是数组A[1...n], 存放排序结果的B[1...n]，以及提供计数临时存储的C[0...k]。

COUNTING-SORT(A,B,k)jk

1    for  i<- 0 to k

2        do C[i] i<- 0 //初始化临时存储数组

3    for j i<-1 to length[A]

4        do C[A[j]] =C[A[j]]+1

//到此时C[i]中数值表示A中等于i的元素个数

5    for i <-1 to k

6        do C[i] = C[i] + C[i-1]

//到此时C[i]中数值表示A中等于小鱼等于i的元素个数

7    for i <- length[A] downto 1

8        do B[C[A[i]] = A[i]

9             C[A[i]] = C[A[i]] -1  //important

第七行，从length[A] downto 1是为了正确解决由相同元素时的排序情况，保证算法稳定。若改为for
i<- 1 upto length[A]，则排序不稳定。

3.基数排序

基本思想：按组成关键字的各个位的值来实现排序的

基数：计算的基数就是基本的单元数。比如10进制的基数就是10，二进制的基数就2，八进制的基数是8等等。

基数排序说通俗点，就是把带排序的N个数字右对齐排成一列。然后把相同的位数互相比较，来排序