什么时候使用选择排序和合并排序？

Question

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

Answer 1

因为选择排序的运行时间是 Θ(n ² ) 并且归并排序的运行时间是 O(n log n)，对于足够大的输入，归并排序将优于选择排序。但是，有两个方面的选择排序可能更好：

1. 数组上的选择排序可以使用 O(1) 辅助存储空间来实现，而数组上合并排序的（大多数）实现使用 Θ(n) 辅助存储空间。因此，如果内存极其稀缺，选择排序将是比归并排序更好的选择。（但是，这将是比堆排序或快速排序更糟糕的选择！）

2. 在小输入数组上，选择排序可能比归并排序更快，因为它是一种更简单的算法，其常数因子比被归并排序隐藏的因子更低。如果您要对 16 个左右元素的数组进行排序，那么选择排序可能比归并排序快。（但是，这可能是比插入排序更糟糕的选择）。

因此，换句话说，在某些情况下选择排序会比归并排序更好，但在这些情况下，您可能仍然最好使用另一种排序算法。:-)