使用Java代码对1到9个整数进行排序,范围从1到9

Question

给定1到9之间的100万个整数的集合.您如何以有效的方式对它们进行排序？

Input: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]  
Output: [1,2,2,3,4,4,5,5,5,6,6,7,8,8,9]

Answer 1

对于大输入,Java Collections.sort()使用TimSort,它运行在O(n log(n))上.如果你想让它运行得更快,那就说线性时间比你应该使用非基于比较的排序算法.

由于您的整数范围远小于要排序的项目数,因此这是Counting Sort的完美用法.

存在k = 9(范围从1-9)和N = 1 million.你的运行时间是O(k + N).