在基于比较的排序算法中，归并排序与堆排序在最坏时间复杂度也能达到O(nlgn)，快速排序的平均时间复杂度是O(nlgn)。所以，基于比较的排序算法，O(nlgn)是最好表现。然而，基于非比较的排序算法的时间复杂度能达到O(n)。下面，我们介绍三个非比较的排序算法。

计数排序

计数排序是稳定的排序算法，基数排序中使用到了该排序算法。

基数排序

基数排序的思想: 首先使用最低关键字排序，然后再使用次低关键字，直到最高关键字。这样经过n次时间复杂度为O(n)的排序得到最后结果。

引用场景: 对于基于n个关键字的排序最有效

相关问题:

1. 对于大数的排序

桶排序

桶排序的思想: 首先，分配n个桶，将数据映射到桶中，然后再对桶中的数据进行排序(或继续使用桶排序算法或其他排序算法)。最后，将所有的桶中的数据串联起来，得到最后的结果。

应用场景: 对于海量且范围有限的数据进行排序最有效。

相关问题:

1. 一年的高考人数为500万，分数使用标准分，最低100，最高999，没有小数，要求对所有的分数进行排序。
2. 在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。