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

Question

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

只是为了更好的理解而找出分类。

查询堆排序：

1. 我们在哪里使用堆排序？
2. 堆排序有什么更大的优势(除了时间复杂度O(n log ))？
3. 堆排序的缺点是什么？
4. 堆的构建时间是多少？(我听说了O(n)，但我不确定。)
5. 任何必须使用堆排序或堆排序的场景都是更好的选择(除了优先级队列)？
6. 在对数据应用堆排序之前，我们将查看数据的参数是什么？

Answer 1

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

通常，时间复杂度会让我们知道随着数据集大小的增加，算法的性能是如何变化的。需要考虑的事项：

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

类似地，空间复杂性描述了一个算法需要运行多少空间。例如，像插入排序这样的简单排序需要额外的固定空间来存储当前正在插入的元素的值。这是O(1)的辅助空间复杂度-它不随输入的大小而改变。但是，合并排序在运行时会在内存中创建额外的数组，辅助空间复杂度为O(n)。这意味着它所需要的额外空间的数量与输入的大小呈线性相关。

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

有关更多信息，您可能会发现本教程很有用。

要回答您更新的问题，您可能会发现堆排序上的维基百科页面很有用。

Answer 2

如果您指的是选择哪种类型的标准，以下是需要考虑的其他项目。

您拥有的数据量:您有10、100、1000或数百万项要排序。

算法的复杂性:越复杂，就需要做更多的测试来确保它是正确的。对于少量的数据，气泡排序或快速排序很容易编码和测试，而其他类型的排序可能会对您必须排序的数据量过高。

排序需要多长时间:如果你有一个大集合，泡泡/快速排序将花费大量的时间，但是如果你有很多时间，这可能不是问题。然而，使用更复杂的算法将减少排序的时间，但代价是在编码和测试方面付出更多的努力，如果排序从长时间(小时/天)减少到更短的时间，这可能是值得的。

数据本身:是所有数据几乎相同的数据。对于某些类型，您可能会得到一个线性列表，因此，如果您知道数据的组成，它可能有助于确定选择哪种算法的努力。

可用资源的数量:您是否有大量内存来存储所有项，或者是否需要将项存储到磁盘中。如果所有的东西都不能放在内存中，合并排序可能是最好的，而如果您处理内存中的所有内容，其他的可能会更好。