〖不可方物〗算法可视化——洗牌和排序（二）

我的素质低

2825

收藏 2015-03-20

正如扑克的洗牌一样，洗牌算法是对一组元素的随机重排列的过程。一个好的洗牌算法应该是无偏的，即每一种排列都是等可能的。

下面我们来看看Fisher–Yates洗牌算法，它可是最优洗牌算法哦~它不仅是无偏的，而且时间复杂度是O(n)，空间复杂度是O(1)，同时也非常容易实现，代码如下

算法的过程见下图

图中的每一条线代表一个数字，线的倾斜程度代表数的大小，线越往左倾斜表明数越小，反之越往右倾斜表明数越大。

从图中可以明显看出，该算法把数组划分为两个部分，右半边是已洗牌区域（用黑线表示），左半边是待洗牌区域（用灰线表示）。每一步从左边的待洗牌区域随机选择一个元素并将其移动到右侧，如此循环下去直到待洗牌区域无数组元素，算法终止。

Fisher–Yates洗牌算法是一个简单而且正确的算法，但并不是每一个简单的洗牌算法都一定是正确的。我们来看看下面这个错误的洗牌算法

我们先来解释一下代码，array.sort()表示对数组进行排序，一般情况下是按照数组中元素的大小（例如整形）或者是按照字典序列（例如字符）来进行排序。

当然我们也可以自定义规则，也就是自定义一个comparator函数，然后依据返回值来确定待排元素的大小关系，返回值大于0表明第一个参数更大，返回值小于0表明第二个参数更大，返回值为0表明相等。上面的代码中定义了这样的一个comparator函数，从数组中随机取两个元素a和b，然后随机返回[-0.5,0.5)之间的一个值，也就是说元素a和b之间的大小关系是随机的，所以它们之间的顺序也是随机的，这样遍历完整个数组后所有元素的顺序都是随机的。

但真的是这样的吗？当然不是，这个算法的有着非常严重的缺陷。首先我们要知道，任意两个元素之间的顺序随机性并不能保证整体的顺序随机性。同时，一个比较器应该满足传递性，如果有a>b且b>c，那么就有a>c。而上述代码中的随机比较器破坏了这个特性，导致array.sort()的行为是不确定的，所以最后的结果也是不可靠的。

乍一看好像也是随机的啊，但是我们要注意有些东西人眼看起来是随机的，但实际上确并非随机的。

为了更直观的衡量算法的质量，我们换一种方式来进行展示~

一个好的洗牌算法应该保证无偏性，也就是说保证每个元素在洗牌结束后出现在数组的任何位置都是等可能的，概率为1/n，其中n为数组元素个数。当然准确的计算这个概率有点困难（依赖具体的算法），但是我们可以从统计意义上来计算这个概率。也就是把洗牌算法运行几千次，统计原先在位置i的元素在洗牌后出现在位置j的次数，然后画在一张图上，如下

上图中列表示元素在洗牌前的位置，行表示元素在洗牌后的位置。颜色表示概率，绿色表示正偏，也就是其出现次数高于预期。红色表示负偏，也就是其出现次数低于预期。

上图是在Chrome浏览器下的结果，只能说很一般。注意到在对角线偏下的位置有严重的正偏现象，表明这个算法很容易将一个在位置i元素在洗牌后放置到i+1或者i+2的位置上去，同时也注意到在数组第一个、中间的和最后一个元素也有很多正偏和负偏现象，这个可能和Chrome浏览器的具体实现有关。

而Fisher–Yates洗牌算法的结果就要好很多

图中没有明显的规律可循，个别偏差也是因为我们使用的是统计的方法，与算法本身无关。

另外值得一提的一点是，随机比较器(random comparator)洗牌算法的结果与浏览器的实现也有很大关系。刚才Chrome浏览器的结果已经很糟糕了，我们再来看看Firefox下的结果

只能说惨不忍睹！当然这并不意味着Chrome比Firefox要强，只能说明我们所使用的算法是有问题的，导致其结果是不确定的。而浏览器内部的不同实现更直观的把这个问题暴露出来了。

排序

排序呢大家都很熟悉了，我们先来看看耳熟能详的快速排序

快排的原理这里也不多说了，就是通过在当前待排元素中取一个基准，然后将比该基准小的元素放置其左侧，比基准大的元素放置在其右侧，然后递归进行下去。

以下是实现代码

当然快排算法有很多版本，上面演示的那个版本是最简单也是最慢的一种，主要用于教学演示，在实际应用中有很多其他优化的方法。例如三数取中（median-of-three）法，即取三个元素先进行排序，将中间数作为基准，一般是取左端、右端和中间三个数，也可以随机抽取。这样做的好处是得到的基准有很大可能会更接近真正的中间数，划分出来的两个部分大小会更加均衡，递归的层数会更少，可以提高算法的效率。另一种优化方法是在当递归进行到一定程度时，也就是当数组元素比较少的时候采用插入排序而不是继续递归下去。

用动画来展示算法虽然有趣直观，但有的时候却可能让我们忽视掉一些细节，而且如果动画太快的话思维就跟不上了。所以我们可以用一种类似漫画的方法来进行展示，突出算法中的关键步骤。

注意这里左右两个部分的快速排序是并行执行的，红线表示当前划分所使用的基准，在下一层中使用过的基准会标成灰色。

还有另外一种展示方法，用色带来表示元素。色带颜色越深表示元素越大，色带颜色越浅表示元素越小。下面我们用这种方法来展示上述快排算法

至此我们演示了三种可视化快速排序算法的方法，动画展示、分步展示、色带展示。这三种方法各有各的优点和缺点，相信大家心里也有数。

看完了快排算法的可视化，我们再来看看归并排序

上面是归并排序的代码，效果如下图

与快速排序不同，归并排序需要用到额外的存储空间，所以在动画中我们用到了两行来进行演示。归并排序的原理也很好理解，就是把两个相邻的有序表归并为一个新的有序表。

关键步骤如下

不过我们也不能一味的追求炫丽的视觉效果，因为我们的最终目的是学习和理解算法的本质，而不是仅仅局限在一个数据集上。

这里我们可以通过数据最终的展示形式将算法可视化划分为三个层次：

Level 0/黑盒——这是最简单的一类，就是只展示最终结果，我们看不到算法运行的过程，但是可以判断算法的正确性。用这种形式来展示更有助于我们比较不同算法之间结果。我们也可以将黑盒可视化与其他更深层次的分析方法结合起来，如前面洗牌算法部分用到的展示算法偏差方法。

Level 1/灰盒——许多算法是逐渐生成最终结果的，通过观察算法过程中的一些关键步骤有助于我们理解算法的运行过程，而且我们也不需要引入什么新的名词概念，因为中间过程的结构和最终结果的结构是相似的。但是灰盒可视化也会引入更多问题，因为它并没有触及到算法的本质，大家往往搞不清为什么算法的中间过程是这样的。