切换导航
京西&周倍庆&程序猿
首页
前端
JavaScript
jQuery
AngularJS
Bootstrap
后端
Nginx
MySQL
PHP
系统
Mac
Centos
杂谈
工作
娱乐
爱情
梦想
JS算法之快速排序法
浏览量:
28
发布时间:
2016-01-18
发布人:
京西
文章由
京西
原创,转载时请在文章底部添加如下内容
本文转载自京西的个人博客,原文链接为
http://www.siguoya.name/home/article/48
相关推荐
JavaScript现在和将来都将是编程
创造 JavaScript 仅用 10
###"快速排序"的思想: >(1)在数据集之中,选择一个元素作为"基准"(pivot)。 (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。 (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。 ###问题: 给定一个数据集{85, 24, 63, 45, 17, 31, 96, 50},通过快速排序算法实现对数组从小到大的排序 ```javascript function quickSort(arr){ //获取数组长度,如果数组元素为1,直接返回; var length=arr.length; if(arr.length<=1){ return arr; } var midIndex=parseInt((arr.length)/2); //不能将arr.splice(midIndex,1)[0]写成是arr[midIndex]; //向splice函数传递两个参数具有删除的作用,会不断减少数组元素的个数 //arr[midIndex]会导致算法陷入死循环 var midValue=arr.splice(midIndex, 1)[0]; var leftArray=[]; var rightArray=[]; for(var i=0;i<arr.length;i++){ if(arr[i]<midValue){ leftArray.push(arr[i]); }else{ rightArray.push(arr[i]); } } //concat的时候加上midValue也是将上述注释中删除的进行补上 return quickSort(leftArray).concat(midValue,quickSort(rightArray)); } var arr=[85, 24, 63, 45, 17, 31, 96, 50]; console.log(quickSort(arr));//[17, 24, 31, 45, 50, 63, 85, 96] ```