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

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 元素基本情况），通常使用插入排序，因为它具有良好的最佳情况性能（在已经排序的情况下快速通过，并且在几乎排序的情况下有效）。

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

插入排序没有这个问题：接近末尾的小元素将在到达时有效地插入（通过复制较早的元素以打开间隙）。（并且达到它只需要比较已经排序的元素来确定并继续执行零实际插入工作）。开始附近的大元素最终会快速向上移动，只需要稍微多一些工作：在所有其他元素之后，每个要检查的新元素都必须插入到该大元素之前。所以这是两次比较并且实际上是一次交换，这与冒泡排序在其“好”方向上每一步进行一次交换不同。尽管如此，插入排序的坏方向还是比冒泡排序的“坏”方向好得多。

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

为什么冒泡排序在真实 CPU 上不好：

交换模式可能比插入排序更随机，并且 CPU 分支预测器的可预测性更低。因此导致比插入排序更多的分支错误预测。

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

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

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

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

（IDK，如果该“写入次数”是基于源的幼稚分析，或者查看经过适当优化的 asm）：

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

脚注 1： 除非您重复对同一个小数组进行排序；我在我的 Skylake CPU 上尝试过一次，使用简化的 x86 asm 冒泡排序实现，我为这个代码高尔夫问题编写了代码（代码高尔夫版本故意对性能来说很糟糕，仅针对机器代码大小进行了优化；IIRC 我基准测试的版本避免了存储转发摊位和locked 指令，如xchg mem,reg）。

我发现每次使用相同的输入数据（在重复循环中复制一些 SIMD 指令），Skylake 中的 IT-TAGE 分支预测器“学习”了特定 ~13 元素冒泡排序的整个分支模式，导致至perf stat1％以下分支误预测报告，IIRC。所以它毕竟没有证明我对冒泡排序的大量错误预测，直到我增加了一些数组大小。:P