随机比较器洗牌的行为在很大程度上取决于浏览器。不同的浏览器使用不同的排序算法,并且不同的排序算法与(破坏了的)随机比较器表现非常不同。这里是随机比较器在Firefox上洗牌的结果: 这是非常失偏的!所得到的数组通常几乎没有洗过牌,如该矩阵中的强绿色对角线所示。这并不意味着Chrome的排序是比Firefox的“更好”,它只是意味着不应该使用随机比较器洗牌。随机比较器从根本上被破坏了。 排序 排序是洗牌的逆过程——它从无序创建顺序,反之亦然。这使得排序成为更困难的问题,要为不同的权衡和约束设计各种解决方案。 最知名的排序算法之一是快速排序。 Quicksort首先通过选择一个基准将数组分成两个部分。 左半部包含所有小于基准的元素,而右半部包含大于基准的所有元素。在数组分区后,快速排序在左右两部分内递归。当每个部分只包含一个元素时,递归停止。 分区操作使得只在数组的活动部分上进行单一操作。类似于Fisher-Yates通过交换元素递增地建立洗牌区,分区操作递增地构建子阵列的较小(左)和较大(右)部分。当每个元素被访问时,如果它小于基准,它被交换到较小部分; 如果它大于基准,则分区操作移动到下一个元素。 ▼代码如下所示—— function quicksort(array, left, right) { if(left < right - 1) { var pivot = left + right >> 1; pivot = partition(array, left, right, pivot); quicksort(array, left, pivot); quicksort(array, pivot + 1, right); } } function partition(array, left, right,pivot) { varpivotValue = array[pivot]; swap(array, pivot, --right); for(var i = left; i < right; ++i) { if (array[i] < pivotValue) { swap(array, i, left++); } } swap(array, left, right); return left; } 快速排序有很多版本。上面显示的是最简单也是速度最慢的一个。这种变化对于教学是有用的,但是在实践中,为了得到更好的性能应用了更复杂的实现方法。 常见的改进是“三中值”枢轴选择,其中第一,中间和最后元素的中值被用作基准。这倾向于选择更接近真实中值的基准,导致类似大小的左半部分和右半部分以及递归层数更少。另一个优化是对于数组的小部分来说,从快速排序切换到插入排序,由于函数调用的开销问题这可以更快。 一个特别聪明的变化是Yaroslavskiy的双基准快速排序,它将数组分为三个部分,而不是两个。这是Java和Dart中的默认排序算法。 上面的排序和洗牌动画有不错的属性,atv直播,那就是时间映射到时间:我们可以简单地观察算法如何进行。但是虽然直观,动画也可以让人在看的时候感到沮丧,特别是如果我们想关注偶然的、奇怪的算法的行为。动画也严重依赖我们的记忆来观察行为模式。虽然通过控制以暂停和擦洗时间来改进动画,但是同时展示一切的静态显示甚至可以更有效。眼睛扫描比手动要快。 将动画转换为静态显示的一种简单方法是从动画中选择关键帧,并按顺序显示,如同漫画一样。如果我们在关键帧之间删除冗余信息,我们会更有效地使用空间。更密集的显示可能需要更多的研究来理解,但是可以更快地扫描,因为眼睛移动较少。 下面,每一行显示递归之前的数组的状态。第一行是数组的初始状态,第二行是第一次分区操作之后的数组,第三行是第一个分区的左右部分再次被分区之后的数组等等。实际上,这是广度优先快速排序,其中左右两侧的分区操作并行进行。 与之前一样,每个分区操作的基准以红色突出显示。请注意,在下一级递归处,基准将变为灰色:分区操作完成后,关联的基准处于其最终的排序位置。显示的总深度是递归的最大深度,给出了快速排序执行如何有效的感觉。它在很大程度上取决于输入和基准选择。 (责任编辑:本港台直播) |