[[428697]]

本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰 。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。

一、是什么

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

實(shí)現(xiàn)的基本思想是：通過一次排序?qū)⒄麄€(gè)無序表分成相互獨(dú)立的兩部分，其中一部分中的數(shù)據(jù)都比另一部分中包含的數(shù)據(jù)的值小

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

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

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

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

以 49 為支點(diǎn)，將整個(gè)無序表分割成了兩個(gè)部分，分別為{27，38，13}和{65，97，76，49}，繼續(xù)采用此種方法分別對(duì)兩個(gè)子表進(jìn)行排序

前部分子表以 27 為支點(diǎn)，排序后的子表為{13，27，38}，此部分已經(jīng)有序;后部分子表以 65 為支點(diǎn)，排序后的子表為{49，65，97，76}

此時(shí)前半部分子表中的數(shù)據(jù)已完成排序;后部分子表繼續(xù)以 65 為支點(diǎn)，將其分割為{49}和{97，76}，前者不需排序，后者排序后的結(jié)果為{76， 97}

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

二、如何實(shí)現(xiàn)

可以分成以下步驟：

分區(qū)：從數(shù)組中選擇任意一個(gè)基準(zhǔn)，所有比基準(zhǔn)小的元素放在基準(zhǔn)的左邊，比基準(zhǔn)大的元素放到基準(zhǔn)的右邊

遞歸：遞歸地對(duì)基準(zhǔn)前后的子數(shù)組進(jìn)行分區(qū)

用代碼表示則如下：

function quickSort (arr) { 
  const rec = (arr) => { 
    if (arr.length <= 1) { return arr; } 
    const left = []; 
    const right = []; 
    const mid = arr[0]; // 基準(zhǔn)元素 
    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) 
}; 

快速排序是冒泡排序的升級(jí)版，最壞情況下每一次基準(zhǔn)元素都是數(shù)組中最小或者最大的元素，則快速排序就是冒泡排序

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

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

關(guān)于上述代碼實(shí)現(xiàn)的快速排序，可以看到是穩(wěn)定的

三、應(yīng)用場(chǎng)景

快速排序時(shí)間復(fù)雜度為O(nlogn)，是目前基于比較的內(nèi)部排序中被認(rèn)為最好的方法，當(dāng)數(shù)據(jù)過大且數(shù)據(jù)雜亂無章時(shí)，則適合采用快速排序

參考文獻(xiàn)

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