JavaScript快速排序功能详解

2018-7-12 00:01| 作者: admin| 查看: 422| 评论: 0|来自: 蚂蚁部落

排序的方法有很多种,但是使用最为广泛的是快速排序,下面就通过代码示例详细介绍一下它的实现过程。

先给出代码实例,然后对其的原理和实现过程进行详细介绍。

代码实例如下:

[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作为"基准":

基准值可以任意选择,但是选择中间的值比较容易理解。

a:3:{s:3:\"pic\";s:43:\"portal/201712/04/144934izisz1q1qsg7gij1.jpg\";s:5:\"thumb\";s:0:\"\";s:6:\"remote\";N;}

第二步,按照顺序,将每个元素与"基准"进行比较:

形成两个子集,一个"小于45",另一个"大于等于45"。

a:3:{s:3:\"pic\";s:43:\"portal/201712/04/144959pt7trvbidbgvkvgb.jpg\";s:5:\"thumb\";s:0:\"\";s:6:\"remote\";N;}

第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止:

a:3:{s:3:\"pic\";s:43:\"portal/201712/04/145022yzkhn77mwne20eem.jpg\";s:5:\"thumb\";s:0:\"\";s:6:\"remote\";N;}

二.代码注释:

(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()一章节。


鲜花

握手

雷人

路过

鸡蛋

最新评论

返回顶部