快速排序的JS实现

From：阮一峰 快速排序（Quicksort）的Javascript实现

排序算法（Sorting algorithm）是计算机科学最古老、最基本的课题之一。要想成为合格的程序员，就必须理解和掌握各种排序算法。

目前，最常见的排序算法大概有七八种，其中"快速排序"（Quicksort）使用得最广泛，速度也较快。它是图灵奖得主C. A. R. Hoare（1934--）于1960时提出来的。

"快速排序"的思想很简单，整个排序过程只需要三步：

1. 在数据集中，选择一个元素作为基准
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

用JavaScript实现上边的步骤

1. 首先定义一个 quickSort函数，他的参数是一个数组

function quickSort(arr){
  ...
}

2. 检查数组元素的个数，如果小于等于1，就返回

function quickSort(arr){
  if(arr.length<=1){ return arr}
}

3. 接着选择基准,并将其与原数组分离，再定义两个空数组，用来存放一左一右两个子集

function quickSort(arr){
  if(arr.length<=1){ return arr}
  var pivotIndex = Math.floor(arr.length / 2) ;  //基准的下标
  var pivot = arr.splice(pivotIndex, 1)[0];  // 把基准从数组分离出来
  var left = [];  // 基准左边子集存放变量
  var right = []; // 基准右边子集存放变量
}

4. 然后开始遍历数组，比基准大的存入right,比基准小的存入left

function quickSort(arr){
  if(arr.length<=1){ return arr}
  var pivotIndex = Math.floor(arr.length / 2) ;  //基准的下标
  var pivot = arr.splice(pivotIndex, 1)[0];  // 把基准从数组分离出来
  var left = [];  // 基准左边子集存放变量
  var right = []; // 基准右边子集存放变量
  for(var i=0;i<arr.length;i++){
    if(arr[i]<= pointNum){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
}

5. 最后使用递归，不断重复这个过程，就可以得到排序后的数组

function quickSort(arr){
  if(arr.length<=1){ return arr}
  var pivotIndex = Math.floor(arr.length / 2) ;  //基准的下标
  var pivot = arr.splice(pivotIndex, 1)[0];  // 把基准从数组分离出来
  var left = [];  // 基准左边子集存放变量
  var right = []; // 基准右边子集存放变量
  for(var i=0;i<arr.length;i++){
    if(arr[i]<= pointNum){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pointNum],quickSort(right))
}

使用的时候，直接调用quickSort 就行了

var arr1 = [1,5,23,60,80,123,342,0,3,45,60,100,1000,21];
var arr2 = quickSort(arr1);
console.log(arr2 )   //[0, 1, 3, 5, 21, 23, 45, 60, 60, 80, 100, 123, 342, 1000]