介绍

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼・霍尔提出。在平均状况下，排序 n 个项目要 ${\displaystyle \ O(n\log n)}$（大 O 符号）次比较。在最坏状况下则需要 ${\displaystyle O(n^{2})}$ 次比较，但这种状况并不常见。事实上，快速排序 ${\displaystyle \Theta (n\log n)}$ 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

原理

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的 2 个子序列，然后递归地排序两个子序列。

步骤为：

• 挑选基准值：从数列中挑出一个元素，称为 “基准”（pivot），
• 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
• 递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

伪代码

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))
     }
 }

动画

实现

JavaScript

/**
 * @function QuickSort
 * @description Quick sort is a comparison sorting algorithm that uses a divide and conquer strategy.
 * @param {Integer[]} items - Array of integers
 * @return {Integer[]} - Sorted array.
 * @see [QuickSort](https://en.wikipedia.org/wiki/Quicksort)
 */
function quickSort (items) {
  const length = items.length

  if (length <= 1) return items
  const PIVOT = items[0]
  const GREATER = []
  const LESSER = []

  for (let i = 1; i < length; i++) {
    if (items[i] > PIVOT) GREATER.push(items[i])
    else LESSER.push(items[i])
  }

  return [...quickSort(LESSER), PIVOT, ...quickSort(GREATER)]
}

QuickSortRecursive

/*
    Quicksort is the most popular sorting algorithm and there have
    lots of different implementations but the "recursive" or "Partition in place"
    is one of the most efficient implementations below we have discussed how to
    implement it.
    Partition in place => "in place" Partition in place indicates that we
    do not need any other space to store the auxiliary array and the term
    "partition" denotes that we split the list into two parts one is less
    than the pivot and the other is greater than the pivot and repeats this
    process recursively and breaks the problem into sub-problems and makes
    it singular so that the behavior or "divide and conquer" get involved
    too.
    Problem & Source of Explanation => https://www.cs.auckland.ac.nz/software/AlgAnim/qsort1a.html
*/

/**
 * Partition in place QuickSort.
 * @param {number[]} inputList list of values.
 * @param {number} low lower index for partition.
 * @param {number} high higher index for partition.
 */
const quickSort = (inputList, low, high) => {
  if (!Array.isArray(inputList)) {
    throw new TypeError('Please input a valid list or array.')
  }
  if (low < high) {
    // get the partition index.
    const pIndex = partition(inputList, low, high)
    // recursively call the quickSort method again.
    quickSort(inputList, low, pIndex - 1)
    quickSort(inputList, pIndex + 1, high)
  }
  return inputList
}

/**
 * Partition In Place method.
 * @param {number[]} partitionList list for partitioning.
 * @param {number} low lower index for partition.
 * @param {number} high higher index for partition.
 * @returns {number} `pIndex` pivot index value.
 */
const partition = (partitionList, low, high) => {
  const pivot = partitionList[high]
  let pIndex = low
  for (let index = low; index <= high - 1; index++) {
    if (partitionList[index] < pivot) {
      // swap variables using array destructuring
      [partitionList[index], partitionList[pIndex]] = [partitionList[pIndex], partitionList[index]]
      pIndex += 1
    }
  }
  [partitionList[pIndex], partitionList[high]] = [partitionList[high], partitionList[pIndex]]
  return pIndex
}

参考

• 快速排序 - 维基百科，自由的百科全书 (opens new window)