如何使用合并排序算法进行就地排序？
我知道这个问题不太具体。
我想要的是有人告诉我如何将普通合并排序转换为就地合并排序（或具有恒定额外空间开销的合并排序）。
我只能在网上找到说“它太复杂”或“超出本文范围”的页面。
唯一已知的就地合并（没有任何额外空间）的方法过于复杂，无法简化为实际程序。（从这里拍摄）
即使太复杂，如何进行合并排序的基本概念是什么？
展开
收起
1
条回答
写回答
写回答
-
这确实不是容易或高效的，并且我建议您除非确实需要，否则不要这样做（并且除非您是家庭作业，否则您可能不必这样做，因为就地合并的应用大部分是理论上的）。您不能使用quicksort吗？无论如何，Quicksort都会通过一些更简单的优化而更快，并且其额外的内存为O（log N）。
无论如何，如果必须这样做，那么就必须这样做。这是我发现的：一和二。我不熟悉就地合并排序，但似乎基本的想法是使用旋转方便地合并两个数组，而无需使用额外的内存。
请注意，这比没有适当位置的经典合并排序要慢。 问题来源于stack overflow
2020-01-16 15:47:10赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
