关于JS的快速排序实现方法

LeexMuller 发布于2019-08-21 17:40 / 1356人阅读

摘要：所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把改记录排在这两部分的中间称为该记录归位，这个过程称作一次快速排序。代码如下大佬的代码还是比较厉害的，简单易懂，佩服以上就是相关的快速排序的实现方法

由于自己不是计算机专业，数据结构没有太多研究，曾经面试时有被问过关于快速排序以及冒泡排序的写法，冒泡排序比较简单，当时能回答出来，但是快速排序当时就比较懵逼，不知道是个什么方式实现的，面试回来后也没太在意，最近在看C语言的数据结构，拓展下这方面的知识，其中就看到了关于快排算法的描述

描述如下：在待排序的n个记录中任取一个记录（通常取第一个记录），数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把改记录排在这两部分的中间（称为该记录归位），这个过程称作一次快速排序。之后对所有的两部分分别重复上述过程，直至每部分内只有一个记录或空为止。

光看概念有点晕，书上用的是C的源代码，改写下，变成JS代码：

function quickSort(arr, start, end){
        var i = start
        var j = end
        if (start < end ) {
            
            var temp = arr[start]
            while (i != j ) {
                while(arr[j] > temp && j > i){
                    j--
                }
                var com = arr[j]
                arr[j] = arr[i]
                arr[i] = com
                while(arr[i] < temp && i < j){
                    i++
                }
                var com1 = arr[j]
                arr[j] = arr[i]
                arr[i] = com1
            }
            arr[i] = temp
            quickSort(arr, start, i - 1)
            quickSort(arr, i + 1, end)
        }
    }

解释下：
假设一个无序数组：[6,8,7,9,0,1,3,2,4,5]
取第一个元素为参考元素，先从尾端开始即end向左遍历，元素下标为j, 发现比参考元素小的值，则与从左向右遍历的元素arr[i]进行交换，然后就从i开始向右遍历，找到一个比参考元素大的值，而后与arr[j]进行交换，最终i = j 时完成一次快速排序,然后对左边部分进行快排，对右边进行快排。

根据书上就是这样的了，自己也尝试了下，答案是没有问题的

然后看网上某位大佬的做法，更加简单易懂，将快排简单化，就是比参考元素小的放置左边部分，比参考元素大的放置右边部分，而后分别对两部分进行快排。

代码如下：

function quickSort(arr){
    if (arr.length <= 1) {
        return arr
    }

    var left = [], right=[]
    var pivotIndex = Math.floor(arr.length / 2)
    var pivot = arr.splice(pivotIndex, 1)[0]
    for (var 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))
}

大佬的代码还是比较厉害的，简单易懂，佩服

以上就是相关的快速排序的实现方法

云服务器 GPU云服务器 js快速排序快速排序法js js中数据排序方法 js实现table排序

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

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

算法之旅 | 快速排序法

摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。 HTML5学堂-码匠：前几期算法之旅跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的慢排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法—— 快速排序法 [ 平均时间复杂度为O (n l...

AlanKeene 2019-08-22 11:11 评论0 收藏0
前端优化 - 收藏集 - 掘金

摘要：虽然有着各种各样的不同，但是相同的是，他们前端优化不完全指南前端掘金篇幅可能有点长，我想先聊一聊阅读的方式，我希望你阅读的时候，能够把我当作你的竞争对手，你的梦想是超越我。如何提升页面渲染效率 - 前端 - 掘金Web页面的性能我们每天都会浏览很多的Web页面，使用很多基于Web的应用。这些站点看起来既不一样，用途也都各有不同，有在线视频，Social Media，新闻，邮件客户端...

VincentFF 2019-08-20 17:15 评论0 收藏0
JavasScript重难点知识

摘要：忍者级别的函数操作对于什么是匿名函数，这里就不做过多介绍了。我们需要知道的是，对于而言，匿名函数是一个很重要且具有逻辑性的特性。通常，匿名函数的使用情况是创建一个供以后使用的函数。 JS 中的递归递归, 递归基础, 斐波那契数列, 使用递归方式深拷贝, 自定义事件添加这一次，彻底弄懂 JavaScript 执行机制本文的目的就是要保证你彻底弄懂javascript的执行机制，如果...

forsigner 2019-08-21 18:36 评论0 收藏0
JavaScript专题之解读 v8 排序源码

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

princekin 2019-08-21 17:07 评论0 收藏0