[[428697]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰 。轉載本文請聯系JS每日一題公眾號。

一、是什么

快速排序(Quick Sort)算法是在冒泡排序的基礎上進行改進的一種算法，從名字上看就知道該排序算法的特點是快、效率高，是處理大數據最快的排序算法之一

實現的基本思想是：通過一次排序將整個無序表分成相互獨立的兩部分，其中一部分中的數據都比另一部分中包含的數據的值小

然后繼續沿用此方法分別對兩部分進行同樣的操作，直到每一個小部分不可再分，所得到的整個序列就變成有序序列

例如，對無序表49，38，65，97，76，13，27，49進行快速排序，大致過程為：

首先從表中選取一個記錄的關鍵字作為分割點(稱為“樞軸”或者支點，一般選擇第一個關鍵字)，例如選取 49

將表格中大于 49 個放置于 49 的右側，小于 49 的放置于 49 的左側，假設完成后的無序表為：{27，38，13，49，65，97，76，49}

以 49 為支點，將整個無序表分割成了兩個部分，分別為{27，38，13}和{65，97，76，49}，繼續采用此種方法分別對兩個子表進行排序

前部分子表以 27 為支點，排序后的子表為{13，27，38}，此部分已經有序;后部分子表以 65 為支點，排序后的子表為{49，65，97，76}

此時前半部分子表中的數據已完成排序;后部分子表繼續以 65 為支點，將其分割為{49}和{97，76}，前者不需排序，后者排序后的結果為{76， 97}

通過以上幾步的排序，最后由子表{13，27，38}、{49}、{49}、{65}、{76，97}構成有序表：{13，27，38，49，49，65，76，97}

二、如何實現

可以分成以下步驟：

分區：從數組中選擇任意一個基準，所有比基準小的元素放在基準的左邊，比基準大的元素放到基準的右邊

遞歸：遞歸地對基準前后的子數組進行分區

用代碼表示則如下：

function quickSort (arr) { 
  const rec = (arr) => { 
    if (arr.length <= 1) { return arr; } 
    const left = []; 
    const right = []; 
    const mid = arr[0]; // 基準元素 
    for (let i = 1; i < arr.length; i++){ 
      if (arr[i] < mid) { 
        left.push(arr[i]); 
      } else { 
        right.push(arr[i]); 
      } 
    } 
    return [...rec(left), mid, ...rec(right)] 
  } 
  return res(arr) 
}; 

快速排序是冒泡排序的升級版，最壞情況下每一次基準元素都是數組中最小或者最大的元素，則快速排序就是冒泡排序

這種情況時間復雜度就是冒泡排序的時間復雜度：T[n] = n * (n-1) = n^2 + n，也就是O(n^2)

最好情況下是O(nlogn)，其中遞歸算法的時間復雜度公式：T[n] = aT[n/b] + f(n)，推導如下所示：

關于上述代碼實現的快速排序，可以看到是穩定的

三、應用場景

快速排序時間復雜度為O(nlogn)，是目前基于比較的內部排序中被認為最好的方法，當數據過大且數據雜亂無章時，則適合采用快速排序

參考文獻

https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842

https://www.cnblogs.com/l199616j/p/10597245.html