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

Question

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

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

有一些关于堆排序的查询:

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

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

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

4. 什么是堆的构建时间？(我听说O(n),但我不确定.)

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

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

Answer 1

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

通常,时间复杂度让我们知道算法的性能随着数据集大小的增加而变化.需要考虑的事项:

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

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

当然,算法设计通常需要在时间和空间之间进行权衡 - 具有低空间复杂度的算法可能需要更多时间,而具有低时间复杂度的算法可能需要更多空间.

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

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