algorithm - 冒泡排序有什么用？

Question

冒泡排序在现实世界中有任何用途吗？每次我看到有人提到，它总是要么：

一种可以学习的排序算法。
不使用的排序算法示例。

score 81 · Accepted Answer

冒泡排序（可证明）是在非常特定的情况下可用的最快排序。它最初之所以广为人知，主要是因为它是最早经过严格分析的算法之一（任何类型的），并且证明它在其有限的情况下是最优的。

考虑一个存储在磁带驱动器上的文件，以及如此小的随机存取内存（或如此大的密钥），以至于您在任何给定时间只能将两条记录加载到内存中。倒带速度很慢，以至于在文件中进行随机访问通常是不切实际的——如果可能的话，您希望按顺序处理记录，一次不超过两个。

回到磁带驱动器很常见的时候，只有几千个（字|字节）RAM（任何类型）的机器很常见，这足够现实值得研究。这种情况现在很少见，所以研究冒泡排序毫无意义——但更糟糕的是，无论如何都没有教授最佳的情况，所以即使/如果出现正确的情况，几乎没有人会意识到这一点。

至于在极小和/或几乎排序的数据集上是最快的，虽然这可以掩盖冒泡排序的弱点（至少在某种程度上），但插入排序本质上总是对两者中的任何一个/两者都更好那些。

score 47 · Accepted Answer

这取决于您的数据分布方式 - 如果您可以做出一些假设。

我发现了解何时使用冒泡排序或其他排序的最佳链接之一是关于排序算法的动画视图：

http://www.sorting-algorithms.com/

score 20 · Accepted Answer

它在现实世界中并没有得到太多使用。它是一个很好的学习工具，因为它易于理解并且可以快速实施。它具有糟糕的 (O(n^2)) 最坏情况和平均性能。当您知道数据几乎已排序时，它具有良好的最佳情况性能，但是还有许多其他算法具有此属性，具有更好的最坏情况和平均情况性能。

score 10 · Accepted Answer

我最近在一个优化轶事中发现了它的一个很好的用途。一个程序需要一组按每帧深度排序的精灵。仇恨顺序在帧之间不会有太大变化，因此作为一种优化，它们在每帧一次通过的情况下进行了冒泡排序。这是在两个方向（从上到下和从下到上）完成的。因此，精灵几乎总是使用非常有效的 O(N) 算法进行排序。

score 7 · Accepted Answer

对于小型套装来说，这可能是最快的。

说到教育。整理整理最后一幕的链接，太神奇了。必看。

score 3 · Accepted Answer

这对小型数据集很有用——这就是为什么当分区大小变小时一些 qsort 实现会切换到它的原因。但是插入排序仍然更快，所以除了作为教学辅助之外，没有什么好的理由使用它。

score 3 · Accepted Answer

我们最近在算法的最优性证明中使用了冒泡排序。我们必须将由一系列对象表示的任意最优解转换为我们的算法找到的解。因为我们的算法只是“按此标准排序”，所以我们必须证明我们可以对最优解进行排序而不会使其变得更糟。在这种情况下，冒泡排序是一种非常好的算法，因为它具有很好的不变量，即只交换两个相邻且顺序错误的元素。我认为，使用更复杂的算法会使大脑融化。

问候。

score 2 · Accepted Answer

我认为这是一个很好的“教学”算法，因为它很容易理解和实现。出于同样的原因，它也可能对小型数据集有用（尽管一些 O(n lg n) 算法也很容易实现）。

score 2 · Accepted Answer

我无法抗拒对冒泡排序的任何评论，提到更快的（似乎是 O(nlogn)，但这并没有真正得到证明）Comb Sort。请注意，如果您使用预先计算的表，梳排序会更快一些。梳排序与冒泡排序完全相同，只是它最初不是通过交换相邻元素开始的。它几乎与冒泡排序一样容易实现/理解。

score 2 · Accepted Answer

冒泡排序很容易实现，当你有小数据集时它足够快。

当您的集合几乎已排序（例如，一个或多个元素不在正确的位置）时，冒泡排序足够快，在这种情况下，您最好交错从 0-index 到 n-index 以及从 n-index 到 0-index . 使用 C++ 可以通过以下方式实现：

void bubbleSort(vector<int>& v) { // sort in ascending order
  bool go = true;
  while (go) {
    go = false;
    for (int i = 0; i+1 < v.size(); ++i)
      if (v[i] > v[i+1]) {
         swap(v[i], v[j]);
         go = true;
      }
    for (int i = (int)v.size()-1; i > 0; --i) 
      if (v[i-1] > v[i]) {
         swap(v[i-1], v[i]);
         go = true;
      }
  }
}

如果两个相邻项目的交换是筹码并且任意项目的交换很昂贵，那可能会很好。

Donald Knuth 在他著名的“计算机编程艺术”中总结道，“冒泡排序似乎没有什么可推荐的，除了一个吸引人的名字和它导致一些有趣的理论问题的事实”。

由于该算法易于实现，因此易于支持，并且在实际应用程序生命周期中减少支持工作量很重要。

score 1 · Accepted Answer

实际上，这是我最常使用的那种。（在我们的项目中，我们不能使用任何外部库。）

当我确定数据集非常小时，它很有用，所以我一点也不关心速度，想要最短和最简单的代码。

泡沫不是你能达到的最低值。最近，我遇到了需要对三个元素进行准确排序的情况。我写了这样的东西：

// Use sort of stooge to sort the three elements by cpFirst

SwapElementsIfNeeded(&elementTop, &elementBottom);
SwapElementsIfNeeded(&elementTop, &elementMiddle);
SwapElementsIfNeeded(&elementMiddle, &elementBottom);

*pelement1 = elementTop;
*pelement2 = elementMiddle;
*pelement3 = elementBottom;

score 1 · Accepted Answer

在某些情况下，我曾经在 TRS-80 Model 1 上将它用于小 N。使用 for 循环，可以在一个程序行上实现完整的排序。

除此之外，它对教学很有用，有时也适用于几乎按排序顺序排列的列表。

score 1 · Accepted Answer

我曾经将它用于绝大多数情况下它将对两个项目进行排序的情况。

下次我看到该代码时，有人将其替换为库排序。我希望他们首先对其进行基准测试！

score 1 · Accepted Answer

编码既快速又容易（几乎不可能出错）。如果你不做繁重的工作并且没有图书馆分类支持，它就有它的位置。

score 1 · Accepted Answer

哦，是的，这是一个很好的选择机制。如果您在某人编写的代码中找到它，您就不会雇用他。

score 0 · Accepted Answer

0

大多没有。请改用 QuickSort 或 SelectionSort...！

于 2008-11-29T22:33:21.930 回答

algorithm - 冒泡排序有什么用？

16 回答 16

Related

Reference