use*_*866 10 sorting algorithm
当所有值都在1到k的范围内时,我们能否比O(n lg n)运行时间更好地进行基于比较的算法,其中k <n.
计算排序和基数排序不是基于比较的算法,不允许使用.通过决策树分析,似乎存在k ^ n个可能的排列.有2 ^ h个叶子,因此应该可以用基于比较的排序算法解决O(n lg k)时间的问题.
请不要给出基于非比较的排序算法来解决这个问题,所有排序必须基于两个元素之间的比较.谢谢!
它可以很容易地在您指定的边界内完成.构建k叶的二叉树并在每个叶上包含计数值.如果使用合适的平衡算法,处理每个元素(添加它或计算计数)将是O(lg k),因此所有这些元素都将是O(n lg k).重新构成列表将是O(n).
是的，您可以使用大小为 k 的数组。（没有比较）
每个单元格 i 将包含一个列表。
遍历原始数组，将每个项目放入右侧单元格的列表中。
检查第二个数组，将它们拉出来，然后按正确的顺序放回去。
在）