JavaScript中的快速排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript中的快速排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2903字,纯文字阅读大概需要5分钟。
内容图文
![JavaScript中的快速排序](/upload/InfoBanner/zyjiaocheng/636/3d9db2d5b8cf4baf8b4d0d385f328602.jpg)
1.快速排序有多重要?
快速排序几乎可以说是目前所有排序算法中,最快的一种排序算法。(当然,没有任何一种算法在任意情况下都是最优的。比如:希尔排序确实在某些情况下可能好于快速排序,但大多数情况下,快速排序还是比较好的选择~)
2.快速排序的思想:
先来回忆一下冒泡排序的思路:对于未排序的各元素依次比较相邻两个元素大小关系;
如果左边的数大,则两元素交换位置,向右移动一个位置,比较下面两个元素;
当走到最右端时,最大的元素一定被放在了最右边。
按照这个思路,从最左端重新开始,第二轮走到倒数第二个位置即可.............
快速排序就是冒泡排序的升级版,快速排序可以在一次循环中(其实是递归调用),找出某个元素的正确位置,并且该元素之后不需要任何移动。
快速排序最重要的思想:分而治之。
可以看到,以上是递归的处理左边的数据和右边的数据。那么问题来了?我该如何选择一个数字来进行划分呢?为什么选择65、31、81呢?接下来学习如何选择一个:枢纽。
3.快排的实现思路(我直接写在纸上了,字不好看,但知识很有意思~)
可以看到枢纽起着至关重要的作用~~,接下来看看如何选择枢纽(尽量选择靠中间的)
这里我的做法是:选择头、中、尾三个数,然后比较大小,选择一个中位数
对应到上个例题中就是:left:0, right:length-1; center:(left+right)/2
left:[0] right:[8] center:[4]
left:23 right:72 center:76
中位数为:72,所以就将72定位枢纽(可能这里这个数据不太好,但原理就是这么个原理~)
接下来就将这三个数字排序之后放在对应的位置,将比枢纽小的放在第一个,比枢纽大的放在最后一个,将枢纽放在倒数第二位
4.代码实现:
// 快速排序代码 // 1.选择枢纽 ArrayList.prototype.median = function (left, right) { // 取出中间的位置 var center = Math.floor((left + right) / 2) // 对三个数据进行判断大小,并排序 if (this.array[left] > this.array[center]) { // 如果左边的数大于中间的数,则两者交换 this.swap(left, center) } if (this.array[center] > this.array[right]) { // 如果中间的数大于右边的数,则两者交换 this.swap(center, right) } if (this.array[left] > this.array[right]) { // 如果中间的数大于右边的数,则两者交换 this.swap(left, right) } // 将枢纽与倒数第二个位置上的数交换 this.swap(center, right - 1) // 返回枢纽 return this.array[right - 1] } ArrayList.prototype.quickSort = function(){ this.quick(0,this.array.length-1) } //递归函数 ArrayList.prototype.quick = function(left,right){ // 结束条件:当传入的left比right大时(左边的数比右边的数大时)递归结束 if(left >= right) return // 获取枢纽 var pivot = this.median(left,right) // 左指针,变量,用于记录当前找到的位置 var i = left // 右指针 var j = right - 1 // 开始进行交换 while(true){ // 左指针向右移,碰到比枢纽大的就停住(直接从++i开始,是因为left是比枢纽小的,不用再次比较) while(this.array[++i] < pivot ) {} // 右指针向左移,碰到比枢纽小的就停住 while(this.array[--j] > pivot ) {} if(i<j){ // 如果i<j,则i与j交换(比如例题中的第三步) this.swap(i,j) }else{ // 当i>j的时候,退出循环 break } } // i和枢纽交换,此时枢纽已经找到正确位置,枢纽左边的都是小于它的,枢纽右边的都是大于它的 // (可以参考例题中的步骤4) this.swap(i,right-1) // 分而治之,枢纽左边的 this.quick(left,i-1) // 分而治之,枢纽右边的 this.quick(i+1,right) }
内容总结
以上是互联网集市为您收集整理的JavaScript中的快速排序全部内容,希望文章能够帮你解决JavaScript中的快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。