文档章节

JavaScript数据结构排序

Acce1erator
 Acce1erator
发布于 2016/06/15 16:40
字数 1103
阅读 38
收藏 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
粉丝 23
博文 25
码字总数 18001
作品 0
朝阳
程序员
私信 提问
用js来实现那些数据结构及算法—目录

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

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

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

eternalless
09/07
0
0
13 个最佳 JavaScript 数据表格库

JavaScript 是一种通常被用在网页开发中的编程语言。它主要是在互联网上的网页浏览器中开发出效果出众且可交互的特效。它是客户端脚本语言中的一种,是被用来作为通过用户的网页浏览器进行处...

oschina
2017/03/10
5K
7
深度理解 Virtual DOM

目录: 1 前言 2 技术发展史 3 Virtual DOM 算法 4 Virtual DOM 实现 5 Virtual DOM 树的差异(Diff算法) 6 结语 7 参考链接 1 前言 我会尽量把 Virtual DOM 应用场景、实现思路、算法讲述清...

大灰狼的小绵羊哥哥
11/19
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

没有更多内容

加载失败,请刷新页面

加载更多

python自然语言处理快速入门2常见的NLP操作

在本章中,我们将讨论我们文本数据进行的一些常见数据预处理操作,以适配典型的机器学习算法,如贝叶斯、决策树,逻辑回归等等。这些算法都只适用于数字向量,而不是文本。 那么我们如何将文...

python测试开发人工智能安全
18分钟前
0
0
OSChina 周一乱弹 —— 温柔的人应该这样

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @clouddyy :#每日一歌# 《フィクション-sumika》 《フィクション-sumika》 手机党少年们想听歌,请使劲儿戳(这里) 假期时间干嘛去, @for...

小小编辑
35分钟前
9
4
[LintCode] Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)

描述 设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。 如何反序列化或序列化二叉树是没有限制的,你...

honeymose
今天
6
0
java框架学习日志-7(静态代理和JDK代理)

静态代理 我们平时去餐厅吃饭,不是直接告诉厨师做什么菜的,而是先告诉服务员点什么菜,然后由服务员传到给厨师,相当于服务员是厨师的代理,我们通过代理让厨师炒菜,这就是代理模式。代理...

白话
今天
26
0
Flink Window

1.Flink窗口 Window Assigner分配器。 窗口可以是时间驱动的(Time Window,例如:每30秒钟),也可以是数据驱动的(Count Window,例如:每一百个元素)。 一种经典的窗口分类可以分成: 翻...

满小茂
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部