algorithm - 您什么时候使用选择排序与归并排序？

Question

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

Answer 1

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

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

2. 选择排序在小型输入数组上可能比归并排序更快，因为它是一种更简单的算法，与归并排序隐藏的算法相比具有更低的常数因子。例如，如果您要对包含 16 个左右元素的数组进行排序，那么选择排序可能比归并排序更快。 (但是，与插入排序相比，它可能是一个更糟糕的选择)。

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