文档章节

JavaScript数据结构排序

Acce1erator
 Acce1erator
发布于 2016/06/15 16:40
字数 1103
阅读 35
收藏 1
<!-- 
/**
 * @auther yuyuzhao
 * @since 2016年3月25日
 * @copyright Copyright (c) 2016 by ZhaoYuyu
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
 -->
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Animation of Sorting Methods</title>
<style>
#canvas {
    border: dashed 2px #CCC;
}
</style>
</head>
<body>
    <div>
        <canvas id="canvas" width="400" height="300"></canvas>
    </div>
    <div>
        <ul>
            <li><button id="bubbleBtn">冒泡排序</button></li>
            <li><button id="selectBtn">选择排序</button></li>
            <li><button id="insertBtn">插入排序</button></li>
            <li><button id="shellBtn">希尔排序</button></li>
            <li><button id="mergeBtn">归并排序</button></li>
            <li><button id="quickBtn">快速排序</button></li>
        </ul>
    </div>
</body>
<script type="text/javascript">
    (function() {
        'use strict';
        var ArraySort = function(size, bound) {
            if (typeof bound == 'undefined')
                bound = 100;
            this.array = new Array(size);
            for (var i = 0; i < size; i++)
                this.array[i] = parseInt(Math.random() * bound);
        };

        ArraySort.copyOf = function(arr) {
            return copyOf(arr);
        };

        ArraySort.prototype = {
            copy : function() {
                return copyOf(this.array);
            },
            bubbleSort : function(callback) {
                var arr = copyOf(this.array);
                var temp;
                for (var i = 1; i < arr.length; i++)
                    for (var j = 0; j < arr.length - i; j++)
                        if (arr[j] > arr[j + 1]) {
                            temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                            if (typeof callback == 'function')
                                callback(arr);
                        }
                return arr;
            },
            selectSort : function(callback) {
                var arr = copyOf(this.array);
                var max;
                var temp;
                for (var i = 1; i < arr.length; i++) {
                    max = 0;
                    for (var j = 1; j < arr.length - i + 1; j++)
                        if (arr[max] < arr[j])
                            max = j;
                    temp = arr[arr.length - i];
                    arr[arr.length - i] = arr[max];
                    arr[max] = temp;
                    if (typeof callback == 'function')
                        callback(arr);
                }
                return arr;
            },
            insertSort : function(callback) {
                var arr = copyOf(this.array);
                var mark;
                var temp;
                for (var i = 1; i < arr.length; i++) {
                    mark = 0;
                    while (arr[mark] < arr[i])
                        mark++;
                    if (mark < i) {
                        temp = arr[i];
                        for (var j = i; j > mark; j--)
                            arr[j] = arr[j - 1];
                        arr[mark] = temp;
                        if (typeof callback == 'function')
                            callback(arr);
                    }
                }
                return arr;
            },
            shellSort : function(callback) {
                var arr = copyOf(this.array);
                var h = 1;
                while (3 * h + 1 < arr.length)
                    h = 3 * h + 1;
                var mark;
                var temp;
                while (h >= 1) {
                    for (var i = 0; i < h; i++)
                        for (var j = 1; h * j + i < arr.length; j++) {
                            mark = i;
                            while (arr[mark] < arr[h * j + i])
                                mark += h;
                            if (mark < h * j + i) {
                                temp = arr[h * j + i];
                                for (var n = h * j + i; n > mark; n -= h)
                                    arr[n] = arr[n - h];
                                arr[mark] = temp;
                                if (typeof callback == 'function')
                                    callback(arr);
                            }
                        }
                    h = (h - 1) / 3;
                }
                return arr;
            },
            mergeSort : function(callback) {
                var arr = copyOf(this.array);
                coreMergeSort(0, arr.length - 1, arr, new Array(arr.length),
                        callback);
                return arr;
            },
            quickSort : function(callback) {
                var arr = copyOf(this.array);
                coreQuickSort(0, arr.length - 1, arr, callback);
                return arr;
            },
            defaultSort : function() {
                return Array.sort(copyOf(this.array));
            }
        };

        function copyOf(arr) {
            var newArr = new Array(arr.length);
            for (var i = 0; i < arr.length; i++)
                newArr[i] = arr[i];
            return newArr;
        }

        function coreMergeSort(begin, end, arr, temp, callback) {
            if (begin == end)
                return;
            var mid = Math.floor((begin + end) / 2);
            coreMergeSort(begin, mid, arr, temp, callback);
            coreMergeSort(mid + 1, end, arr, temp, callback);
            var i = begin;
            var j = mid + 1;
            for (var k = begin; k <= end; k++) {
                if (i <= mid && ((j <= end && arr[i] <= arr[j]) || j > end))
                    temp[k] = arr[i++];
                else
                    temp[k] = arr[j++];
            }
            for (var k = begin; k <= end; k++)
                arr[k] = temp[k];
            if (typeof callback == 'function')
                callback(arr);
        }

        function coreQuickSort(left, right, arr, callback) {
            if (left >= right)
                return;
            var pivot = arr[right];
            var i = left - 1;
            var j = right;
            var temp;
            while (i < j) {
                while (arr[++i] < pivot)
                    ;
                while (--j > 0 && arr[j] > pivot)
                    ;
                if (i < j) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    if (typeof callback == 'function')
                        callback(arr);
                }
            }
            arr[right] = arr[i];
            arr[i] = pivot;
            if (typeof callback == 'function')
                callback(arr);
            coreQuickSort(left, i - 1, arr, callback);
            coreQuickSort(i + 1, right, arr, callback);
        }

        window.ArraySort = ArraySort;

        var BarHelper = function(id) {
            var canvas = document.getElementById(id);
            this.g = canvas.getContext('2d');
            this.width = canvas.getAttribute('width');
            this.height = canvas.getAttribute('height');
        };

        BarHelper.prototype = {
            getGraphics : function() {
                return this.g;
            },
            erase : function() {
                this.g.clearRect(0, 0, this.width, this.height);
            },
            paint : function(arr) {
                var g = this.g;
                var w = this.width;
                var h = this.height;
                g.clearRect(0, 0, w, h);
                var dx = Math.floor(w / arr.length);
                for (var i = 0; i < arr.length; i++) {
                    if (arr[i] % 5 == 0)
                        g.fillStyle = '#ff6666';
                    else if (arr[i] % 5 == 1)
                        g.fillStyle = '#66ff66';
                    else if (arr[i] % 5 == 2)
                        g.fillStyle = '#6666ff';
                    else if (arr[i] % 5 == 3)
                        g.fillStyle = '#333333';
                    else if (arr[i] % 5 == 4)
                        g.fillStyle = '#cccccc';
                    g.fillRect(i * dx, h - arr[i], dx - 2, arr[i]);
                }
            }
        };

        window.BarHelper = BarHelper;
    })()
</script>
<script type="text/javascript">
    (function() {
        var sort = new ArraySort(30, 200);
        var helper = new BarHelper('canvas');
        var cache;
        var timer;

        var bind = function(domId, action, event) {
            var element = document.getElementById(domId);
            element.addEventListener(action, function() {
                event();
            }, false);
        };

        var init = function(method) {
            bind(method + 'Btn', 'click', function() {
                if (typeof timer != 'undefined')
                    clearInterval(timer);
                cache = [];
                if ('bubble' == method)
                    sort.bubbleSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                else if ('select' == method)
                    sort.selectSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                else if ('insert' == method)
                    sort.insertSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                else if ('shell' == method)
                    sort.shellSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                else if ('merge' == method)
                    sort.mergeSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                else if ('quick' == method)
                    sort.quickSort(function(arr) {
                        cache.push(ArraySort.copyOf(arr));
                    });
                timer = setInterval(function() {
                    if (cache.length == 0)
                        clearInterval(timer);
                    else
                        helper.paint(cache.shift());
                }, 500);
            })
        };

        init('bubble');
        init('select');
        init('insert');
        init('shell');
        init('merge');
        init('quick');
    })();
</script>
</html>

<!-- GitHub项目地址:https://github.com/YuyuZha0/SortAnimation -->

 

© 著作权归作者所有

共有 人打赏支持
Acce1erator
粉丝 22
博文 25
码字总数 18001
作品 0
朝阳
程序员
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
js实现数据结构及算法之排序算法

冒泡排序 冒泡排序是最慢的排序算法之一,数据值会像起跑一样从数组的一端漂浮到另一端 动画演示 js实现 选择排序 从数组的开头开始,将第一个元素和其他元素相比,最小的元素放在第一个位置...

eternalless
09/07
0
0
Immutable.js了解一下?

本篇只是对Immutable.js的简单介绍,后续会继续分享其具体实践应用。 什么是Immutable Data? Immutable data encourages pure functions (data-in, data-out) and lends itself to much si...

桂圆_noble
03/29
0
0
[译] 论 Rust 和 WebAssembly 对源码地址索引的极限优化

原文地址:Oxidizing Source Maps with Rust and WebAssembly 原文作者:Nick Fitzgerald 译文出自:掘金翻译计划 本文永久链接:github.com/xitu/gold-m… 译者:D-kylin Tom Tromey 和我尝...

LeviDing
07/16
0
0
六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong
05/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

给MySQL授权远程访问

putty登录服务器; 登录MySQL: mysql -u root -p 新建远程用户: CREATE USER 'myusername' IDENTIFIED BY 'mypassword'; 授权: grant all on *.* to john@'101.102.103.104' identified by......

sweethome
57分钟前
0
0
在t-io老巢造谣,不过有造谣的就会有反造谣的!

只发当事人的截图,不发表评论,以免有引导嫌疑 PS: 截图是由不同的人发过来的 本人已经不在此微信群 图3:有造谣的,就有反造谣的 图4是2018-09-23的t-io官方群的一个发言小统计,有助于让...

talent-tan
今天
99
0
heartbeat 资源

drbd+apache+heartbeat : http://blog.51cto.com/11838039/1827901 heartbeat双机热备的架设 : http://blog.51cto.com/11838039/1827560 对heaetbeat的深一步认识 : http://blog.51cto.co......

寰宇01
今天
4
0
Spring 转换 model 为 json 时增加属性

缘起 目前的项目中有个需求是在附件对象转换成 json 时增加个 url 属性,以前的方式是在返回附件对象或列表时候做一次统一处理,这次想看看 spring 或者 jackson fasterxml 是否自带类似功能...

郁也风
今天
4
0
10大PHP比特币开源项目

如果你是一个Phper,如果你希望学习区块链,那么本文列出的 10个开源的Php比特币项目,将有助于你了解在自己的应用中 如何加入对比特币的支持。 如果你希望快速掌握使用Php对接比特币钱包的方...

汇智网教程
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部