用Javascript写排序算法的动画演示-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

用Javascript写排序算法的动画演示

知与谁同 2018-07-21 15:04:27 1017
用Javascript写排序算法的动画演示
JavaScript 前端开发 搜索推荐
分享到
取消 提交回答
全部回答(2)
  • icebergyao
    2019-07-17 22:50:43

    推荐参考十大算法排序 javascript 版本相关的详细介绍,内含排序动画:https://www.cnblogs.com/herozhi/p/5880939.html

    0 0
  • liujae
    2019-07-17 22:50:43
    1.让JavaScript暂停下来,慢下来。
    JavaScript排序是很快的,要我们肉眼能看到它的实现过程,我首先想到的是让排序慢下来。 排序的每一个循环都让它停300ms然后再继续进行。 怎么样才能停下来呢。查了一下JavaScript貌似没有sleep()这样的函数。暂停做不到,但是可以想办法让实现跟暂停差不多的效果。比如在循环里做一些无关的事情 。
    首先尝试了让while(true)来一直执行一个空操作。执行一段时间再回到排序逻辑。代码大致是这样:
    for (var i = 0; i < 3; i++) {
    document.writeln(i); //DOM操作
    var now = new Date().getTime();
    while(new Date().getTime() - now < 3000){}
    }

    慢是慢下来了。不过太耗资源,排序进行过程中dom并不会有任何改变,直到排序结束, DOM会变成排序好之后的样子。 但是如果设置断点一步步执行的时候 又可以看到一步步的排序变化。估计是因为这个操作太耗资源导致浏览器下达了一个DOM操作的命令但是一直腾不出资源来进行DOM操作。所以真正DOM操作的时候在js代码执行结束之后。
    所以让JavaScript排序慢来来还是没有实现。
    另一种让JavaScript暂停下来的思路:
    写这个文章的时候又想到一种方法来让JavaScript停下来。 那就是AJAX的同步请求,以及超时操作。 也就是在要停下来的地方放一个AJAX请求,同步请求, 然后设置超时。超时的时间就是我们要暂停的时间。为了避免在到达超时请求之前服务 器就返回了我们的AJAX请求。可以在服务端运行类似 sleep()的程序 。从而保证AJAX不会返回。直接超时然后返回到我们的循环。不过这只是个设想。有兴趣的可以去尝试一下。
    2.闭包和定时器。 这种思路不需要让排序过程慢下来。而是使用闭包缓存排序过程中数组的变化。然后使用setTimeout来确定展示每一个数组状态的顺序。在排序循环中放入类似下面的代码。
    (function(){
    var theArr = arr.slice();//当前数组状态的备份
    setTimeout(function(){
    bubbleSortDom(theArr);//排序的DOM操作。
    },500*timeCount);
    timeCount++;//定时器的顺序。
    })();

    不过后来发现这样子写的话代码量会比较大,逻辑有修改的话要修改的地方会有点多。局限性很多,比如要实现排序动画加快或减慢操作几乎是很困难的。所以还要另想办法。
    3.缓存排序中的数组状态。
    也就是在排序过程中。将数组的每一轮循环的状态保存到一个数组。然后再用这个数组依次将排序状态保存下来。 只需要在排序中加入一句就行。
    this.pushHis(arr.slice(),i-1,j,k,temp);

    这样就只需要一个setInterval()就可以了。并且可以很方便的实现动画的加快与减慢。逻辑也比较好理解 。
    问题二:如何实现JavaScript排序动画的加快与减慢。
    我们问题一使用的第三种方法。 得到一个保存了每一步排序状态的数组arr。 然后我们可以使用一个setInterval()定时器一步步展现排序状态。 如果要加快速度或减慢速度。就clearInterval(),修改定时器的执行间隔,重新setInterval(),从前一个定时器执行到数组中的位置开始执行。
    问题三:对于使用递归实现的数组怎么办。 不是在原数组上进行操作的怎么办。
    使用递归实现的排序。 可能并没有在一个数组上进行操作,只是最后返回一个排序好的数组出来。那么我们要如何获得排序中的数组的完整状态呢。
    比如快速排序。
    最开始不考虑动画,我的实现是这样的:
    function quickSort(arr){
    var len = arr.length,leftArr=[],rightArr=[],tag;
    if(len<2){
    return arr;
    }
    tag = arr[0];
    for(i=1;i<len;i++){
    if(arr[i]<=tag){
    leftArr.push(arr[i])
    }else{
    rightArr.push(arr[i]);
    }
    }
    return quickSort(leftArr).concat(tag,quickSort(rightArr));
    }

    然后为了考虑动画,我改写了它的逻辑,让它在同一个数组上进行了实现。 其实是在递归的时候传入了当前的的子数组在原数组中的起始位置。从而在原数组上进行了操作。
    用了两种方法来实现方式。在排序逻辑上略有不同。
    第一种是先跟远处的对比。遇到比自己小的放到自己前面去。循环序号+1。比自己大的放到当前排序子数组的最后面去,循环序号不变。直到排列完成。
    这种方法的缺点是即使是一个有序数组。它也会重新排。
    第二种方法是 除了标记位,再设置一个对比位。 遇到比自己小的,放到前面去,标记位的位置+1,标记位与对比位之间所有的往后面移动一个位置。
    遇到比自己大的。标记位不变,对比位+1。
    这种方法的缺点是对数组进行的操作太多。优点是对有序数组不会再排。
    方式一:
    function quickSort(arr,a,b,qArr){

    var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
    if(a == undefined && b == undefined){
    a = 0; b= arr.length-1;//初始化起始位置。
    }
    if(qArr == undefined){
    qArr = arr.slice();
    }

    if((len == 2 && arr[0] == arr[1])||len<2){
    return arr;
    }

    tag = qArr[a];
    for (i = 1; i < len;) {
    if(qArr[a+i]<=tag){
    leftArr.push(qArr[a+i]);
    qArr[a+i-1] = qArr[a+i];
    qArr[a+i] = tag;
    k = a+i;
    i++;
    }else{
    if(leftArr.length+rightArr.length == len-1){
    break;
    }
    temp = qArr[a+i];
    qArr[a+i] = qArr[b-rightArr.length];
    qArr[b-rightArr.length] = temp;
    rightArr.push(temp);
    k = a+i-1;
    }
    this.pushHis(qArr.slice(),a,b,k);
    }

    len_l = leftArr.length;
    len_r = rightArr.length;
    if(len_l== 0){
    lb = a;
    }else{
    lb = a+len_l -1;
    this.sort(leftArr,a,lb,qArr);
    }

    if(len_r == 0){
    ra = b;
    }else{
    ra = b + 1 - len_r;
    this.sort(rightArr,ra,b,qArr)
    }
    return qArr
    }

    方式二:
    function quickSort2(arr,a,b,qArr){
    var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
    if(a == undefined && b == undefined){
    a = 0; b= arr.length-1;//初始化起始位置。
    }
    if(qArr == undefined){
    qArr = arr.slice();
    }
    if(len<2){
    return arr;
    }
    if(len == 2 && arr[0] == arr[1]){
    return arr;
    }
    tag = qArr[a];
    for (i = 1,k = 0; i < len;) {
    if(qArr[a+i]>=tag){
    rightArr.push(qArr[a+i]);
    i++;
    }else{
    temp = qArr[a+i];
    for(j = a+i;j>a+k;j--){
    qArr[j] = qArr[j-1];
    // this.pushHis(qArr.slice(),a,b,a+k);
    }
    qArr[a+k] = temp;
    leftArr.push(temp);
    k++;
    i++;
    }
    this.pushHis(qArr.slice(),a,b,a+k,i-1);
    }
    len_l = leftArr.length;
    len_r = rightArr.length;
    if(len_l== 0){
    lb = a;
    }else{
    lb = a+len_l -1;
    this.sort(leftArr,a,lb,qArr);
    }
    if(len_r == 0){
    ra = b;
    }else{
    ra = b + 1 - len_r;
    this.sort(rightArr,ra,b,qArr)
    }
    return qArr;
    }

    具体的不同下面会有动画演示。
    问题四:动画的流畅。
    排序动画的DOM操作是很多的很快的。这里我做的优化只是让每一个排序步骤只涉及一个DOM操作。 全部由JavaScript拼接好,一次替换。类似下面的代码。
    效果图:

    主要实现了:
    冒泡排序JavaScript动画演示
    插入排序JavaScript动画演示
    选择排序JavaScript动画演示
    快速排序JavaScript动画演示
    归并排序JavaScript动画演示
    希尔排序JavaScript动画演示
    0 0
添加回答
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题