证明：所有基于比较模型（comparison model 通过比较两个元素的大小以确定元素的位置）的排序算法的运算速度不会快于O(nlogn)
比如快速排序（nlogn），堆排序（nlogn），归并排序（nlogn），插入排序（n2）……等等，都是基于比较模型
为了证明该结论，引入决策树这个工具
例如，假设要排序三个元素，a,b,c , 构造的决策树如下所示
a > b?
/ \
b>c? a>c?
/ \ / \
a,b,c a>c? b,a,c b>c?
/ \ / \
a,c,b c,a,b b,c,a c,b,a
其中的每个节点表示一次比较，最后的叶子节点表示所有可能的比较结果，因此，决策树的定义如下：
假设待排序<a1,a2,a3…………an>长度为n
1、树种的每个非叶节点都会有两个下标 i , j ( 1<= i,j <=n ) ,表示要比较ai和aj的大小
2、每个非叶节点会分裂成两个子树，其中左边的子树说明ai<=aj的情况下的后续情况，右侧子树说明ai>aj情况下的后续情况
3、每个叶子节点表示一种排序结果情况
这样的决策树就是一个二叉树，所有基于比较模型的排序算法都可以转换成决策树模型的方式，现在用决策树来处理比较排序
1、为待排序列n构造一个决策树
2、在进行比较时，将树分成两个分支左子树和右子树。决策树就是把算法中这些比较的所有可能的结果分别列出来，指出了所有可能的路线
这样，对于长度为n的待排序列，根据排列组合原理，总的可能的排序结果有n!个，由此可见决策树增长很快（指数级），这也是为什么一般不用决策树来描述算法，不够简洁。不过用决策树来进行算法分析的话就很有用了，决策树代表了算法执行的所有可能，如果找出一条特定的算法执行路径，即一条从跟节点到叶子节点的路径
路径的深度=算法运行时间
树的高度=算法的最坏运行时间
现在，就需要证明树的高度至少是nlogn，即如果决策树对n个元素排序，则该决策树的高度至少是nlogn
已知：决策树的叶子节点数为n!个，根据二叉树的性质可知，对于一个高度为h的二叉树，其叶子节点数最多为2h个，即可得到一个不等式
n!≤2h
两边取对数，得到
h≥logn!
由可知
h≥logn!
≥log(n/e)n
=nlogn-nloge=O(nlogn) 证毕
同样可以证明，在加入随机化过程的比较模型中，也要至少经过nlogn次比较。
因此，想要得到线性速度的排序算法（不能比线性速度更快了，因为无论如何都要遍历一遍排序序列），就必须舍弃基于比较的模型，而是对元素做一些其他的操作。
计数排序（counting sort）
计数排序是一个线性时间的排序算法，算法如下：
1、待排序列A <a1,a2,a3……an>长度为n
2、序列中的每个元素ai的数值范围都在[1,k]之间，实际的运行时间也会依赖于k
3、排好序后的序列存放到B <b1,b2,b3……bn>中，同时需要一个长度为k的辅助存储序列C <c1,c2,c3……ck>
void CountingSort(int A[],int B[],int n) { int C[k]; int i; for(i=0;i =0;i--){ B[C[A[i]]] = A[i]; C[A[i]] -=1; } } 唔，很简洁，也很令人迷惑，举例如下：
假设A=[4,1,3,4,3] 可见数组中的元素最大不超过4，于是k=5(从0到4)，因此初始化C=[0,0,0,0,0]
然后循环序列A，并对C中的元素赋值，整个过程如下
C=[0,0,0,0,1]
C=[0,1,0,0,1]
C=[0,1,0,1,1]
C=[0,1,0,1,2]
C=[0,1,0,2,2]
然后循环序列C，求和
C=[0,1,0,2,2]
C=[0,1,1,2,2]
C=[0,1,1,3,2]
C=[0,1,1,3,5]
最后得到的序列C表示，总共有5个元素，其中小于等于3的有3个，小于等于2的有1个，小于等于1的有1个，小于等于0的没有。
最后一个循环得到结果序列B
A=[4,1,3,4,3] , B=[ , , , , ] , C=[0,1,1,3,5]
i=4 , A[i]=3 , C[A[i]]-1=C[3]-1=2 , B[C[A[i]]-1]=B[2]=3 , B=[ , ,3, , ] , C=[0,1,1,2,5]
i=3 , A[i]=4 , C[A[i]]-1=C[4]-1=4 , B[C[A[i]]-1]=B[3]=4 , B=[ , ,3, ,4] , C=[0,1,1,2,4]
i=2 , A[i]=3 , C[A[i]]-1=C[3]-1=1 , B[C[A[i]]-1]=B[1]=3 , B=[ ,3,3, ,4] , C=[0,1,1,1,4]
i=1 , A[i]=1 , C[A[i]]-1=C[1]-1=0 , B[C[A[i]]-1]=B[0]=1 , B=[1,3,3, ,4] , C=[0,0,1,1,4]
i=0 , A[i]=4 , C[A[i]]-1=C[4]-1=3 , B[C[A[i]]-1]=B[3]=4 , B=[1,3,3,4,4] , C=[0,0,1,1,3]
运行时间T(n)=O(k)+O(n)+O(k)+O(n)=O(k+n)
因此，当k比较小的话（K<n），则T(n)=O(n)。
在实际场景中，如果要处理的数据大小很小，比如只有一个字节的话，那么k=256,那么这个算法就很快了O(256+n)
而如果要处理的数据是一些32位的整形数据的话，那么k=232=4G，那么辅助数组C就需要4G*4B=16GB的内存空间，光初始化数组C就得费老大劲了，况且谁有16G内存的电脑可供挥霍呢……
这儿计数排序有一个很重要的特点：
即待排序列中相等元素在排序过后的相对位置保持不变。计数排序就是一个稳定的排序，可以看到原序列中有两个3和两个4，排序前位置靠前的3和4在排序后位置依然靠前。基数排序就是基于稳定的计数排序，也是一个线性时间的排序算法。
基数排序
基数排序是最古老的排序方法之一，大约出现于1890年由Herman Hollerith发明。Herman发明了最早版本的打孔机和卡片制表系统，在1890年的时候，美国的人口普查是一件很艰难的工作，Herman利用他的发明的制表系统帮助美国政府统计人口，赚了很大一笔钱，他的公司后来发展成现在的IBM。由此可见，科技真是第一生产力。
Herman在他的制表系统中使用的排序方法是：使用一种稳定的排序算法先对n个数的最低位进行排序，然后对n个数的次低位进行排序，按照这样的顺序排序下去，最后给n个数的最高位进行排序，这样这n个数就整体有序了。（低位优先排序法）
即整个算法的排序思想就是按位排序，从最低位排到最高位，想出这个算法的人真是个天才。例如对下面7个数排序：
329 720 720 329
457 355 329 355
657 436 436 436
839 -->457-->839-->457
436 657 355 657
720 329 457 720
355 839 657 839
最后结果就是有序的了，现在证明其正确性：
1、对已排序的部分按照数字位进行归纳，记为t，即通过归纳假设在t之前的t-1位已经排序
2、然后对t位排序。
3、排序过程中，如果有两个元素是相同的，即有相同的第t位数字，基于稳定性原则，那么就不能交换其顺序。根据归纳假设可知这t位仍然保持有序
4、如果有不同的第t位数字，那么排序过程就将他们调整为正确的顺序，由此得到有序的序列，那么这t位依然保持有序（高位大，无论低位如何，数就是大的）。证毕
使用计数排序作为辅助算法来实现基数排序，这样便克服了计数排序无法排序数据范围比较大的数的缺点，同时保证了线性的时间复杂度。
比如，对于n个32位的整数，可以将这32位的数分为4个部分，每个部分8位，然后使用计数排序分别对这4个部分进行排序即可。
那么，对于n个b位的整数，如何进行划分才能获得最大效率呢？
假设将b位的整数划分为b/r个部分，每个部分有r位，用计数排序对r位数据进行排序，可知k=2r,计数排序花费时间为O(2r+n)，总共需要进行b/r轮的计数排序，则总用时为：
T(n)=O[b/r(2r+n)]
其中的r是为我们所掌控的，通过选择适当的r来减少运行时间。想要得到线性的运行时间，只需要
(b/r)*2r ≤ (b/r)n
就可以了，这样对于O符号就可以忽略低阶项，两边取对数，得
r ≤ logn
取r=logn带入T(n)，同时忽略低阶项得
T(n)=O(bn/logn)
其中b表示整数的位数，整数的表示范围为2b-1，同时也可以表示为nd-1，两边取对数得到
b=dlogn
带入T(n)得到
T(n)=O(d*n)
其中d是一个常数，只要d<logn，那么整个的排序速度就比nlogn的比较模型的排序算法速度快了