技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 使用Jscex实现排序算法动画

使用Jscex实现排序算法动画

浏览:2350次  出处信息

    用动画来观察排序算法是一件很酷的事情,例如有人便为各种排序算法提供了动画效果。只可惜这些效果都是实现准备好的gif图片,并非由代码写成。在大部分平台上编写这样的程序并没有太大困难,只要在绘制出图形之后短暂地阻塞线程就行了。可惜,在JavaScript中我们只能“一蹴而就”,要暂停的话,只能使用setTimeout进行回调了。不过,这也正是Jscex的用武之地,用Jscex编写的代码需要“暂停”,只需要简单地调用sleep异步方法,一切都很直接。

    例如,传统的冒泡排序算法,使用JavaScript实现可能是这样的:

var bubbleSort = function (array) {
    for (var x = 0; x < array.length; x++) {
        for (var y = 0; y < array.length - x; y++) {
            if (array[y] > array[y + 1]) {
                swap(array, y, y + 1);
            }
        }
    }
}

    如果使用Jscex,则变成了:

var bubbleSortAsync = eval(Jscex.compile("$async", function (array) {
    for (var x = 0; x < array.length; x++) {
        for (var y = 0; y < array.length - x; y++) {
            var r = $await(compareAsync(array[y], array[y + 1]));
            if (r > 0) {
                $await(swapAsync(array, y, y + 1));
            }
        }
    }
}));

    算法实现上唯一的变化可能就是“比较”方法被独立成单独的compareAsync方法了。它和swapAsync方法的代码如下:

var compareAsync = eval(Jscex.compile("$async", function (x, y) {
    $await(Jscex.Async.sleep(10));
    return x - y;
}));

var swapAsync = eval(Jscex.compile("$async", function (array, x, y) {
    var t = array[x];
    array[x] = array[y];
    array[y] = t;

    repaint(array);

    $await(Jscex.Async.sleep(20));
}));

    简单地说,一个排序算法的性能如何,关键看它的比较和元素交换的次数。因此,我在compareAsync和swapAsync方法中都使用sleep进行了一定时间的停顿(其中后者更长一些)。由于改变了元素位置,因此在swapAsync方法中我还重新绘制了图案。有了这两个方法,我们只要将其简单地组合进bubbleSortAsync方法中即可。

    我们轻松实现的冒泡排序算法,Jscex编译器则会将其转化为复杂的Monadic代码,我本想贴在这里,但发现过于复杂凌乱,也太占地方。如果您感兴趣可以打开浏览器的console窗口,查看其输出结果。基于Jscex实现的选择排序和快速排序也和传统实现可谓毫无二致:

var selectionSortAsync = eval(Jscex.compile("$async", function (array) {
    for (var j = 0; j < array.length - 1; j++) {
        var mi = j;
        for (var i = j + 1; i < array.length; i++) {
            var r = $await(compareAsync(array[i], array[mi]));
            if (r < 0) { mi = i; }
        }
        $await(swapAsync(array, mi, j));
    }
}));

var quickSortAsync = eval(Jscex.compile("$async", function (array) {
    $await(_quickSortAsync(array, 0, array.length - 1));
}));

var _quickSortAsync = eval(Jscex.compile("$async", function (array, begin, end) {
    var index = $await(_partitionAsync(array, begin, end));

    if (begin < index - 1) {
        $await(_quickSortAsync(array, begin, index - 1));
    }

    if (index < end) {
        $await(_quickSortAsync(array, index, end));
    }
}));

var _partitionAsync = eval(Jscex.compile("$async", function (array, begin, end) {
    var i = begin;
    var j = end;
    var pivot = array[Math.floor((begin + end) / 2)];

    while (i <= j) {
        while (true) {
            var r = $await(compareAsync(array[i], pivot));
            if (r < 0) { i++; } else { break; }
        }

        while (true) {
            var r = $await(compareAsync(array[j], pivot));
            if (r > 0) { j--; } else { break; }
        }

        if (i <= j) {
            $await(swapAsync(array, i, j));
            i++;
            j--;
        }
    }

    return i;
}));

    言止于此,我们现在就来看一下(冒泡选择快速)三种排序方式的动画吧(请使用支持canvas的浏览器,例如IE 9、FireFox、Chrome、Safari)。我很难想象,使用传统方式实现一个快速排序的动画会是什么情况。

    我最近愈发懒惰,愈发不愿意去想这些事情了。如今Jscex已经支持JavaSript语言中绝大部分语言特性,包括条件判断,各种循环(以及循环中的break和continue),还有异常处理等等。对于Jscex带来的编程体验我有十足的信心,但现在的最大问题却是不知道该如何推广。我也希望可以有更多人可以参与并接受这个项目。之前想过用它来实现一个小游戏等等,但素材方面却总是难以落实。我十分希望能从您那里得到各方面的意见和建议。

建议继续学习:

  1. 如何使用1M的内存排序100万个8位数    (阅读:10910)
  2. 快速排序(Quicksort)的Javascript实现    (阅读:10100)
  3. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读:9047)
  4. jQuery Color Animations颜色动画插件    (阅读:7092)
  5. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读:6197)
  6. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读:5994)
  7. css3-animation制作逐帧动画    (阅读:5322)
  8. Java程序员必知的8大排序算法    (阅读:4461)
  9. Mysql中的排序优化    (阅读:4367)
  10. Vim(gVim)对排序的妙用    (阅读:4225)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1