今天要介紹的是快速排序法 Quick Sort，它普遍被認為最快的排序演算法，並且採用分治法(Divide and Conquer)。運作方式是在資料列設定一個基準點(pivot)，然後分別從最左邊和最右邊的數開始比較，將比基準點小的資料移到左邊，比基準點大的資料移到右邊。

之後就變成: "小資料 + 基準點 + 大資料" 這樣的順序，之後可以在小資料和大資料的部分再各找基準點，然後再做數次資料移動，不斷重複這些步驟，最後會得到一個有排序過的資料列。

此網頁有小動畫可以參考看看，非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php

接著我們來實作吧!完成後會討論其時間複雜度~

// 交换
function swap(arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

function partition(arr, left, right) {
  // 設定基準值在資料列中間
  const pivot = arr[Math.floor((right + left) / 2)];

  // 左邊索引小於等於右邊索引都會持續比較
  while (left <= right) {

    // 從左到右找到不小於基準值的元素為止
    // 注意遇到相等的情况也要停下
    while (arr[left] < pivot) {
      left++;
    }

    // 從右到左找到不大於基準值的元素為止
    // 注意遇到相等的情况也要停下
    while (arr[right] > pivot) {
      right--;
    }

    // 當右邊元素大於等於左邊元素就做交換
    if (left <= right) {
      swap(arr, left, right);
      
      left++;
      right--;
    }
  }
  // 回傳分區的索引
  return left;
}

function quickSort(arr, left, right) {
  // 紀錄分裂的索引
  let index;

  // 確保原本陣列長度大於1
  if (arr.length > 1) {

    // 一開始left和right都是undefined，因此設定typeof判斷是否是數字來給left和right初始值
    left = typeof left != "number" ? 0 : left;
    right = typeof right != "number" ? arr.length - 1 : right;
    console.log(left, right);

    // 獲得分裂位置索引
    index = partition(arr, left, right);

    // 從基準值位置判斷，確保左邊陣列還有元素存在
    if (left < index - 1) {
      quickSort(arr, left, index - 1);
    }

    // 從基準值位置判斷，確保右邊陣列還有元素存在
    if (index < right) {
      quickSort(arr, index, right);
    }
  }
  return arr;
}

console.log(quickSort([1, 234, -5, 78, -182, 45]));

2021/02/18 更新另外解法: 解構+遞迴解法

function quickSort(array) {
  if (array.length === 0) {
    return [];
  } else {
    const pivotValue = array[0];
    let lesser = [];
    let equal = [];
    let greater = [];
    for (let e of array) {
      if (e < pivotValue) {
        lesser.push(e);
      } else if (e > pivotValue) {
        greater.push(e);
      } else {
        equal.push(e);
      }
    }
    return [...quickSort(lesser), ...equal, ...quickSort(greater)];
  }
}

時間複雜度:

• 最佳時間複雜度: Ο(n log n)
  第一個基準值的位置剛好是中位數，將資料均分成二等份，然後依序拆分子陣列
  

• 平均時間複雜度: Ο(n log n)

• 最差時間複雜度: Ο(n^2)
  當資料的順序恰好為由大到小或由小到大時

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day21-quick-sort.js

排序相關的演算法到這邊結束。明天將會介紹搜尋演算法-循序搜尋法!