为什么冒泡排序效率不高？

Question

我正在使用Node.js开发后端项目，并打算实现产品排序功能。我研究了一些文章，有几篇文章说泡泡排序不是有效的。泡泡排序在我以前的项目中使用，我很惊讶为什么它是不好的。有人能解释一下为什么效率低下吗？如果您能用c编程或汇编命令来解释，将不胜感激。

Answer 1

冒泡排序具有O(N^2)个时间复杂度，因此与O(N，log，N)个排序相比，它对于大型数组来说是垃圾。

在JS中，如果可能的话，使用JS运行时可能能够用预编译的自定义代码处理的内置排序函数，而不必对排序函数进行JIT编译。标准库排序应该（通常？）为JS解释器/JIT进行良好的调整，以便高效地处理，并使用高效算法的高效实现。

这个答案的其余部分是假设一个用例，比如在提前编译的语言中对整数数组进行排序，比如编译为本机ASM的C语言。如果对一个成员作为键的结构数组进行排序，不会有太大的变化，但是如果对char*字符串和包含int的大结构进行排序，比较和交换的开销可能会有所不同。（冒泡排序对于所有这些交换的情况来说都是不好的。）

参见泡泡排序：考古算法分析，了解更多关于为什么它“流行”（或被广泛教授/讨论），尽管它是最糟糕的O(N^2)类之一，包括一些历史/教育学的意外。还包括一个有趣的定量分析，它是否真的（正如有时声称的）是使用几个代码度量最容易编写或理解的之一。

对于简单的O(N^2)排序是合理选择的小问题（例如，快速排序或合并排序的N<=32个元素基本情况），通常使用插入排序，因为它具有良好的最佳情况性能（在已经排序的情况下快速通过一次，在几乎排序的情况下高效）。

在一些几乎已排序的情况下，气泡排序（带有未进行任何交换的pass的提前出局）也不可怕，但比插入排序更糟糕。但是一个元素每次只能向列表的前面移动一步，所以如果最小的元素接近列表的末尾，但在其他情况下完全排序，它仍然需要O(n^2)的冒泡排序工作。维基百科解释兔子和乌龟。

插入排序不存在这个问题：靠近末尾的一个小元素将被有效地插入（通过复制较早的元素来打开一个缺口）。（达到它只需要比较已经排序的元素就可以确定，并以零实际插入工作继续前进）。靠近起点的一个大元素最终会迅速向上移动，只需要稍微多做一些工作：每个要检查的新元素都必须插入到那个大元素之前，然后插入到所有其他元素之后。因此，这是两个比较，有效地交换，不像泡泡排序在“好”的方向上每步交换一个。尽管如此，插入排序的坏方向比冒泡排序的“坏”方向要好得多。

有趣的事实：在实际CPU上进行小数组排序的最新技术可以包括使用打包的最小/最大指令进行SIMD网络排序，以及向量洗牌来并行执行多个“比较器”。

交换模式可能比插入排序更具随机性，对CPU分支预测器的可预测性更低。从而导致比插入排序更多的分支错误预测。

我自己还没有测试过这一点，但是想想插入排序是如何移动数据的：内循环的每次完整运行都会向右移动一组元素，为新元素打开一个空隙。在外循环迭代中，该组的大小可能保持相当恒定，因此有合理的机会预测内循环中循环分支的模式。

但是冒泡排序不能创建太多的部分排序组；交换模式不太可能重复¹。

我搜索了一下我刚刚编造的猜测的支持，确实找到了一些：插入排序比冒泡排序更好？引用维基百科：

冒泡排序与现代CPU硬件的交互性也很差。它产生的写入次数至少是插入排序的两倍，缓存未命中次数至少是插入排序的两倍，分支预测错误也会逐渐增加。

（IDK如果“写次数”是基于源代码的简单分析，或者查看经过适当优化的asm）：

这就引出了另外一点：冒泡排序可以非常容易地编译成低效的代码。交换的名义实现实际上存储到内存中，然后重新读取它刚刚写入的元素。根据编译器的智能程度，这实际上可能发生在asm中，而不是在下一个循环迭代中重用寄存器中的值。在这种情况下，您将在内部循环中有存储转发延迟，从而创建一个循环携带的依赖链。也会对缓存读取端口/加载指令吞吐量造成潜在的瓶颈。

脚注1：除非你重复排序同一个小数组；我在Skylake CPU上尝试了一次，使用了一个简化的x86 asm气泡排序实现，我为这个code golf问题编写了该实现（code-golf版本的性能很差，只针对机器代码大小进行了优化；IIRC我基准测试的版本避免了存储转发停滞和lockED指令，如XCHG mem,reg)。

我发现，每次使用相同的输入数据（在重复循环中用几条SIMD指令复制），Skylake中的IT-TAGE分支预测器“学习”了特定的13个元素冒泡排序的整个分支模式，导致perf stat在1%的分支错误预测下报告，IIRC。因此，它并没有证明我从泡泡排序中期望的大量错误预测，直到我增加了一些数组大小。：P