网站地图    收藏   

主页 > 前端 > javascript >

js算法之快速排序

来源:未知    时间:2018-01-11 16:38 作者:小飞侠 阅读:

[导读] 今天带来js算法之快速排序 js快速排序思想: js快速排序 通过分治思想、递归方法将数据依次分解为包含较小元素和较大元素的不同子序列 1.在数组中选择一个元素为基准 2.对数组进行...

今天带来js算法之快速排序


js快速排序思想:

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

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

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

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


js快速排序实现代码:

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));

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

以上是自学php网提供 js快速排序 相关方法代码以及介绍。


自学PHP网专注网站建设学习,PHP程序学习,平面设计学习,以及操作系统学习

京ICP备14009008号-1@版权所有www.zixuephp.com

网站声明:本站所有视频,教程都由网友上传,站长收集和分享给大家学习使用,如由牵扯版权问题请联系站长邮箱904561283@qq.com

添加评论