使用Jscex实现排序算法动画
2011-03-10 23:35 by 老赵, 4672 visits用动画来观察排序算法是一件很酷的事情，例如有人便为各种排序算法提供了动画效果。只可惜这些效果都是实现准备好的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至2名ASP.NET程序员：
- 岗位职责：负责服务器及数据库的搭建、维护工作，并配合前端工程师完成网站架构。
- 岗位要求：熟悉.NET 3.5开发，有关系型数据库（MySQL优先）开发管理经验。有MongoDB等NoSQL开发经验者优先。有网站数据负载均衡经验者优先。
- 办事认真踏实，对行业充满热情，了解行业最新动态。
很显然，这不是我的招聘需求，不过我也帮忙筛选面试。欢迎大家自荐或推荐，邮件请至：
。
有工具可以将compile放在js发布之前，而不是运行时。友好的调试支持。文档。