线性时间排序算法
给定含n个元素的输入序列，任何比较排序在最坏情况下都需要Ω(nlogn)次比较来进行排序。合并排序和堆排序在最坏情况下达到上界O(nlogn)，它们都是渐进最优的排序算法，快速排序在平均情况下达到上界O(nlogn)。
本文介绍的三种以线性时间运行的算法：计数排序、基数排序和桶排序，都用非比较的一些操作来确定排序顺序。因此，下界Ω(nlogn)对它们是不适用的。
计数排序（CountingSort）假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。
计数排序的基本思想就是对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组中的位置上。
算法描述
算法的步骤如下：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组，将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1；
算法复杂度
最差时间复杂度O(n+k)
平均时间复杂度O(n+k)
最差空间复杂度O(n+k)
计数排序不是比较排序，排序的速度快于任何比较排序算法。
计数排序的一个重要性质就是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的次序相同。
之所以说计数排序的稳定性非常重要，还有一个原因是因为计数排序经常用作基数排序算法的一个子过程，其稳定性对于基数排序的正确性来说非常关键。
基数排序（RadixSort）
基数排序（RadixSort）是一种非比较型整数排序算法，其原理是将整数值按相同的有效位进行分组，然后在有效位区间内进行排序。
算法描述
每个元素值首先被放入一个该值的最右位所对应的桶中，桶内会保持被放入元素值最初的顺序。这使得桶的数量和值的数量能够根据其最右位建立一对一的关系。然后，通过相同的方式重复处理下一位，直到所有的位都已被处理。
获得值的最右侧的最小的位。
根据该位的值将数组内的元素值进行分组，但仍然保持元素的顺序。(以此来保持算法稳定性)
重复上述分组过程，直到所有的位都已被处理。
结束语：以上就是关于线性时间排序算法的全部内容，更多内容请关注学步园。