就地归并排序实际用法

In-place merge sort practical usage(就地归并排序实际用法)

本文介绍了就地归并排序实际用法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我试着到处搜索,以找出到底什么是就地合并排序,以及我需要在哪里使用它?但没有找到一个直接的答案。请在下面回答以帮助我。 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)空间的指针。

希望这能有所帮助。

这篇关于就地归并排序实际用法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:就地归并排序实际用法

基础教程推荐