什么是泡沫sorting?

泡沫sorting有没有真正的世界使用? 每当我看到一个提到的,它总是:

  1. 用于学习的sortingalgorithm。
    • 使用sortingalgorithm的一个例子。

这取决于你的数据分布的方式 – 如果你能做出一些假设。

我发现了解何时使用冒泡sorting(或其他types)的最佳链接之一是对sortingalgorithm的animation视图:

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

泡沫sorting(可能)是在非常特定的情况下可用的最快sorting。 它最初是因为它是第一个被严格分析的algorithm之一而被人们所熟知的,certificate它在有限的情况下是最优的。

考虑一个存储在磁带驱动器上的文件,以及随机访问内存(或者如此大的密钥),因此在任何给定的时间只能将两条logging加载到内存中。 重放磁带足够慢,以至于在文件中进行随机访问通常是不切实际的 – 如果可能的话,您希望按顺序处理logging,每次不超过两个。

当磁带驱动器很常见时,只有几千字(RAM)(无论是什么types的)的机器是常见的,这是足够现实的,值得研究。 那种情况现在很less见,所以研究泡沫sorting根本就没什么意义 – 但更糟糕的是,最佳情况并没有被教导,所以即使出现正确的情况,几乎没有人会意识到这一点。

就极小的和/或几乎sorting的数据集而言,尽pipe它能够掩盖气泡sorting的弱点(至less在某种程度上),但插入sorting对于任何一个/两个那些。

它在现实世界中使用得并不多。 这是一个很好的学习工具,因为它易于理解和快速实施 。 它有坏(O(n ^ 2))最坏的情况和平均performance。 当你知道数据几乎被sorting时,它具有良好的性能performance,但是有很多其他algorithm具有这个属性,具有更好的最差和平均情况下的性能。

我最近在一个优化轶事中遇到了很大的用处。 一个程序需要一组精灵按深度顺序sorting。 spites的顺序在帧之间不会有很大的变化,所以优化的时候,每一帧都是一次一遍的冒泡。 这是在两个方向(从上到下,从下到上)完成的。 所以精灵总是用一个非常高效的O(N)algorithm来sorting。

这可能是最小的一套。

说到教育。 链接到sorting的最后一幕,这是惊人的。 一个必须看到的。

对于小数据集是很好的 – 这就是为什么当分区大小变小时,一些qsort实现切换到它。 但是插入sorting还是比较快,所以除了作为辅助工具之外,没有什么好的理由使用它。

我们最近在一个algorithm的最优性certificate中使用了bubblesort。 我们必须将由一系列对象表示的任意最优解转化为我们的algorithmfind的解决scheme。 因为我们的algorithm只是“按照这个标准sorting”,所以我们必须certificate我们可以在不使情况恶化的情况下对最优解进行sorting。 在这种情况下,冒泡sorting是一个非常好的algorithm,因为它具有很好的不变性,只是交换彼此相邻的两个元素并且顺序错误。 我想,使用更复杂的algorithm会导致大脑融化。

问候。

我认为这是一个很好的“教学”algorithm,因为它很容易理解和实施。 对于小数据集也可能有相同的理由(尽pipe一些O(n lg n)algorithm也很容易实现)。

泡泡sorting很容易实现,而且当你有小的数据集的时候就足够快了。

当你的集合几乎被sorting时(例如,一个或几个元素不在正确的位置),泡泡sorting是足够快的,在这种情况下,你最好隔行扫描从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在他着名的“计算机程序devise艺术”一书中得出结论:“除了一个引人注目的名字和导致一些有趣的理论问题的事实之外,泡沫sorting似乎没有什么可推荐的 。

由于该algorithm易于实现,因此易于支持,并且在实际应用生命周期中减less支持的努力是重要的。

在TRS-80 Model 1中,我曾经在某些情况下使用它来创build小的N.使用for循环,可以在一个程序行上实现完整的sorting。

除此之外,这对于教学是有利的,有时对于几乎sorting顺序的列表来说也是如此。

我曾经用过这样一个案例,绝大多数时候它将分拣两个项目。

下一次我看到这个代码时,有人用库类来replace它。 我希望他们先对它进行基准testing!

代码快速简单(几乎不可能做错)。 如果你没有繁重的工作,并且没有图书馆sorting支持,那么这就是它的地方。

这是我最常用的那种。 (在我们的项目中,我们不能使用任何外部库。)

当我确定数据集非常小时,这非常有用,所以我不在乎速度,而想要最短和最简单的代码。

泡沫是不是你可以去的最低。 最近,我正处于需要排列三个要素的情况。 我写了这样的东西:

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

我无法拒绝对泡沫sorting的任何评论,提到更快(似乎是O(nlogn),但这并没有真正certificate) 梳理sorting 。 请注意,如果您使用预先计算的表格,则梳理sorting会快一点。 梳理sorting与气泡sorting完全相同,只不过它最初不是通过交换相邻元素来开始的。 像泡泡分类一样容易实现/理解。

哦,是的,这是一个很好的select机制。 如果你用某人写的代码find它,你就不雇用他。

几乎没有 。 使用QuickSort或SelectionSort来代替…!