线性时间排序

我们拥有可以在O（n log n）时间内对“ n”个数字进行排序的排序算法。

合并排序和堆排序在最坏的情况下达到此上限, 而快速排序在平均情况下达到此上限。

合并排序, 快速排序和堆排序算法具有一个有趣的属性：它们确定的排序顺序仅基于输入元素之间的比较。我们称这种排序算法为“比较排序”。

有一些算法运行速度更快并且需要线性时间, 例如计数排序, 基数排序和存储桶排序, 但是它们需要对输入序列进行排序的特殊假设。

计数排序和基数排序假定输入由小范围内的整数组成。

“存储桶排序”假定在该时间间隔内均匀分布元素的随机过程生成输入。