以上将的都是基于比较的排序，时间复杂度上界为O(n ^ 2)， 下界为O(nlogn)。下面介绍几种线性排序：
1、基数排序
基数排序是按照低位先排序，然后收集；再按照次低位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，它在每一位排序中依赖于一个稳定的排序算法，所以基数排序是稳定的排序算法。
给定n个d位数，其中每个数位有k个可能的取值。那么需要d轮排序，所以基数排序耗时为d(n + k)，而d为常数，所以基数排序复杂度为O(n + k)。
2、计数排序
假设n个输入元素中每个都是在0到k区间的整数(k是某个整数)。当k = O(n)时，排序的运行时间为O(n)。
3、桶排序
假设输入数据服从均匀分布，平均情况下其时间代价为O(n)。和计数排序类似，计数排序假设数据都是一个小区间内的整数，桶排序则假定输入由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间内。
桶排序将[0,1)区间划分为n个相同大小的子区间，称为桶；然后，将n个数分别放入到各个桶中，因为输入数据是均匀分布的，所以不会出现很多数落在一个桶内的情况。为了得到输出结果，先对每个桶中数进行排序（例如，利用插入排序），然后遍历每个桶，按照次序把各个桶内的元素列出来即可。