7

在我得到答案之前，我冒着这个问题被关闭的风险，但我真的很想知道答案。所以这里。

我目前正在尝试学习算法，并且我开始理解它，但无法与之相关。

我了解时间复杂性和空间复杂性。我也确实了解一些基于伪代码的排序算法

排序算法如

  1. 冒泡排序
  2. 插入排序
  3. 选择排序
  4. 快速排序
  5. 合并排序
  6. 堆排序（一些什么）

我也知道最好的情况和最坏的情况（平均情况不是很多）。

一些网上相关的参考资料

  • 以图形方式显示以上所有内容的好地方。
  • 这也让我有了很好的理解。

但我的问题是 - 有人可以给我实现这些排序算法的真实世界示例。

4

2 回答 2

8

随着元素数量的增加，您将使用更复杂的排序算法。后来的排序技术具有更高的初始开销，因此您需要大量元素来排序以证明该成本是合理的。如果您只有 10 个元素，则冒泡排序或插入排序将比合并排序或堆排序快得多。

对于电视遥控器或手机等较小的嵌入式设备，空间复杂性很重要。您没有足够的空间在这些设备上执行诸如堆排序之类的操作。

数据库使用外部合并排序对太大而无法完全加载到内存中的数据集进行排序。这种类型的驱动因素是磁盘 I/O 数量的减少。

好的冒泡排序讨论，还有许多其他因素需要考虑，这些因素会导致时间和空间复杂性。

排序算法.com

于 2012-06-13T20:33:52.867 回答
0

一个例子是 C++ STL 排序

正如维基百科页面所说：

例如，GNU 标准 C++ 库使用混合排序算法：首先执行 introsort，最大深度由 2×log2 n 给出，其中 n 是元素的数量，然后对结果进行插入排序。1无论采用何种实施方式，复杂度平均应为 O(n log n) 次比较。 [2]

于 2012-06-13T20:29:45.817 回答