我正在尝试创建一个非常节省空间的不寻常的关联数组实现,我需要一个满足以下所有条件的排序算法:
- 稳定(不改变具有等键的元素的相对顺序。)
- 就地或几乎就地(O(log n) 堆栈很好,但没有 O(n) 空间使用或堆分配。
- O(n log n) 时间复杂度。
另请注意,待排序的数据结构是一个数组。
很容易看出有一个基本算法可以匹配这三个中的任意两个(插入排序匹配 1 和 2,归并排序匹配 1 和 3,堆排序匹配 2 和 3),但我一辈子都做不到找到符合所有这三个条件的任何内容。
最佳答案
我相信合并排序可以写成就地。这可能是最好的路线。
关于algorithm - 稳定、高效的排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/113025/