冒泡排序，摇滚排序和鸡尾酒摇床排序

我目前正在参加Donald Knuth的《计算机编程艺术》的读书俱乐部。由Zartaj Majeed经营；您可以在此处找到有关Meetup的详细信息。

昨天，我们讨论了第5.2.2节“通过交换进行排序”的前半部分。（我们正在以非常非线性的方式阅读。）本节从气泡排序的变化开始。我编写了一些C ++代码来演示本节中的三种算法。我想我最好也分享一下。

首先，“冒泡排序”和“插入排序”（Knuth在第5.2.1节“通过插入排序”中涉及）之间有什么区别？这个StackOverflow回答确实为我提供了明确的答案。在插入排序的每个步骤中，您都将最上面未排序的元素通过排序部分冒泡到正确的位置（Knuth将此称为“ bridge-player”方法）。在气泡排序的每个步骤中，您都在未排序部分中进行筛选以找到最大值，该最大值的正确位置必须在已排序部分的底部。

在“选择排序”中，您要遍历未排序的部分以找到最大数量-在此步骤结束之前不进行任何交换。在任何给定的传递中，只有一个数组元素向上移动。而在冒泡排序中，您可能会冒泡一些非最大元素，然后再找到实际的最大值。

for（int i = 0; i＆lt; n; ++ i）{for（int j = 0; j＆lt; ni-1; ++ j）{if（a [j + 1]＆lt; a [j] ）swap（a [j]，a [j + 1]）; }}

但是Knuth提出的bubbleort具有巧妙的优化。将向上运动的元素视为气泡在水中冒泡。随着算法的进行，我们将空气积聚在水柱的顶部。每次通过时，水位至少会下降一个……但可能还会下降更多！ Knuth的原型气泡排序（第5.2.2节中的算法B）在称为BOUND的变量中跟踪真实水位，并且可以终止少于n次传递-BOUND达到零时，我们就完成了。

第106页的Knuth第3卷，给出了上面关于冒泡现象的漂亮可视化效果（当含水未分类部分中的每个元素移近表面时，都会有气泡状痕迹）。每列中的水平线代表水位。维持这一技巧的诀窍是要注意，在每一列中，水位都是在上一步交换的最后两个元素之间精确设置的。

在本例的第4遍中，我们冒出512，将其交换为426、154和509，然后由于512小于612，因此我们将612作为新的最大值而不进行交换;然后是653、677和703。 （也就是说，我们不交换任何这些元素。）因此，我们在Pass 4中交换的最后一对元素是509和512。这就是Pass 4之后的水位下降了五个位置以降落在509和512之间的原因。我们只是与上面介绍的“幼稚”嵌套循环Bubblesort代码相比，savefourfour通过了！

可以很容易地想象出所有反向计数器都冒着气泡的版本，在这种情况下，我们将“重”元素沉没到了列的底部，而不是将“通风”元素抬高到了列的顶部。在聚会上，迈克尔·扎列夫斯基（MichaelZalewski）将此变化称为“摇滚排序”。

在第109-110页上，克努斯指出，普通的气泡类型具有自然的倾向，可以使“岩石”自行沉入底部。每次我们向上充气一个轻元素时，我们都会将其任意随机地移过许多较重的元素，每个元素都会稍微向下沉。请注意，在图14的通道4中，元素061和087已经到达列的底部。如果我们除了跟踪“水位”之外还跟踪“岩石级”，我们可以跳过对这两个元素的比较在随后的每个通行证上。努斯写道：

Knuth第3卷，第110页，给出了鸡尾酒搅拌器分类的上述精美外观。请注意，这一次，交替的通行泡沿相反的方向起泡。第一道气泡使空气向上气泡并降低水位；第二次通过时，气泡向下倾斜，从而提高了岩石高度。经过六遍后，水位达到了岩石水位，这就是我们要做的。

[精炼Bubblesort]的另一个想法是消除大多数交换；由于大多数元素在交换过程中仅向左移动一步，因此我们可以通过不同地查看数组，移动索引的原点来实现相同的效果！

他是什么意思，“大多数元素只是向左移动一步”？好吧，向上移动的通风元件的数量往往很少-我们大部分时间都花在向上鼓泡相同的少数元件上。每个比当前最大值重的元素最终都会向下精确地向下移动一步（当该通风的元素冒泡经过它时）。确实有些元素会向上移动，而有些元素会留在同一位置（图14的元素170在第4遍到第7步中所做的操作，然后再次在第8遍中移动）。但是，绝大多数元素的确在每次通过时都向下移动了一步。

因此，我们不打算将交换描述为“元素a [i]进入a [i + 1]，a [i + 1]进入a [i]”，而是想象覆盖数组b使得b [0]为a [1]的别名，比方说“元素a [i]进入b [i + 2]，a [i + 1]进入b [i + 1]。”请记住，a [i]无论如何都不会落在b [i + 2]上，因为a [i]是当前的最大值，并且可能会一次向上气泡多个位置。然后，在下一步中，我们只需更改索引方案，以便对数组a的别名数组binstead进行操作...

这种方案似乎会使数组在每次通过时在内存中向右爬行。但是我们可以通过使用鸡尾酒摇床排序而不是直接的冒泡排序来解决此问题！在奇数遍中，我们将覆盖b，使得b [0]是a [1]的别名，因此“下沉”元素不必移动。在偶数遍中，我们将覆盖c，使得c [1]是b [0]的别名，因此“上升”元素不必移动。这使我们的数组回到了初始位置。

这种改进提高了“鸡尾酒摇床排序”这个名称的适用性，因为现在我们实际上是通过重复的动作将整个容器上下移动一小段。但是，自相矛盾的是，我们正在移动容器，以使内部元素的运动减少；结果不是完全混合的饮料，而是完全没有混合的饮料。

我决定编写上述用于气泡排序，鸡尾酒摇床排序和“移动鸡尾酒摇床排序”的算法，以亲眼看到Knuth不同改进的效果。 （此外，我需要说服自己，这种振动筛可以实现！）

它生成一个包含100个随机整数的数组，然后以五种不同的方式对其进行排序。

天真：4950c 2468s-气泡：4931c 2468s-摇动：3477c 2468s-移位：3477c 1118s-标准：808c 70s天真：4950c 2391s-泡沫：4814c 2391s-摇动：3295c 2391s-移位：3295c 999s-标准：820c 66s -气泡：4833c 2203s-抖动：3007c 2203s-移位：3007c 913s-标准：746c 57s天真：4950c 2652s-气泡：4761c 2652s-抖动：3472c 2652s-移位：3472c 924s-标准：810c 56s

输出的每一行代表一个不同的随机输入。 4950c表示算法进行了4950次比较，而2468s表示进行了2468次交换。

“气泡”是Knuth的气泡排序，可跟踪水位。请注意，它的交换次数与“朴素”次数相同，但是由于不需要比较水线上方的元素，因此可以节省一些比较。

“摇动”是Knuth的鸡尾酒摇动器，可同时跟踪水位和岩石位。请注意，它进行的交换次数相同，但是由于不需要比较海底以下的元素，因此可以节省更多的比较。

“转变”是我对不断变化的鸡尾酒摇床的解释。请注意，它执行与“摇动”相同的比较次数，但是这次它节省了一些交换。我的实现涉及将当前冒泡的元素“拉出”到局部变量中，而不是将其保留在数组中。创建抽出菜单时，我仅会计算一次“交换”，而一旦将其放回阵列中的最终位置，我便会计算一次。

“ Std”是C ++标准库的std :: sort，只是为了好玩。我相信这通常是introsort。请注意，它所做的比较少得多，交换也少得多。但是，请注意，“掉期”号码可能是个谎言。允许std :: sort使用与我的振动筛排序类似的提取，并且不需要“报告”这些操作以进行计数。 （我们也可以为Wrapped提供一些特殊的成员函数来对这些操作进行计数，但我没有这样做。）有趣的是，libc ++似乎对仅移动类型使用了另一种更为繁重的交换算法。

最后，我认为有趣的是，所有“天真”，“冒泡”和“摇动”都执行完全相同的交换次数。这是因为eachswap交换了两个相邻的乱序元素，因此将数组的反转数精确地减少了1。当反转数达到零时，将对数组进行排序。因此，每个仅交换乱序的排序算法相邻元素必须执行完全相同数量的交换。同样，每个这样的算法实际上都是稳定的。

要执行更少的总交换，您必须执行一些交换，从而一举将倒置次数减少超过1。这意味着您必须交换一些不相邻的元素对。折衷方案是，这很容易使您的排序算法不稳定。

顺便说一下，Knuth对这些算法很感兴趣，主要是因为它们在运行时间分析过程中出现了有趣的数学问题，而不是因为它们无论如何都是有效的算法！如果必须对一百万个32位整数进行排序，那么冒泡排序将是错误的方法。