js快速排序标准版与简版

107 阅读 0 评论 71 点赞

我是靠谱客的博主阔达小松鼠，这篇文章主要介绍js快速排序标准版与简版，现在分享给大家，希望可以做个参考。

快速排序的核心思想非常简单：

在数组中，找一个基准点P，然后splice出去；
将数组中小于改基准点的数据放在一个数组，大于基准点的数据放在一个数组；
对左边的数组进行递归操作，对右边的数组递归操作，最后concat起来，并返回

标准思想：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(arr) {
    arr = arr.concat();
    if(arr.length<=1){
        return arr
    }
    let left=[], right=[];
     let basis = arr.splice(0,1);
    arr.forEach(function (v) {
        if(v<basis){
            left.push(v)
        }else{
            right.push(v)
        }
    });
    return quickSortTwo(left).concat(basis,quickSortTwo(right))
}

第二种，使用数组的首个元素作为基准点，然后利用filter函数过滤并返回新数组，最后递归：

复制代码

1
2
3
function quickSort(arr) {
    return arr.length <=1 ? arr : quickSort(arr.slice(1).filter(v=> v<arr[0])).concat(arr[0],quickSort(arr.slice(1).filter(v=>v>=arr[0])))
}

快速排序还有很多优化的方法，阮老师的排序方法还是值得推荐的：

快速排序（Quicksort）的Javascript实现：http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html