排序的方法有很多种,但是使用最为广泛的是快速排序,下面就通过代码示例详细介绍一下它的实现过程。
先给出代码实例,然后对其的原理和实现过程进行详细介绍。
代码实例如下:
[JavaScript] 纯文本查看 复制代码运行代码var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1); var left = []; var right = []; for (var index = 0; index < arr.length; index++){ if (arr[index] < pivot) { left.push(arr[index]); } else { right.push(arr[index]); } } return quickSort(left).concat(pivot, quickSort(right)); }; var arr = [85,24,63,45,17,31,96,50]; console.log(arr.join(",")); console.log(quickSort(arr).join(","));
上面的代码就是一个快速排序的代码实例,下面介绍一下它的实现原理和实现过程。
一.实现原理:
整个原理非常的简单,过程大体划分如下:
(1)在数据集之中,选择一个元素作为"基准"(pivot)。
(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
(3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
下面是简单的图示:
第一步,选择中间的元素45作为"基准":
基准值可以任意选择,但是选择中间的值比较容易理解。
第二步,按照顺序,将每个元素与"基准"进行比较:
形成两个子集,一个"小于45",另一个"大于等于45"。
第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止:
二.代码注释:
(1).var quickSort = function(arr) {},此函数实现了快速排序功能,参数是要进行排序的数组。
(2).if (arr.length <= 1) {
return arr;
},如果数组的长度小于等于1,也就是说只有一个元素或者没有元素,那么就直接返回该数组。
(3).var pivotIndex = Math.floor(arr.length / 2),选取基准元素,这里我们选取尽可能居中的元素,当然任何元素都可以。
(4).var pivot = arr.splice(pivotIndex, 1),获取这个基准元素值。
(5).var left = [],此数组用来存储小于基准元素的数组元素。
(6).var right = [],此数组用来存储大于基准元素的数组元素。
(7).for (var index = 0; index < arr.length; index++){
if (arr[index] < pivot) {
left.push(arr[index]);
}
else {
right.push(arr[index]);
}
},通过遍历操作进行元素的比较,将小于基准的元素存入left数组,大于基准的元素存入right数组。
(8).return quickSort(left).concat(pivot, quickSort(right),这个是一个递归操作,一层一层的执行下去,最终能够实现排序功能。
三.相关阅读:
(1).Math.floor()参阅JavaScript Math.floor()一章节。
(2).splice()方法参阅JavaScript Array splice()一章节。
(3).push()方法参阅JavaScript push()一章节。
(4).concat()方法参阅JavaScript Array concat()一章节。
|手机版|小黑屋|
( 鲁ICP备10022556号-3 )
鲁ICP备10022556号-3
Copyright © 2012-2018 Design: 蚂蚁部落
最新评论