当前位置：文江博客话题详情

冒泡排序有什么用？

发布于 2024-07-08 19:07:14 字数 107 浏览 16 评论 0 原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

迷离° 2024-07-15 19:07:14

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

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

当磁带驱动器很常见，并且只有几千（字|字节）RAM（无论何种类型）的机器也很常见时，这是足够现实的，值得研究。这种情况现在很少见，因此研究冒泡排序根本没有任何意义 - 但更糟糕的是，无论如何，它的最佳情况都没有被教授，所以即使当/如果出现正确的情况，几乎没有人意识到< /em> 它。

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

回复收藏 0 原文

假面具 2024-07-15 19:07:14

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

我发现了解何时使用冒泡排序（或其他某种排序）的最佳链接之一是这个 - 有关排序算法的动画视图：

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

回复收藏 0 原文

秋风の叶未落 2024-07-15 19:07:14

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

回复收藏 0 原文

吻安 2024-07-15 19:07:14

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

回复收藏 0 原文

爱要勇敢去追 2024-07-15 19:07:14

对于小型集合来说，这可能是最快的。

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

回复收藏 0 原文

被翻牌 2024-07-15 19:07:14

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

回复收藏 0 原文

梅倚清风 2024-07-15 19:07:14

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

问候。

回复收藏 0 原文

世界和平 2024-07-15 19:07:14

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

回复收藏 0 原文

停滞 2024-07-15 19:07:14

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

回复收藏 0 原文

无尽的现实 2024-07-15 19:07:14

哦，是的，这是一个很好的选择机制。如果你在某人编写的代码中发现了这一点，你就不会雇用他。

回复收藏 0 原文

小伙你站住 2024-07-15 19:07:14

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

当您的集合几乎已排序时（例如，一个或多个元素不在正确的位置），冒泡排序足够快，在这种情况下，您最好从 0 索引到 n 索引以及从 n 索引到 0 索引交错遍历。
使用 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 在他著名的《计算机编程的艺术》中得出结论：“冒泡排序似乎除了一个朗朗上口的名字和它会导致一些有趣的理论问题之外，没有什么可以推荐的”。

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

Bubble sort is easy to implement and it is fast enough when you have small data sets.

Bubble sort is fast enough when your set is almost sorted (e.g. one or several elements are not in the correct positions), in this case you better to interlace traverses from 0-index to n-index and from n-index to 0-index.
Using C++ it can be implemented in the following way:

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;
      }
  }
}

It can be good if swap of two adjacent items is chip and swap of arbitrary items is expensive.

Donald Knuth, in his famous "The Art of Computer Programming", concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".

Since this algorithm is easy to implement it is easy to support, and it is important in real application life cycle to reduce effort for support.

回复收藏 0 原文

小瓶盖 2024-07-15 19:07:14

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

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

回复收藏 0 原文

一个人的夜不怕黑 2024-07-15 19:07:14

我曾经将它用于一个案例，其中绝大多数时间都会对两个项目进行排序。

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

回复收藏 0 原文

遥远的她 2024-07-15 19:07:14

编码快速且简单（几乎不可能出错）。如果您不做繁重的工作并且没有图书馆排序支持，那么它有它的用武之地。

回复收藏 0 原文

我是有多爱你 2024-07-15 19:07:14

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

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

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

// 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;

It is the sort I use most often actually. (In our project, we cannot use any external libraries.)

It is useful when I know for sure that data set is really small, so I do not care one bit about speed and want shortest and simplest code.

Bubble is not the lowest you can go. Recently, I was in a situation when I needed to sort exactly three elements. I wrote something like this:

// 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;

回复收藏 0 原文