快速排序

作者: duJing | 来源:发表于2017-01-04 15:06 被阅读12次

七大排序算法之快速排序
面试准备--排序
排序
算法笔记01-排序#2
PHP 实现快速排序
快速排序的Python实现
数据结构与算法快速排序
数组-快速排序
OC数据结构&算法
要成功就做一百题-94

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>快速排序</title>
</head>
<body>
<script>
    /*
     * 引子：
     * 在JS中，Array.prototype.sort 方法已经封装了排序方法，
     * 最多我们需要自己定义一个排序规则函数扔到sort方法中实现自定义排序
     * */

    /*var arr = [3, 45, 23, 8, 45, 12, 299, 1];
     (function (arr) {
     var res = arr.sort(function (a, b) {
     return a - b;
     });
     console.log(res);   // [1, 3, 8, 12, 23, 45, 45, 299]
     })(arr);*/





    /*
     * 其实上面的排序基本上够我们在平时中使用了，
     * 但是在排序中，快速排序才是效率最高的排序方法之一
     *
     * 快速排序：
     * 1.找出一个数组的中间点
     * 2.建立两个数组，将原数组中小于中间点的值放入左边数组
     * 将原数组中大于中间点的值放入右边数组
     * 3.利用递归排序下去
     * */

    var arr = [3, 45, 23, 8, 45, 12, 299, 1, 24, 6, 3];
    var res = (function (arr) {
        // 递归终止条件
        if (arr.length <= 1) {
            return arr;
        }
        // 中间点
        var middle = Math.floor(arr.length / 2);
        var middleArr = arr.splice(middle, 1);
        // 创建两个数组
        var left = [];
        var right = [];
        // 遍历原数组
        for ( var i = 0; i < arr.length; i++ ) {
            arr[i] <= middleArr[0] ? left.push(arr[i]) : right.push(arr[i]);
        }
        return arguments.callee(left).concat(middleArr, arguments.callee(right));
    })(arr);
    console.log(res);


</script>
</body>
</html>