稳定,高效的排序？

Question

我正在尝试创建一个非常节省空间的不寻常的关联数组实现,我需要一个满足以下所有条件的排序算法:

1. 稳定(不会更改具有相同键的元素的相对顺序.)
2. 就地或几乎就地(O(log n)堆栈很好,但没有O(n)空间使用或堆分配.
3. O(n log n)时间复杂度.

另请注意,要排序的数据结构是一个数组.

很容易看出有一个基本的算法匹配这三个中的任何两个(插入排序匹配1和2,合并排序匹配1和3,堆排序匹配2和3),但我不能为我的生活找到任何东西匹配所有这三个标准.

Answer 1

合并排序可以写成就地我相信.这可能是最好的路线.

Answer 2

注意:标准快速排序不是 O(n log n)!在最坏的情况下,它可能需要花费O(n ^ 2)的时间.问题是你可能会转向远离中位数的元素,这样你的递归调用就会非常不平衡.

有一种方法可以解决这个问题,即谨慎选择一个保证或至少非常可能接近中位数的中位数.令人惊讶的是,您实际上可以在线性时间内找到确切的中位数,尽管在您的情况下,听起来您关心速度,所以我不建议这样做.

我认为最实用的方法是实现一个稳定的快速排序(它很容易保持稳定),但使用5个随机值的中位数作为每一步的枢轴.这使得您不太可能进行慢速排序,并且稳定.

顺便说一句,合并排序可以就地完成,尽管在原位和稳定两者都很棘手.

Answer 3

那么快速排序呢？

交换也可以做到这一点，根据你的条件可能会更“稳定”，但快速排序更快。