本文介绍了就地归并排序实际用法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我试着到处搜索，以找出到底什么是就地合并排序，以及我需要在哪里使用它？但没有找到一个直接的答案。请在下面回答以帮助我。 1)何时何地需要就地合并？就地合并的实际用法。2)如果未对就地合并的输入数组进行排序，会发生什么情况？
3)在合并排序、就地合并排序和快速排序中，哪种排序占用的内存更多？
注意：我问的是关于"std：：inplace_merge"的问题，这是一种stl算法。
推荐答案
1)如果要在O(Nlogn)时间内对列表进行排序，而使用的空间比标准合并排序少，则使用就地合并排序。
2)排序的全部目的是对输入数组进行排序，因此未排序的输入数组将按就地合并排序。
3)Mergesort使用更多内存，因为它为两个递归调用创建了两个大小减半的新数组。就地合并排序和快速排序应该占用相同的空间，因为它们都是就地排序。对于合并排序，In-Place意味着保留长度为n的数组的相关索引的O(Logn)额外空间，而不是最严格的In-Place的O(1)含义。快速排序在最坏的情况下会占用O(Nlogn)个额外空间，因为可能有O(N)个递归调用，每个递归调用都有占用O(Logn)空间的指针。希望这能有所帮助。
这篇关于就地归并排序实际用法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！
本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除！