排序算法

01想排好顺序，需要可以重复的方法

列表就是按某种次序排成的一行对象。这里，一个对象就是一张卡片。卡片的数值用来比较大小，位置则说明它在这一行的哪里。移动卡片改变的是位置，不是卡片上写的数。

我们的要求很明确：每张卡片都不能比下一张大，而且不能丢失或增加卡片。相等的数可以相邻。用一套有限、明确的指令完成这个任务，这套指令就叫算法。下面研究五种排序算法，也就是到达同一种结果的五种方法。

每个实验中，金色表示这一步涉及的卡片，绿色表示以后不再需要改变的位置。字母标记原来的卡片，因此两张写着 2 的卡片仍可以区分。点“下一步”会显示一次决定，解释会说明它的理由；继续推进，就能看到这个决定造成的变化。“上一步”会恢复先前状态，包括计数。

02冒泡排序：把较大的数带到右边

先只看两张相邻卡片。左边较大就交换，否则保留。然后向右移动一个位置，重复这个动作。比较 5 和 2 后，5 向右移动；后来遇到 7，继续向右传递的较大值就变成了 7。所以从左到右走完一轮，最大的值会留在最右端。

现在把已经确定的最后一个位置留在原处，只对前面较短的未完成部分再做一轮。为什么最后一定能完成？每轮至少确定一个新位置，有限张卡片不会让我们永远重复。如果某一轮完全没有交换，说明每对相邻卡片已经有序。一张不大于后一张，后一张又不大于再后一张，沿着整行就能知道整行有序，因此可以提前停止。

03选择排序：一次确定一个最终位置

我们也可以换一种方式决定第一张卡片：检查所有剩余卡片，记住目前见过的最小值。一开始先记第一张；遇到更小的，就更新记住的选择。必须检查完所有剩余卡片，才能把最小值交换到第一个尚未完成的位置。

记住的值确实是最小值，因为每张检查过的卡片都与它比较过，而记住的值只会变小。把它放好后，剩余的数都不小于它。再对剩余部分重复即可。注意它与冒泡排序的区别：即使初始排列已经有序，这种方法仍要完成检查，因为它没有“没有交换就结束”的规则。

04插入排序：保留已经排好的部分

单独一张卡片已经有序。取下一张，与左邻居比较。如果左邻居较大，就交换，再检查新的左邻居。走到开头，或者遇到一个不比这张卡片大的邻居时停下。这样，我们把一张新卡片插入了正确位置，同时没有打乱其他卡片原来的次序。

为什么在这里停止就够了？更左边原本已经有序，所以都不大于我们停下处的左邻居。我们刚越过的卡片都比选中的卡片大，并且已经移到它右边。因此左右两侧都符合顺序。每次有序部分增加一张，直到包含整行。

05归并排序：利用两个已经完成的小任务

假设已经有两行排好的卡片。要找尚未取走的最小卡片，只需要比较两行最前面的卡片：每行后面的卡片都不小于自己的第一张。把较小的首张复制到新行，让原行的下一张成为首张，再重复。一行取完后，另一行剩余卡片按原顺序接到后面。这个操作叫合并。

那两行有序卡片从哪里来？把原行分成两段，对每段再做同一个排序任务。不断分下去，直到每段只有一张卡片。最小的任务已经完成，于是可以往回合并：单张合成有序的两张，再合成更大的有序部分。在更小的输入上重复同一个任务叫递归；这里每个小输入在过程中都有具体位置。

辅助行在原来的两段仍供读取时保存副本。合并完成后，再把结果复制回原行。因此画面会暂时出现同一张卡片的副本，最终列表并没有增加卡片。这种实现需要额外存储空间，计数也包括写入辅助行和写回原行的操作。

06快速排序：先放好一张用于分界的卡片

选一张卡片作为基准，也就是用来区分其他数的值。这里选最后一张。逐个检查其他卡片，把小于基准的数收集到左边，并记住这个较小组后面的边界。遇到较小值，就把它交换到边界位置，再把边界右移一格。

检查完后，把基准交换到边界处。它左边全部更小，右边全部不小于它，因此基准已经处在一个正确的最终位置。两侧可能仍未排好，不过现在可以分别用同一个方法排序。每个递归任务都排除已经放好的基准，所以任务会变小，最终结束。

卡片下方的色带显示扫描中的三组：已经检查且较小、已经检查且不小于基准、尚未检查。基准另放在末尾等候。每次比较前，白色边界线标出较小组的终点，箭头指向下一张尚未检查的卡片。最后一张卡片归类后，尚未检查组变为空。可以退回一步，逐次观察究竟是哪一组扩大了。

“快速”这个名字不保证每种输入都快。试一试已经有序的排列。选最后一个最大值，会留下几乎完整的左段和空的右段，任务只减少了一张卡片。其他基准选择方法可以避免许多这种情况，但当前这个“选最后一张”的演示仍会遇到它。

07计算工作量，比较方法怎样适合任务

一次数值比较检查两个数的大小或是否相等。一次数组写入把一个对象存进一个位置。在这里的计数中，交换两个不同位置需要两次数组写入，临时变量赋值不计入。这些计数说明这个实现做了什么，并不表示秒数，而且比较与写入不一定耗费相同时间。

还有一种要求，单看柱高无法看出来。假设相等数值代表同分的人，原列表已经按到达先后排列，我们可能希望保留这个先后次序。如果排序保留相等值对象原本的相对次序，就称为稳定排序。跟着相等卡片上的字母看。冒泡和这里的插入法只交换相邻卡片。两张相等卡片如果要颠倒次序，就必须互相越过；只靠相邻交换，就必定要在某一步直接交换这两张卡片。而我们的规则从不交换相等值，所以它们不可能颠倒。选择和当前快速排序则可以在一次交换中跨过好几张卡片，无须直接比较那对相等值，也可能改变它们的先后。

归并排序先看只有一张卡片的部分，里面没有可以颠倒的相等卡片。假设两个较小部分已经保留各自相等卡片的原顺序。每次只从首张取出，就保留了每部分内部的顺序。如果相等卡片来自不同部分，左部分原本就在右部分前面，因此相等时先取左边，也保留了它们的顺序。这样每一次合并都保留这个性质，直到整行合并完成。

快速排序虽然没有归并那样的辅助行，仍需要记录尚未完成的递归任务。因此选择方法要考虑数据情况、稳定性、存储空间，也要考虑比较次数。接下来到搜索页面，看看排好顺序以后能做什么。

08检查自己能否说明下一步