线性时间排序

在讲线性时间排序之前，首先可以按照时间复杂度进行分类：

• O(n²) ：冒泡排序、插入排序、选择排序、希尔排序；
• O(n log n)：归并排序、快速排序、堆排序；
• O(n)：计数排序、基数排序、桶排序；

其中，时间复杂度为 O(n)的排序算法被称为线性时间排序，它与非线性时间排序最本质的区别在于，非线性时间排序在排序的过程中，各元素通过比较确定次序（这类排序算法也被称为比较排序），而线性排序算法并不是通过比较来确定排序顺序的，那么，它们是如何进行排序的呢？