快速排序(QuickSort)

快速排序是效率较快,也是最常用的排序算法,其原理也非常的简单

(1)先在数组中找到一个比较值,一般采用中间值.
(2)此时,先定义一个一左一右的数组,遍历比较时如果比中间值小,就添加到左数组,比中间值大则添加到右数组.
(3)遍历数组,与中间值比较
(4)然后,再对左右两边的数组重复以上操作
(5)一直到不断被细分的数组的长度≤1的时候就返回数组

---

1.定义方法

function QuickSort(arr){

}

2.找到中间值,并且取出来,要做比较

function QuickSort(arr){
  var pivotIndex=Math.floor(arr.length/2);
  var pivot=arr.splice(pivotIndex,1)[0];//splice返回的是数组,用[0]返回值
}

3.再定义一左一右的数组,开始遍历

function QuickSort(arr){
  var pivotIndex=Math.floor(arr.length/2);
  var pivot=arr.splice(pivotIndex,1)[0];
  var left=[],right=[];
  for(var i=0;i<arr.length;i++){

  }
}

4.如果比中间值小,就添加到左数组,比中间值大则添加到右数组.

function QuickSort(arr){
  var pivotIndex=Math.floor(arr.length/2);
  var pivot=arr.splice(pivotIndex,1)[0];
  var left=[],right=[];
  for(var i=0;i<arr.length;i++){

    if(arr[i]<pivot){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }

  }
}

5.使用递归,再对左右两边的数组重复以上操作

function QuickSort(arr){
  var pivotIndex=Math.floor(arr.length/2);
  var pivot=arr.splice(pivotIndex,1)[0];
  var left=[],right=[];
  for(var i=0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return QuickSort(left).concat([pivot],QuickSort(right));
}

6.直到数组长度≤1的时候返回数组!注意!要在函数一开始就写上!

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=[],right=[];
  for(var i=0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return QuickSort(left).concat([pivot],QuickSort(right));
}

完工!