切换导航
京西&周倍庆&程序猿
首页
前端
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] ```
