文档章节

JavaScript数据结构排序

Acce1erator
 Acce1erator
发布于 2016/06/15 16:40
字数 1103
阅读 33
收藏 1
点赞 0
评论 0
<!-- 
/**
 * @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
粉丝 21
博文 25
码字总数 18001
作品 0
朝阳
程序员
六种排序算法的JavaScript实现以及总结

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

DM.Zhong ⋅ 05/24 ⋅ 0

前端基础之JavaScript

一、JavaScript的历史 略 二、ECMAScript 注:ES6就是指ECMAScript 6。 尽管 ECMAScript 是一个重要的标准,但它并不是 JavaScript 唯一的部分,当然,也不是唯一被标准化的部分。实际上,一...

西鼠 ⋅ 05/09 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

15个必备的javascript小技巧,看的懂是入门,全会写就是大神

1、变量转换 看起来很简单,但据我所看到的,使用构造函数,像Array()或者Number()来进行变量转换是常用的做法。始终使用原始数据类型(有时也称为字面量)来转换变量,这种没有任何额外的影...

急速奔跑中的蜗牛 ⋅ 06/06 ⋅ 0

WebAssembly 时代,Rust 也想成为 Web 语言

目前 Mozilla 正在基于 WebAssembly 可移植代码格式研发 JavaScript 和 Rust 之间的桥梁——wasm-bindgen,意义是提高 JavaScript 和 Rust 之间的互操作性。Mozilla 这么做是想让 Rust 成为类...

开源中国 ⋅ 04/10 ⋅ 0

第一章--JavaScript简介

1. JavaScript的构成 1.1. ECMAScript ECMAScript规定了核心语言的组成部分分别为:语法、类型、语句、关键字、保留字、操作符、对象。 宿主环境:Web浏览器、Node、Adobe Flash。 1.2. DOM...

lovewt ⋅ 06/05 ⋅ 0

从JS对象开始,谈一谈“不可变数据”和函数式编程

文章转载自:https://segmentfault.com/a/1190000008780076 作为前端开发者,你会感受到JS中对象(Object)这个概念的强大。我们说“JS中一切皆对象”。最核心的特性,例如从String,到数组,再...

朱先忠老师 ⋅ 05/20 ⋅ 0

JSON,异步加载(学习笔记)

JSON是一种传输数据的格式(以对象为样板,本质上就是对象,但用途有区别,对象就是本地用的,json是用来数据传输的,前端与后端的数据通信) JSON是静态类(不需要构造),类似于Math,内部...

Mrs_CoCo ⋅ 04/23 ⋅ 0

四月前端知识集锦(每月不可错过的文章集锦)

目前自己组建的一个团队正在写一份面试图谱,将会在七月中旬开源。内容十分丰富,第一版会开源前端方面知识和程序员必备知识,后期会逐步写入后端方面知识。因为工程所涉及内容太多(目前已经...

夕阳 ⋅ 05/02 ⋅ 0

你不懂js系列学习笔记-异步与性能- 05

第五章: 程序性能 原文:You-Dont-Know-JS 这本书至此一直是关于如何更有效地利用异步模式。但是我们还没有直接解释为什么异步对于 JS 如此重要。最明显明确的理由就是 性能。 举个例子,如果...

寇格莫 ⋅ 05/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部