JavaScript实现快速排序的方法分析

本文实例讲述了JavaScript实现快速排序的方法。分享给大家供大家参考，具体如下：

思想：

通过分治思想、递归方法将数据依次分解为包含较小元素和较大元素的不同子序列

1.在数组中选择一个元素为基准

2.对数组进行遍历，小于基准的元素都移到基准的左边，大于基准的元素都移到基准的右边

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

实现代码：

function sqort(arr){
 if(arr.length===0){
 return [];
}
var left=[];
var right=[];
var pivot=arr[0];//(基准以首元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,qsort(right));//递归
}
var a=[];
for (i=0;i<10;++i){
a[i]=Math.floor(Math.random()*100+1);
}
console.log(a);
console.log(sqort(a));
//(基准以中间元素的情况)
function sqort(arr){
 if(arr.length<=1){
 return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//(基准以中间元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,sqort(right));//递归
}
var a=[12,34,23,78,34,26];
console.log(a);
console.log(sqort(a));

注:  对于较小数组和较大数组分别递归调用sqort()函数，当递归结束时候，再将较小的数组与基准以及较大的数组连接起来形成最终的有序数组并返回。

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • 几种经典排序算法的JS实现方法

    一.冒泡排序 function BubbleSort(array) { var length = array.length; for (var i = length - 1; i > 0; i--) { //用于缩小范围 for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 if (array[j] > array[j+1]) { var temp = array[j]; array[j] = array[j+1]; arra

  • js快速排序的实现代码

    但是有不少的书本讲得并不是很清楚,而且不同的教材的实现方式也不尽相同,我这里将最简单的快速排序的思路写出来供大家参考. 希望不管是使用什么语言都能从这个简单的代码里很方便的掌握快排思路与编写方式 复制代码 代码如下: function quick_sort(list, start, end) {        if (start < end) {          var pivotpos = partition(list, start, end);   //找出快排的基数          q

  • javascript与Python快速排序实例对比

    本文实例对比了javascript与Python快速排序实现方法.分享给大家供大家参考.具体如下: js实现方法: function quicksort(arr) { if (arr.length <= 1) return arr return quicksort(arr.filter(function (lt, i) {return i > 0 && lt < arr[0]})) .concat([arr[0]]) .concat(quicksort(arr.filte

  • js交换排序 冒泡排序算法（Javascript版）

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. function sort(elements){ for(var i=0;i<elements.length-1;i++){ for(var j=0;j<elements.length-i-1;j++){ if(elemen

  • JavaScript希尔排序、快速排序、归并排序算法

    以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

  • js sort 二维数组排序的用法小结

    最近在搞js 排序的问题,因为数据库排序太耗资源,如果能转移到客户端去排序,能大大D减少服务器内存消耗.客户端的话,除了js,就是as了,可惜我as学得太烂,所以只能选择js来研究研究了...经过我的测试,js内置方法sort的效率非常高 我们知道在js中默认提供了sort函数,但是这个函数默认是按照数组内容的ascii码升序进行排列的,如果我们要对二维数组排序要如何做呢?在php中是有multi_sort函数可供调用的,但是在js中似乎没有这种函数,但是没关系 ,因为js的sort函数其实也提

  • js中数组排序sort方法的原理分析

    本文实例分析了js中数组排序sort方法的原理.分享给大家供大家参考.具体分析如下: 最近在百度的项目中要用到对数组进行排序,当然一开始自然想到了数组的sort方法,这方法应用非常简单,大致如下: 复制代码 代码如下: window.onload=function(){         var arr=[2,55,55,1,75,3,9,35,70,166,432,678,32,98];         var arr2=["George","John","

  • JS实现冒泡排序，插入排序和快速排序并排序输出

    JS实现冒泡排序，插入排序和快速排序并排序输出

    在一次面试中被问到了此问题,但是真是懵了,没能回答上来,后来通过JS整理了一下,在结合html代码做了一个文本框,把输入的内容从文本框排序输出,再次不做叙述了,下面通过一段代码给大家展示下: 以下是代码: index.html <!DOCTYPE html> <html> <head> <title>Sorting</title> <link rel="stylesheet" type="text/css&qu

  • JavaScript实现拼音排序的方法

    一般情况下,大家会使用下面的方法来进行汉字的拼音排序 复制代码 代码如下: var list = [ '王', '张','李']; list.sort(function (a, b) { return a.localeCompare(b); }); localeCompare() :用本地特定的顺序来比较两个字符串. 通过localeCompare这个方法来进行拼音排序的不可靠之处在于: 1. 很依赖中文操作系统 2. 很依赖浏览器的内核 也就是说,如果你的网站访问者是通过非中文系统,或者非IE

  • JavaScript实现快速排序的方法分析

    本文实例讲述了JavaScript实现快速排序的方法.分享给大家供大家参考,具体如下: 思想: 通过分治思想.递归方法将数据依次分解为包含较小元素和较大元素的不同子序列 1.在数组中选择一个元素为基准 2.对数组进行遍历,小于基准的元素都移到基准的左边,大于基准的元素都移到基准的右边 3.对基准左边和右边的两个子集,不断重复前两步,直到所有子集只剩下一个元素为止 实现代码: function sqort(arr){ if(arr.length===0){ return []; } var lef

  • JavaScript实现快速排序的方法

    本文实例讲述了JavaScript实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: <html> <head> <script> function quickSort(input) { if (input.length <= 1) return input; var pivot = Math.floor(Math.random()*input.length) var less = [], greater=[]; var pivotElem = inpu

  • JavaScript实现多重继承的方法分析

    本文实例讲述了JavaScript实现多重继承的方法.分享给大家供大家参考,具体如下: 1. 定义一个空的父类构造函数,然后通过prototype的方式为该父类定义属性和方法 2. 定义一个空的子类的构造函数,然后将子类的原型绑定在父类的实例上,再将子类原型的父类也绑定在父类的实例上.通过prototype的方式为子类设置自己的属性和方法. 3. 定义一个空的孙类构造函数,然后将孙类的原型绑定到子类的实例上,再将孙类原型的父类绑定到子类的实例上.通过prototype方式为孙类定义自己的属性和方

  • JavaScript重复元素处理方法分析【统计个数、计算、去重复等】

    本文实例讲述了JavaScript重复元素处理方法.分享给大家供大家参考,具体如下: 判断一个字符串中出现次数最多的字符,统计这个次数 //将字符串的字符保存在一个hash table中,key是字符,value是这个字符出现的次数 var str = "abcdefgaddda"; var obj = {}; for (var i = 0, l = str.length; i < l; i++) { var key = str[i]; if (!obj[key]) { obj[

  • JavaScript实现重力下落与弹性效果的方法分析

    JavaScript实现重力下落与弹性效果的方法分析

    本文实例讲述了JavaScript实现重力下落与弹性效果的方法.分享给大家供大家参考,具体如下: 这里利用JS语言在Html页面中实现重力作用下落地后弹起的效果,如下所示: 在此例中主要涉及以下几个问题: 1.给球体一个释放初速度,如何实现越向下运动且在接触边缘之前,竖直方向上的速度speedY越大的效果? 答案:可以在计时器中,每及时一次,竖直方向上的速度speedY自增一个固定值来实现,下面代码中speedY += 6;就是实现这个效果. 2.球体接触地面(此例中指浏览器下边缘)后,如何实现

  • JavaScript中将一个值转换为字符串的方法分析[译]

    译者注:前两天在看ES5的时候顺便出了一道题,今天看到这篇文章,刚好解释的很清楚,就翻译了一下.在JavaScript中,主要有三种方法能让任意值转换为字符串.本文讲解了每种方法以及各自的优缺点. 1.转换字符串的三种方法 这三种将value转换为字符串的方法是: 1.value.toString() 2."" + value 3.String(value) 第一种方法存在的问题是,它不能把null和undefined转换为字符串.还有第二种和第三种方法,这两种方法的效果基本一样. •

  • Javascript数组中push方法用法分析

    本文实例讲述了Javascript数组中push方法用法.分享给大家供大家参考,具体如下: 看下面代码: var o = { 1:'a' ,2:'b' ,length:2 ,push:Array.prototype.push }; o.push('c'); Q:o现在内部的值是什么样子? 我的第一反应是排斥,为什么要研究不合理情况下[解释引擎]的行为?但是这种推论有时候又很吸引人,于是我回来的时候仔细思考了下,发现其实很简单. 对于push这个方法,我条件反射地想到的就是栈,[数据结构的经典栈]

  • javascript数组遍历的方法实例分析

    javascript数组遍历的方法实例分析

    本文实例讲述了javascript数组遍历的方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="UTF-8"> <title></title> </head> <body> <script> var a = [1,2,3,4,5,6]; var b = a.

  • JavaScript变量基本使用方法实例分析

    本文实例讲述了JavaScript变量基本使用方法.分享给大家供大家参考,具体如下: JavaScript 是一种弱类型语言,javascript的变量类型由它的值来决定. 定义变量需要用关键字 'var' var iNum = 123; var sTr = 'asd'; //同时定义多个变量可以用","隔开,公用一个'var'关键字 var iNum = 45,sTr='qwe',sCount='68'; 变量类型 5种基本数据类型: 1.number 数字类型 2.string 字

  • JavaScript类的继承方法小结【组合继承分析】

    本文实例讲述了JavaScript类的继承方法.分享给大家供大家参考,具体如下: 在JavaScript 里,被继承的函数称为超类型(父类,基类也行,其他语言叫法),继承的函数称为子类型(子类,派生类).继承也有之前问题,比如字面量重写原型会中断关系,使用引用类型的原型,并且子类型还无法给超类型传递参数. 为了解决引用共享和超类型无法传参的问题,我们采用一种叫借用构造函数的技术,或者成为对象冒充(伪造对象.经典继承)的技术来解决这两种问题. function aObj(){ this.name

随机推荐