js 排序算法之快速排序

Eidesen 发布于2019-08-23 11:38 / 970人阅读

摘要：快速排序是一种划分交换排序。快速排序基于冒泡递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。

快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序基于冒泡、递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。

最坏时间复杂度：O($n^2$)  当选择的基准值为最大值或最小值时
稳定性：不稳定
平均时间复杂度：O(n*$log_2$n)

阮一峰版内存占用较多

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
//  let pivot = arr.splice(pivotIndex, 1);  3 < [9] //true
    let left = [];
    let right = [];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和高速缓存的性能。

真正的快排

按照维基百科中的原地(in-place)分区版本，实现快速排序方法如下：

function quickSort(arr) {
    function swap(arr, i, k) {
        let temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    // 数组分区，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接选最右边的元素为基准元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
            } 
        }
        swap(arr, storeIndex, right); // 将基准元素放置到最后的正确位置上
        return storeIndex;
    }
    function sort(arr, left, right) {
        if(left > right) {
            return;
        }
        let storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
    sort(arr, 0, arr.length - 1);
    return arr;
}

利用分治法来处理快排，主要的思想是：

在数据集之中，选择一个元素作为”基准”（pivot）。

所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是数组最终排序后它的位置。

对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

步骤：

首先，把基准元素移到結尾（如果直接选择最后一个元素为基准元素，那就不用移动）；
然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1，表示下一个小于基准元素将要移动到的位置；
循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置；所以最后将基准元素所在位置（这里是 right）与 storeIndex 所代表的的位置的元素交换位置。
完成一次分区；

tips：这里为什么要把基准元素放到数组的最后一个元素的位置上，是为了方便对数组中除了基准元素以外的所有元素进行遍历，并方便在找到基准元素的排序位置 storeIndex 后进行两两交换。倘若不如此，需要将该基准元素从原数组中取出来（类似阮一峰版做法arr.splice(pivotIndex, 1)）,循环遍历完所有除基准元素外的元素后，找到基准元素的最后排序位置 storeIndex后，需要将基准元素插入进来（用到插入排序的思想），显然这种方式较为复杂。

所以一般选取了除数组最后一个元素为基准元素后，会将该基准元素换到最后一个元素上；这里便直接选取数组中最后一个元素为基准元素，对整个数组进行分区操作[0~arr.length-1].当然也可以只对数组中某一连续数组元素进行分区，即只对数组中这一小部分元素进行排序sort(arr, start, end);。

function quickSort(arr, start, end) {
    function swap(arr, i, k) {
        let temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    // 数组分区，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接选最右边的元素为基准元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
            } 
        }
        swap(arr, storeIndex, right); // 将基准元素放置到最后的正确位置上
        return storeIndex;
    }
    function sort(arr, left, right) {
        if(left > right) {
            return;
        }
        let storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
    sort(arr, start, end);
    return arr;
}
quickSort([3,7,8,5,2,1,9,5,4], 3, 7) // 只对部分元素排序

References

JS实现快速排序算法的详细解释
常见排序算法 - 快速排序 (Quick Sort)
算法的时间复杂度和空间复杂度-总结

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法 js快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97233.html

JavaScript专题之解读 v8 排序源码

摘要：插入排序是稳定的算法。所以准确的说，当数组长度大于的时候，采用了快速排序和插入排序的混合排序方法。在对数组进行了一次快速排序后，然后对两个子集分别进行了插入排序，最终修改数组为正确排序后的数组。 JavaScript 专题系列第二十篇，也是最后一篇，解读 v8 排序源码前言 v8 是 Chrome 的 JavaScript 引擎，其中关于数组的排序完全采用了 JavaScript 实...

princekin 2019-08-21 17:07 评论0 收藏0
Java排序算法之——快速排序

摘要：代码片段语言组织能力有限，直接上代码排序算法之快速排序参数为需要排序的数组参数为数组的起始下角标即参数为数组的最后下角标即经过一轮排序，已经将数组分为左右两部分进行递归排序总结快速排序的精髓在于分治思想，分而治之，它的时间复杂度为。算法简述所谓快速排序算法是基于交换排序和递归思想的，它的速度的确如名字所示——快！并且这种一算一般被用作数量级比较大的数据当中，在大数据中有着很重要的地...

Yangyang 2019-08-14 12:19 评论0 收藏0
Deep in JS - 收藏集 - 掘金

摘要：今天同学去面试，做了两道面试题全部做错了，发过来给道典型的面试题前端掘金在界中，开发人员的需求量一直居高不下。排序算法 -- JavaScript 标准参考教程（alpha） - 前端 - 掘金来自《JavaScript 标准参考教程（alpha）》，by 阮一峰目录冒泡排序简介算法实现选择排序简介算法实现 ... 图例详解那道 setTimeout 与循环闭包的经典面...

enali 2019-08-20 16:36 评论0 收藏0
PHP算法之四大基础算法

摘要：而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言虽然工作中，你觉得自己并没有涉及到算法这方面的东西，但是算法是程序的...

isLishude 2019-07-01 12:31 评论0 收藏0
算法学习之路，排序之快速排序（Java实现）

摘要：接下来我来说明快速排序的思路以及实现的代码。快速排序思路首先是定义一个变量，把数组的第一个元素的值赋给，然后定义两个变量指向数组的第一个元素和最后一个元素。今天突然想写个排序，以前写过，然后写了之后一直出错，然后自己百度了一下，看了别人写的方法，自己也尝试着写了一个。接下来我来说明快速排序的思路以及实现的代码。快速排序思路：首先是定义一个变量key，把数组的第一个元素的值赋给key...

charles_paul 2019-08-14 15:38 评论0 收藏0