开发者社区> 问答> 正文

如何使用合并排序算法进行就地排序?

我知道这个问题不太具体。

我想要的是有人告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序)。

我只能在网上找到说“它太复杂”或“超出本文范围”的页面。

唯一已知的就地合并(没有任何额外空间)的方法过于复杂,无法简化为实际程序。(从这里拍摄)

即使太复杂,如何进行合并排序的基本概念是什么?

展开
收起
保持可爱mmm 2020-01-16 15:46:49 395 0
1 条回答
写回答
取消 提交回答
  • 这确实不是容易或高效的,并且我建议您除非确实需要,否则不要这样做(并且除非您是家庭作业,否则您可能不必这样做,因为就地合并的应用大部分是理论上的)。您不能使用quicksort吗?无论如何,Quicksort都会通过一些更简单的优化而更快,并且其额外的内存为O(log N)。

    无论如何,如果必须这样做,那么就必须这样做。这是我发现的:一和二。我不熟悉就地合并排序,但似乎基本的想法是使用旋转方便地合并两个数组,而无需使用额外的内存。

    请注意,这比没有适当位置的经典合并排序要慢。 问题来源于stack overflow

    2020-01-16 15:47:10
    赞同 展开评论 打赏
问答分类:
问答地址:
相关产品:
问答排行榜
最热
最新

相关电子书

更多
图解算法小抄 立即下载
低代码开发师(初级)实战教程 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载