本港台开奖现场直播 j2开奖直播报码现场
当前位置: 新闻频道 > IT新闻 >

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空(5)

时间:2016-12-07 13:05来源:118图库 作者:www.wzatv.cc 点击:
随机比较器洗牌的行为在很大程度上取决于浏览器。不同的浏览器使用不同的排序算法,并且不同的排序算法与(破坏了的)随机比较器表现非常不同。这

  随机比较器洗牌的行为在很大程度上取决于浏览器。不同的浏览器使用不同的排序算法,并且不同的排序算法与(破坏了的)随机比较器表现非常不同。这里是随机比较器在Firefox上洗牌的结果:

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空

  这是非常失偏的!所得到的数组通常几乎没有洗过牌,如该矩阵中的强绿色对角线所示。这并不意味着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直播,那就是时间映射到时间:我们可以简单地观察算法如何进行。但是虽然直观,动画也可以让人在看的时候感到沮丧,特别是如果我们想关注偶然的、奇怪的算法的行为。动画也严重依赖我们的记忆来观察行为模式。虽然通过控制以暂停和擦洗时间来改进动画,但是同时展示一切的静态显示甚至可以更有效。眼睛扫描比手动要快。

  将动画转换为静态显示的一种简单方法是从动画中选择关键帧,并按顺序显示,如同漫画一样。如果我们在关键帧之间删除冗余信息,我们会更有效地使用空间。更密集的显示可能需要更多的研究来理解,但是可以更快地扫描,因为眼睛移动较少。

  下面,每一行显示递归之前的数组的状态。第一行是数组的初始状态,第二行是第一次分区操作之后的数组,第三行是第一个分区的左右部分再次被分区之后的数组等等。实际上,这是广度优先快速排序,其中左右两侧的分区操作并行进行。

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空

  与之前一样,每个分区操作的基准以红色突出显示。请注意,在下一级递归处,基准将变为灰色:分区操作完成后,关联的基准处于其最终的排序位置。显示的总深度是递归的最大深度,给出了快速排序执行如何有效的感觉。它在很大程度上取决于输入和基准选择。

(责任编辑:本港台直播)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
栏目列表
推荐内容