资讯专栏INFORMATION COLUMN

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

LeexMuller / 1251人阅读

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

由于自己不是计算机专业,数据结构没有太多研究,曾经面试时有被问过关于快速排序以及冒泡排序的写法,冒泡排序比较简单,当时能回答出来,但是快速排序当时就比较懵逼,不知道是个什么方式实现的,面试回来后也没太在意,最近在看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))
}

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

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

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

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

相关文章

  • 算法之旅 | 快速排序

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

    AlanKeene 评论0 收藏0
  • 前端优化 - 收藏集 - 掘金

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

    VincentFF 评论0 收藏0
  • JavasScript重难点知识

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

    forsigner 评论0 收藏0
  • JavaScript专题之解读 v8 排序源码

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

    princekin 评论0 收藏0

发表评论

0条评论

LeexMuller

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<