快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。该算法可采用原地分区和非原地分区的方式实现。

算法步骤

1. 从数列中挑出一个元素，称为 "基准"（pivot），一般为第一个元素；

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动图演示

非原地分区

/**
 * 伪代码
 * function quicksort(q)
 * {
 *     var list less, pivotList, greater
 *     if length(q) ≤ 1
 *         return q
 *     else
 *     {
 *         select a pivot value pivot from q
 *         for each x in q except the pivot element
 *         {
 *             if x < pivot then add x to less
 *             if x ≥ pivot then add x to greater
 *         }
 *         add pivot to pivotList
 *         return concatenate(quicksort(less), pivotList, quicksort(greater))
 *     }
 * }
 */

function quickSort(arr) {
  if (arr.length < 2) {
    return arr
  }
  let left = []
  let right = []
  let pivot = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
}

let arr = [6, 3, 5, 2, 4, 1]

arr = quickSort(arr)

console.log(arr)

原地分区

// 原地分区，减少内存占用
function quickSort(arr) {
  partition(arr, 0, arr.length - 1)
  return arr
}

function partition(arr, lIndex, rIndex) {
  if (lIndex < rIndex) {
    // 分区操作
    const pivot = lIndex // 设定基准值（pivot）
    const pivotValue = arr[pivot]
    let index = pivot + 1
    for (let i = index; i <= rIndex; i++) {
      // 小于 pivotValue 的全部放到前面的小于pivotValue的分区，这里注意要与20，21行一起看
      if (pivotValue > arr[i]) {
        swap(arr, i, index)
        index++
      }
    }
    // 把 pivotValue 放到分区中间
    const partitionIndex = index - 1
    swap(arr, pivot, partitionIndex)
    // 此时，数组arr被分为了小于pivotValue，pivotValue，大于pivotValue的三个区域
    console.log('current arr', arr)
    partition(arr, lIndex, partitionIndex - 1)
    partition(arr, partitionIndex + 1, rIndex)
  }
  return arr
}

function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

let arr = [3, 4, 2, 6, 5, 1]
console.log(arr)
arr = quickSort(arr)

console.log(arr)