JavaScript 实现排序算法可视化手记

2016-10-07 本文已影响876人未枝丫

原创文章，未经许可，请勿转载
©Soyaine

这两天找了个没网的地方，总算把之前遗留下的排序可视化实现了，现在初步完成了冒泡排序和选择排序，写这篇是为了整理一下从零到实现的过程，也分享自己的解决思路，欢迎多多交流。

（很牛的视频链接列表。）

下面主要记录下选择排序的实现。

失败的尝试

还没开始做时，觉得只要在排序时每一步高亮一个数据块，就能实现了。于是能想到的最简单的是，写一个实现暂停的 sleep 函数，在每次循环后暂停，操作 DOM。我经历过的失败的尝试有：

在循环中操作节点样式，无法控制延迟时间
在循环中混入 setTimeOut
在循环中混入元素交换的操作

浏览器的渲染机制及定时器机制

浏览器渲染

浏览器是单线程的，UI 引擎和 JS 引擎互斥，也就是说，在循环运行的过程中， JS 引擎在执行循环操作时，无法调用 UI 引擎。所以涉及到重新渲染页面的操作不会立即执行，而是会排到任务队列中，等循环结束（JS 引擎空闲）时再执行渲染。所以能看到的效果是，页面假死，到最后突然变成排序结束的样子。

这时候就需要用到定时器，具体用法参见文档。

在将 setTimeOut 和 for/while 循环一起使用的过程中，我遇到了两个问题：

时序混乱。它也会在循环结束后才统一渲染，有可能会出现交叉的情况。
参数无法正确的传递。具体的问题是 setTimeOut 内函数真正执行时，所读取到的是循环结束后的值，而不是想象的每次循环传递一个参数（参见 stackOverflow 的问题）。

由此进化得到的解决办法是，把排序和渲染分离，排序时专注于数据的循环比较，得出每一帧所涉及到的节点索引以及对应状态，存入队列备后续渲染使用，渲染时根据上一步提供的单帧数据，用定时器进行 DOM 操作实现一步一步的动画呈现。

setTimeOut 的循环实现

之所以会考虑将每帧的情况存入数列之后，再统一渲染，这是在用 setTimeOut 实现循环的过程中发现的。

Nicholas 在《JavaScript高级程序设计》中优化性能的思路是将需要长时间运算的循环分解为“片”来进行运算：

// http://www.nczonline.net/blog/2009/01/13/speed-up-your-javascript-part-1/
function chunk(array, process, context){
  var items = array.concat();   //clone the array
  setTimeout(function(){
    var item = items.shift();
    process.call(context, item);

    if (items.length > 0){
      setTimeout(arguments.callee, 100); 
    }
  }, 100);
}

可以注意到其中 setTimeout(arguments.callee, 100) 一句将会为新的数据设定一个新的 timer。借用这种方法，我们可以实现数组元素的遍历，即存入需要渲染的数据之后，只需使用 setTimeOut 依次读取每条数据进行渲染即可。

选择排序的分解

拿选择排序来举例，为便于描述，下面我用外循环和内循环来指代选择排序嵌套的两层循环。

var arr; //待排序数组
var min; //存最小值
for (var outer = 0; outer < arr.length-1; outer++){
  min = outer;
  for (var inner = outer+1; inner < arr.length; inner++){
    if (arr[min] > arr[inner]){
      min = inner;
    }
  }
  swap(arr, min, inner);
}

下面这张图是我的解决思路，主要有两部分，一是 Array（排序数据）操作，二是 DOM 操作，包括样式和高度的改变。

hand writer

DOM 单帧分解

下面来设想一下排序过程中所涉及到的每一帧是以什么样的样式出现。可以回看上面的几个视频，思考过程是这样，把整个排序过程分解，每一步也就对应了我们后来的每一帧。

想象我需要实现的效果：

arr[0] 高亮
arr[1] 高亮
if (arr[min] > arr[1])
1. true : arr[1] 标记为最小值
2. false : arr[1] 取消高亮
arr[2] 高亮
……循环

上面的过程中，为了区分不同类型的数，思考一下有哪些状态：

select: 待交换，每轮外循环所选定的值
on: 正在比较中，即每轮内循环依次遍历的值
min: 内循环的目的是找到此轮的最小值，所以每次比较都会产生当前的最小值，需要区分
sorted: 已完成排序，每轮内循环结束并完成交换后，当前外循环选定的值已完成排序

将以上几种状态对应到不同的 CSS 样式，之后渲染的时候只需要通过操作样式表即可实现不同状态的标识：

/**
 * 渲染每一步
 * @param main 外循环的主数
 * @param div 被比较的用于操作的 div
 * @param state 操作涉及的样式名称
 * @param on 添加或去除样式、
 */
function renderSelectionDiv(main, div, state, on){
    var onDiv = document.getElementById(div.toString());
    if(on == 1){
        if (state == ""){
            //    交换
            var outerDiv = document.getElementById(main.toString());
            swap(outerDiv, onDiv);
        }else{
            onDiv.classList.add(state);
        }
    }else {
        onDiv.classList.remove(state);
    }
}

Array 排序分解

之所以先写上面的部分，是为了便于理解。实际过程中，我是先从排序时的循环过程开始尝试，然后思考每帧需要的数据，之后再回过头来修正这一部分中的数据格式。

考虑排序过程中的两层循环，重点注意下标的变化过程：

外循环是从 0 → 数组倒数第二位
内循环是从 此轮外循环的值 → 数组最后一位。

理解循环的过程不难，较为繁琐的是理清每一步所需的操作是什么，将上一部分中所设想的样式变换插入到排序的循环中，下面是我的代码：

/**
 * 提供外层循环的 selected 值，及内层循环数组
 * @param outerId
 * @param innerQueue
 * @param timerQueue
 */
function getMin(outerId, innerQueue, timerQueue){
    var outerDiv = data[outerId];
    var minId = outerId;
  
    // 选中外层循环主值
    timerQueue.push([outerId, outerId, "select", 1]);

    while(innerQueue.length > 0){
        // 将需要比较的数存入数列
        var innerId = innerQueue.shift();

        var minDiv = data[minId];
        var innerDiv = data[innerId];

        timerQueue.push([outerId, innerId, "on", 1]);

        if(minDiv > innerDiv){
            // 修改最小值
            timerQueue.push([outerId, minId, "min", 0]);
            timerQueue.push([outerId, minId, "on", 0]);

            minId = innerId;

            timerQueue.push([outerId, minId, "min", 1]);

        }else {
            timerQueue.push([outerId, innerId, "on", 0]);
        }
    }

    // 交换
    timerQueue.push([outerId, minId, "", 1]);
    swapData(outerId, minId);
    // 去除最小值标识
    timerQueue.push([outerId, minId, "min", 0]);
    timerQueue.push([outerId, minId, "on", 0]);
    // 已排序标识
    timerQueue.push([outerId, outerId, "sort", 1]);
    // 去除选中值标识
    timerQueue.push([outerId, outerId, "select", 0]);
    timerQueue.push([outerId, outerId, "min", 0]);
    
    return timerQueue;
}

后

这里很简单，但忍不住想要打一个比喻。

想象我们在为电影写剧本，需要提前写好每个镜头所涉及到的演员和表演场景，演员安排即是 Array 操作部分进行管理，而具体的场景则是 DOM 操作部分。

写好剧本之后，交给 setTimeOut ，它将按照剧本的要求，召集人员进行拍摄，然后提供给浏览器播放出来。

如果上面我说得不是很清楚，那么带着这样的想象，回去思考这个过程，会很容易明白。欢迎批评指正。