c++ - 选择排序算法的标准是什么？

Question

我正在阅读排序方法，包括冒泡排序、选择排序、归并排序、堆排序、桶排序等。它们还包含时间复杂度，可以帮助我们了解哪种排序是高效的。所以我有一个基本问题。如果我们包含数据，那么我们将如何选择排序。时间复杂度是帮助我们决定排序方法的参数之一。但是我们是否有另一个参数来选择排序方法？

只是想弄清楚排序以便更好地理解。

对堆排序有一些疑问:

1. 我们在哪里使用堆排序？

2. 堆排序的最大优势是什么(除了时间复杂度O(n log n))？

3. 堆排序的缺点是什么？

4. 堆的构建时间是多少？ (我听说过 O(n) 但我不确定。)

5. 我们必须使用堆排序或堆排序是更好的选择的任何场景(优先级队列除外)？

6. 在对数据应用堆排序之前，我们要查看数据的参数是什么？

Answer 1

排序算法的两个主要理论特征是时间复杂度和空间复杂度。

一般来说，time complexity让我们知道算法的性能如何随着数据集大小的增加而变化。需要考虑的事项:

• 您希望对多少数据进行排序？这将帮助您了解是否需要寻找时间复杂度非常低的算法。
• 您的数据将如何排序？它会部分排序吗？随机排序？这会影响排序算法的时间复杂度。大多数算法都有最坏和最好的情况 - 您要确保您没有在最坏情况的数据集上使用算法。
• 时间复杂度与运行时间不同。请记住，时间复杂度仅描述算法的性能如何随着数据集大小的增加而变化。总是对所有输入进行一次传递的算法将是 O(n) - 它的性能与输入的大小线性相关。但是，总是对数据集进行两次传递的算法也是 O(n) - 相关性仍然是线性的，即使常数(和实际运行时间)不同。

同样，空间复杂度描述了算法运行需要多少空间。例如，一个简单的排序，如 insertion sort需要额外的固定空间来存储当前插入的元素的值。这是 O(1) 的辅助空间复杂度——它不随输入的大小而变化。然而，merge sort运行时在内存中创建额外的数组，辅助空间复杂度为 O(n)。这意味着它需要的额外空间量与输入的大小线性相关。

当然，算法设计往往是时间和空间之间的权衡——空间复杂度低的算法可能需要更多的时间，时间复杂度低的算法可能需要更多的空间。

更多信息，您可以找到this tutorial有用。

---

要回答您更新的问题，您可以在 Heap Sort 上找到维基百科页面有用。