Can we do better than O(n lg n) running time for a comparison-based algorithm when all of the values are in the range 1 to k, where k < n.
当所有值都在1到k的范围内，其中k
Counting sort and radix sort are not comparison-based algorithms and are disallowed. By a decision tree analysis, it seems like there are k^n possible permutations. There are 2^h leaves, so it should be possible to solve the problem in O(n lg k) time with a comparison-based sorting algorithm.
计算排序和基数排序不是基于比较的算法，不允许使用。通过决策树分析，似乎存在k ^ n个可能的排列。有2 ^ h个叶子，因此应该可以用基于比较的排序算法解决O（n lg k）时间的问题。
Please do not give a non-comparison based sorting algorithm for solving this problem, all sorting must be based on comparisons between two elements. Thanks!
请不要给出基于非比较的排序算法来解决这个问题，所有排序必须基于两个元素之间的比较。谢谢！
3 个解决方案
#1
8
It may easily be done in the bound you specified. Build a binary tree of k leaves and include a count value on each leaf. Processing each element (adding it or bumping the count) will be O(lg k) if one uses a suitable balancing algorithm, so doing all of them will be O(n lg k). Reconstituting the list will then be O(n).
它可以很容易地在您指定的边界内完成。构建k叶的二叉树并在每个叶上包含计数值。如果使用合适的平衡算法，处理每个元素（添加或计算计数）将为O（lg k），因此所有元素都将为O（n lg k）。重新构成列表将是O（n）。
#2
4
Ok, if you insist you want comparisons.
好吧，如果你坚持要比较。
You have k elements. So, keep a tree structure that will hold all the elements.
你有k个元素。因此，保持一个可以容纳所有元素的树结构。
Go over the list of items, each time add the item to the tree. If the item is already in the tree, just increment the counter in that node. (or if you want the actual items you can keep a list in each node)
每次将项目添加到树中时，查看项目列表。如果项目已在树中，则只需递增该节点中的计数器。 （或者如果你想要实际的项目，你可以在每个节点中保留一个列表）
The tree will have no more than k items.
树将不超过k个项目。
in the end, go over the tree in an inorder way, and add the items back in the right order (while adding the amount that are in the node's counter).
最后，以顺序方式遍历树，并以正确的顺序添加项目（同时添加节点计数器中的数量）。
Complexity: O(nlogk)
复杂性：O（nlogk）
#3
0
Yes, you could use an array of size k. (Without comparisons)
是的，你可以使用大小为k的数组。 （没有比较）
Each cell i will contain a list.
go over the original array, put every item in the list of the right cell.
每个单元格我都会包含一个列表。遍历原始数组，将每个项目放在右侧单元格的列表中。
Go over the the second array, and pull them out, put them back in the right order.
翻过第二个数组，将它们拉出来，按正确的顺序放回去。
O(n)
上）
#1
8
It may easily be done in the bound you specified. Build a binary tree of k leaves and include a count value on each leaf. Processing each element (adding it or bumping the count) will be O(lg k) if one uses a suitable balancing algorithm, so doing all of them will be O(n lg k). Reconstituting the list will then be O(n).
它可以很容易地在您指定的边界内完成。构建k叶的二叉树并在每个叶上包含计数值。如果使用合适的平衡算法，处理每个元素（添加或计算计数）将为O（lg k），因此所有元素都将为O（n lg k）。重新构成列表将是O（n）。
#2
4
Ok, if you insist you want comparisons.
好吧，如果你坚持要比较。
You have k elements. So, keep a tree structure that will hold all the elements.
你有k个元素。因此，保持一个可以容纳所有元素的树结构。
Go over the list of items, each time add the item to the tree. If the item is already in the tree, just increment the counter in that node. (or if you want the actual items you can keep a list in each node)
每次将项目添加到树中时，查看项目列表。如果项目已在树中，则只需递增该节点中的计数器。 （或者如果你想要实际的项目，你可以在每个节点中保留一个列表）
The tree will have no more than k items.
树将不超过k个项目。
in the end, go over the tree in an inorder way, and add the items back in the right order (while adding the amount that are in the node's counter).
最后，以顺序方式遍历树，并以正确的顺序添加项目（同时添加节点计数器中的数量）。
Complexity: O(nlogk)
复杂性：O（nlogk）
#3
0
Yes, you could use an array of size k. (Without comparisons)
是的，你可以使用大小为k的数组。 （没有比较）
Each cell i will contain a list.
go over the original array, put every item in the list of the right cell.
每个单元格我都会包含一个列表。遍历原始数组，将每个项目放在右侧单元格的列表中。
Go over the the second array, and pull them out, put them back in the right order.
翻过第二个数组，将它们拉出来，按正确的顺序放回去。
O(n)
上）