快速排序法(Quick Sort)又称分割交换排序法，是目前公认效率极佳的演算法，使用了分治法(Divide and Conquer)的概念。原理是先从原始资料列中找一个基准值(Pivot)，接着逐一将资料与基准值比较，小於基准值的资料放在左边，大於基准值的资料放在右边，再将两边区块分别再找出基准值，重复前面的步骤，直到排序完为止。

常用的基准值(Pivot)选择方式:

• 选择第1笔或最後1笔的资料
• 随机乱数
• 三数中位数(Median-of-three)，第一、中间、最後笔资料，排序之後取中间的值(Musser, 1997)。
  例如: 1,5,9,6,3，取出1,9,3，排序後1,3,9，取3为基准点。

平均时间复杂度为: O(n log n)

由於快速排序法有多种实作版本，下面介绍常见的3种实作版本。

递回版本

此版本虽然容易理解，但会影响到空间复杂度，每次都需要申请两个子数列的记忆体空间，递回的深度越多，需要记忆体空间就越大。

操作流程:

1. 资料列中找出一个基准值(Pivot)
2. 将小於Pivot的资料放在左边，大於Pivot的资料放在右边
3. 左右两边资料分别重复1~2步骤，直到剩下1笔资料
4. 合并

下面利用50 90 70 20 10 30 40 60 80由小到大排序。

JavaScript

let data = [50,90,70,20,10,30,40,60,80]

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let left = [];
  let right = [];
  let pivot = arr[0];
  for (let i = 1; i < arr.length; i++) {
    let num = arr[i];
    if (num < pivot) {
      left.push(num);
    } else {
      right.push(num);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort(data))//[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

#Quick Sort
def QuickSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    left = []
    right = []
    pivot = arr[0]
    for i in range(1,n):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return QuickSort(left) + [pivot] + QuickSort(right)

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data))#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交换版本(In-Place)-Lomuto partition scheme

基於Lomuto partition scheme的原理，原始资料列使用一个指标与索引，当索引的资料小於Pivot时，索引的资料与指标位置资料交换。

前面的版本会需要额外的记忆体空间，In-Place版本不需要额外的子数列记忆体空间，因为只会更改原本的数列，切割的同时也就等同合并了，所以只需花费常数O(1)的空间复杂度。实作时会需要用到Partition辅助函式，来直接分割原本的数列。

操作流程:

1. 资料列最後一笔设定为基准值(Pivot)
2. 设定一个指标指向资料列第一笔，用来记录小於Pivot的资料位置
3. 逐一与Pivot比较
4. 若当前资料小於Pivot，就将该资料与指标位置的资料做交换，接着指标往下一个位置移动
5. 若当前资料大於等於Pivot，则跳过不做任何动作
6. 当所有资料比较过後，再将Pivot与指标位置的资料交换
7. 左右两边资料列分别重复1~6步骤，直到剩下1笔分割交换完成，不须合并

下面利用90 40 10 60 70 30 80 20 50由小到大排序。

单回合细节图

每回合简略图

JavaScript

let data = [90, 40, 10, 60, 70, 30, 80, 20, 50];

function quickSort(arr, start, end) {
  if (start < end) {
    const pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr
}

function partition(arr, start, end) {
  let pivot = arr[end];
  let nextIndex = start;
  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      [arr[nextIndex],arr[i]] = [arr[i],arr[nextIndex]]
      nextIndex++;
    }
  }
  [arr[nextIndex],arr[end]] = [arr[end],arr[nextIndex]]  
  return nextIndex
}

console.log(quickSort(data, 0, data.length - 1)) //[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = partition(arr, start, end)
        QuickSort(arr, start, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, end)
    return arr

def partition(arr, start, end):
    n = len(arr)
    pivot = arr[end]
    nextIndex = start
    for i in range(start,n-1):
        if arr[i] < pivot:
            arr[nextIndex],arr[i] = arr[i],arr[nextIndex]
            nextIndex += 1
    arr[nextIndex],arr[end] = arr[end],arr[nextIndex]
    return nextIndex

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data, 0 , len(data)-1))
#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交换版本(In-Place)-Hoare partition scheme

基於Hoare partition scheme的原理，将原始资料列使用两个指标，从资料列的两端开始相互移动，直到它们相遇或反转为止。

操作流程:

1. 资料列中找出一个基准值(Pivot)
2. 最左边有一个指标(Pointer) L，最右边也有一个指标(Pointer) R
3. L逐一往右移动直到找到大於Pivot停下来
4. R逐一往左移动直到找到小於Pivot停下来
5. L与R的资料互相交换，L与R继续移动
6. L与R重叠时，重叠位置的资料Pivot互相交换
7. L与R反转时，R位置的资料与Pivot互相交换
8. 基准值的左右两边资料分别重复1~7步骤，直到剩下1笔分割交换完成，不须合并

下面利用30 10 40 5 70 15 60 20 50 25由小到大排序。

单回合细节图

每回合简略图

JavaScript

let data = [30,10,40,5,70,15,60,20,50,25];

function quickSort(arr, start, end) {
  if (start < end) {
    let pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex-1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr;
}

function partition(arr, start, end) {
  let pivot = arr[start]
  let leftPointer = start+1
  let rightPointer = end
  let done = false
  while (done===false) {
    while (leftPointer <= rightPointer&&arr[leftPointer] <= pivot) {
      leftPointer +=1
    }

    while (leftPointer <= rightPointer&&arr[rightPointer] >= pivot) {
      rightPointer -=1
    }

    if (leftPointer > rightPointer) {
      done = true
    }else{
      [arr[leftPointer],arr[rightPointer]]=[arr[rightPointer],arr[leftPointer]]
    }
  }
  [arr[start],arr[rightPointer]]=[arr[rightPointer],arr[start]]
  return rightPointer
}

console.log(quickSort(data, 0, data.length - 1))
//[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = Partition(arr, start, end)
        QuickSort(arr, start, pivotIndex-1)
        QuickSort(arr, pivotIndex+1, end)
    return arr

def Partition(arr, start, end):
    pivot = arr[start]
    leftPointer = start+1
    rightPointer = end
    done = False
    while not done:
        while leftPointer <= rightPointer and arr[leftPointer] <= pivot:
            leftPointer += 1
        while arr[rightPointer] >= pivot and rightPointer >=leftPointer:
            rightPointer -= 1
        if rightPointer < leftPointer:
            done= True
        else:
            arr[leftPointer],arr[rightPointer] = arr[rightPointer],arr[leftPointer]
    arr[start],arr[rightPointer] = arr[rightPointer],arr[start]
    return rightPointer
    
        
data = [30,10,40,5,70,15,60,20,50,25]

print(QuickSort(data, 0 , len(data)-1))
#[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]