快速排序法 Quicksort

JavaScript 2017-03-09 快速排序,Quicksort,Tony Hoare

快速排序法(Quicksort)是目前排序算法里最常用的算法之一,由Tony Hoare于1959年开发,61年发布

引用Wiki

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959,[1] with his work published in 1961,[2] it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.[3]

这个gif图片特别明确地呈现了其实现原理

1、在数组所有元素中随机找一个基准值

2、所有小于基准点到左边,大于基准点到右边

3、左右两边的合集在进行以上两个步骤,排序完成

如:

[45, 20, 10, 28, 98, 67, 90]

以28为基准值

[45, 20, 10, 28, 98, 67, 90]

位移

[20, 10, 28, 45, 98, 67, 90]

左边的合集在找一个基准值

[20, 10]

排序后,变成

[10, 20]

右边的合集也找一个基准值

[45, 98, 67, 90]

排序后,变成

[45, 67, 98, 90]

以此类推,直到剩下最后一个数字

我们用程序实现一下:

var quickSort = (function(){
    var sort = function (arr) {
        // 这里要做一下判断,否则就死循环啦
        if (arr.length <= 1) {
            return arr;
        }

        // 定义左右合集
        var left = [];
        var right = [];

        for (var i = 1; i < arr.length; i++) {
            // 小于基准点到左边,否则到右边
            if (arr[i] < arr[0]) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }

        // 递归调用,最后拼接成数组返回
        return sort(left).concat(arr[0], (sort(right)));
    };

    return sort;
})();


var arr1 = [45, 20, 10, 28, 98, 67, 90];
console.log(quickSort(arr1)); // [ 10, 20, 28, 45, 67, 90, 98 ]

以上是JS实现方法,大家可以试试!

文字链接:《快速排序法 Quicksort

文章地址:http://www.qttc.net/201703479.html

除非标注,琼台博客所有博文均为原创,转载请加文字链接注明来源

乳名?小名?昵称?网名?均可

email,放心,我不会给你乱投广告的

想获得回访就把你的站点URL写上(没有留空)

[NOTICE]木要投放广告
[NOTICE]木要骂人,说不该说的话
[NOTICE]自由言论,但要遵纪守法

Comments 0

    Hi,你想第一个做沙发么?