JavaScript快速排序功能详解

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

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

代码实例如下:

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