摘要:所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把改记录排在这两部分的中间称为该记录归位,这个过程称作一次快速排序。代码如下大佬的代码还是比较厉害的,简单易懂,佩服以上就是相关的快速排序的实现方法
由于自己不是计算机专业,数据结构没有太多研究,曾经面试时有被问过关于快速排序以及冒泡排序的写法,冒泡排序比较简单,当时能回答出来,但是快速排序当时就比较懵逼,不知道是个什么方式实现的,面试回来后也没太在意,最近在看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...
摘要:虽然有着各种各样的不同,但是相同的是,他们前端优化不完全指南前端掘金篇幅可能有点长,我想先聊一聊阅读的方式,我希望你阅读的时候,能够把我当作你的竞争对手,你的梦想是超越我。 如何提升页面渲染效率 - 前端 - 掘金Web页面的性能 我们每天都会浏览很多的Web页面,使用很多基于Web的应用。这些站点看起来既不一样,用途也都各有不同,有在线视频,Social Media,新闻,邮件客户端...
摘要:忍者级别的函数操作对于什么是匿名函数,这里就不做过多介绍了。我们需要知道的是,对于而言,匿名函数是一个很重要且具有逻辑性的特性。通常,匿名函数的使用情况是创建一个供以后使用的函数。 JS 中的递归 递归, 递归基础, 斐波那契数列, 使用递归方式深拷贝, 自定义事件添加 这一次,彻底弄懂 JavaScript 执行机制 本文的目的就是要保证你彻底弄懂javascript的执行机制,如果...
摘要:插入排序是稳定的算法。所以准确的说,当数组长度大于的时候,采用了快速排序和插入排序的混合排序方法。在对数组进行了一次快速排序后,然后对两个子集分别进行了插入排序,最终修改数组为正确排序后的数组。 JavaScript 专题系列第二十篇,也是最后一篇,解读 v8 排序源码 前言 v8 是 Chrome 的 JavaScript 引擎,其中关于数组的排序完全采用了 JavaScript 实...
阅读 3192·2023-04-26 01:31
阅读 1821·2023-04-25 22:08
阅读 3279·2021-09-01 11:42
阅读 2783·2019-08-30 12:58
阅读 2125·2019-08-29 18:31
阅读 2384·2019-08-29 17:18
阅读 3036·2019-08-29 13:01
阅读 2488·2019-08-28 18:22