雪糕乐
2019年07月16日
若是没有n的取值区间超过内存大小这个限制，可以简单的用hash统计次数，排序再还原即可，即使用计数排序。
否则，因为是数字排序，可以使用基数排序，运行时间相对计数排序来说要多一点，但是都是同一级别O(n)。
即计数排序只需扫描一遍原数组，而基数排序需要扫描k遍，k为n个数中最大那个数十进制下包含的位数。显然
在确定的机器下，k是小于某个常数的。
1
1
allen
回复 雪糕乐的评论：hash和期数排序有什么关系
回复