快速排序又叫快排，和冒泡排序类似，都是通过元素的比较和交换位置来排序，本文记录一下快排的实现方法，希望对大家有所帮助

一、 基本思想

快排采用分治的思想，每个循环将数列依据选定的基准，分成大小两份。主要实现思路 选择基准元素，还有元素的交换。
这里有动画示例很好理解。

二、 代码实现

a、双边循环

/**
    * @method    快排
    * @param     {参数类型} 参数名 参数说明
    * @return    {返回值类型} 返回值说明
    */
    let arrgo = [4,4,6,5,3,2,8,1];
    function quickSort(arr, startIndex, endIndex) {
        if (startIndex>=endIndex) {
            return;
        }

        let pivotIndex = partition(arr, startIndex, endIndex);

        quickSort(arr, startIndex, pivotIndex-1)
        quickSort(arr, pivotIndex+1, endIndex)

    }
    /**
    * @method   分组
    * @param     {参数类型} 参数名 参数说明
    * @return    {返回值类型} 返回值说明
    */
    function partition(arr, startIndex, endIndex){
        let pivot = arr[startIndex];
        let left = startIndex;
        let right = endIndex;
        while(left != right) {
            while(left<right && arr[left] <= pivot){
                left++
            }
            while(left<right && arr[right] > pivot){
                right--
            }
            if (left < right) {
                let temp = arr[right];
                arr[right] = arr[left];
                arr[left]= temp;
            }

        }
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }
    quickSort(arrgo, 0, 4)
    console.log(arrgo);

b、单边循环

下面这种实现，以第一个元素为基准遍历比对，比基准小就和前面大的元素互换位置，最后最后一个交换的元素和基准交换位置，这样左边就是都比基准小的元素，右边都是比基准大的元素

function quickSort2(arr, start, end) {
  while(start >= end) return
  let pivot = start,
  pivotVal = arr[pivot],
  idx = pivot + 1
  while (idx <= end) {
    if (arr[idx] < pivotVal) {
      pivot ++
      if (arr[pivot] != arr[idx]) {
        [arr[pivot], arr[idx]] = [arr[idx], arr[pivot]]
      }
    }
    idx ++
  }
  [arr[pivot], arr[start]] = [arr[start], arr[pivot]]
  quickSort2(arr, pivot + 1, end)
  quickSort2(arr, 0, pivot - 1)
}

c、上面的方法排序结果对原数组有影响，下面的排序会从新生成一个数组对原数组没影响。

   * @method    快排
    * @param     {参数类型} 参数名 参数说明
    * @return    {返回值类型} 返回值说明
    */
    let arrgo = [4,4,6,5,3,2,8,1];
    function quicksort(array) {
  var tmp_array = array.slice(0), result,
  quickSort = function(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] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
  };
  result = quickSort(tmp_array);
  return result;
}

let resultArr = quicksort(arrgo);
console.log(arrgo);
console.log(resultArr);

三、优化方式

对于基准的选择有一种优化方式，为三数取中，这样可以更利于数组均等的拆分，可以避免已经有序的数据，减少执行次数。代码实现如下

function getmid(arr, left, right) {
     if (arr.length < 3) return arr[0];
     let mid = Math.floor(left + (right-left)/2);
     // let temp =[arr[left]];
     if (arr[left] > arr[mid]) {
       // arr.push(arr[mid])
       if (arr[left] > arr[right]) {
         if (arr[mid] > arr[right]){
           return mid;
         } else {
           return right;
         }
       } else {
         return left
       }

     } else {
       if (arr[left] > arr[right]) {
         return left

       } else {
         if (arr[mid] > arr[right]){
           return right;
         } else {
           return mid;
         }
       }
     }
   }

四、总结

对比冒泡排序一轮只能挑选一个元素冒泡到数列的一端，快排使用递归的方式，每轮挑选一个基准元素，然后遍历数列比基准小的放左边，大的放右边，时间复杂度为 O(nlogn)，如果数列已经有序，最差的时间复杂度为 O(n^2)