JavaScript数据结构排序
JavaScript数据结构排序
Acce1erator 发表于2年前
JavaScript数据结构排序
  • 发表于 2年前
  • 阅读 25
  • 收藏 1
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 本文通过JS的canvas API,展示常见的几种排序算法的作用过程.
<!-- 
/**
 * @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 -->

 

共有 人打赏支持
粉丝 20
博文 25
码字总数 18001
×
Acce1erator
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: