什么时候使用Selection sort和Merge sort?

合并排序(nlogn)的效率总是比选择排序(n^2)快。什么时候你会选择选择排序而不是合并排序?

解决方案:

因为选择排序的运行时间是Θ(n2),而mergesort的运行时间为O(n log n),对于足够大的输入,mergesort的性能将优于选择排序。然而,在两个方面,选择排序可能会更好。

  1. 数组上的选择排序可以用O(1)辅助存储空间来实现,而(大多数)数组上的mergesort实现则使用Θ(n)辅助存储空间。因此,如果内存非常稀缺,选择排序将是比mergesort更好的选择。(然而,它比堆排序或quicksort更糟糕!)

  2. 在小的输入数组上,选择排序可能比mergesort更快,因为它是一种更简单的算法,比mergesort所隐藏的常数系数更低。如果你要排序,比如说,16个左右元素的数组,那么选择排序可能会比mergesort快。(然而,它可能会是一个比插入排序更糟糕的选择)。

所以换句话说,在某些情况下,选择排序会比mergesort更好,但在这些情况下,你可能还是使用另一种排序算法更好。)

给TA打赏
共{{data.count}}人
人已打赏
解决方案

我怎样才能找出第二个容器的正确字体大小?

2022-5-14 3:00:14

解决方案

如何修复错误:类Server中的构造函数Server不能应用于给定类型。

2022-5-14 3:00:16

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索