使用Jscex实现排序算法动画
用动画来观察排序算法是一件很酷的事情,例如有人便为各种排序算法提供了动画效果。只可惜这些效果都是实现准备好的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带来的编程体验我有十足的信心,但现在的最大问题却是不知道该如何推广。我也希望可以有更多人可以参与并接受这个项目。之前想过用它来实现一个小游戏等等,但素材方面却总是难以落实。我十分希望能从您那里得到各方面的意见和建议。
建议继续学习:
- 如何使用1M的内存排序100万个8位数 (阅读:10868)
- 快速排序(Quicksort)的Javascript实现 (阅读:10074)
- 腾讯-1亿个数据取前1万大的整数-题解答 (阅读:9025)
- jQuery Color Animations颜色动画插件 (阅读:7069)
- 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序) (阅读:6167)
- 深入浅出交换类排序算法(冒泡排序,快速排序) (阅读:5970)
- css3-animation制作逐帧动画 (阅读:5297)
- Java程序员必知的8大排序算法 (阅读:4439)
- Mysql中的排序优化 (阅读:4339)
- Vim(gVim)对排序的妙用 (阅读:4206)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:老赵 来源: 老赵点滴
- 标签: Jscex 动画 排序
- 发布时间:2011-04-27 23:51:44
- [68] Go Reflect 性能
- [68] 如何拿下简短的域名
- [67] Oracle MTS模式下 进程地址与会话信
- [62] IOS安全–浅谈关于IOS加固的几种方法
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [48] 读书笔记-壹百度:百度十年千倍的29条法则