數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題，即如何讓代碼運(yùn)行得更快，如何讓代碼更省存儲空間。所以，執(zhí)行效率是算法一個(gè)非常重要的考量指標(biāo)。那如何來衡量你編寫的算法代碼的執(zhí)行效率呢？時(shí)間、空間復(fù)雜度分析。

時(shí)間復(fù)雜度
大 O 時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫作漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），簡稱時(shí)間復(fù)雜度。

1、只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
我們在分析一個(gè)算法、一段代碼的時(shí)間復(fù)雜度的時(shí)候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了。這段核心代碼執(zhí)行次數(shù)的 n 的量級，就是整段要分析代碼的時(shí)間復(fù)雜度。

function increment(n){
  let sum = 0;
  for(let i=0;i<n;i++){
    sum += i;
  }
  return sum;
}
復(fù)制代碼

其中第 2 行代碼都是常量級的執(zhí)行時(shí)間，與 n 的大小無關(guān)，所以對于復(fù)雜度并沒有影響。循環(huán)執(zhí)行次數(shù)最多的是第 4行代碼，所以這塊代碼要重點(diǎn)分析。這行代碼被執(zhí)行了 n 次，所以總的時(shí)間復(fù)雜度就是 O(n)。

2、加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度

function fn(n){
  let n = 0;
  let k = 0;
  
  for(let i=0;i<n;i++){
    n += i;
  }
  
  for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
      k += i*j;
    }
  }
}
復(fù)制代碼

綜合這段代碼的時(shí)間復(fù)雜度，我們?nèi)∑渲凶畲蟮牧考?。所以，整段代碼的時(shí)間復(fù)雜度就為 O(n2)。也就是說：總的時(shí)間復(fù)雜度就等于量級最大的那段代碼的時(shí)間復(fù)雜度。

3、乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

function fn(n){
  let res = 0;
  
  for(let i=0;i<n;i++){
    res += add(i);
  }
  
  return res;
}

function add(n){
  let sum = 0;
  for(let j=0;j<n;j++){
    sum += j;
  }
  return sum;
}
復(fù)制代碼

我們看函數(shù)fn的復(fù)雜度，顯而易見就是雙層循環(huán)嵌套。相當(dāng)于嵌套內(nèi)外代碼復(fù)雜度的乘積 O(n) * O(n) = O(n2)

時(shí)間復(fù)雜度按照從小到大的順序排列
常數(shù)時(shí)間 O(1)
對數(shù)時(shí)間 O(logn)
線性時(shí)間 O(nlogn)
二次方 O(n^2)
三次方 O(n^3)
指數(shù)時(shí)間 O(2^n)
常數(shù)階O(1)

function increment(num){
  return ++num;
}
復(fù)制代碼

假設(shè)運(yùn)行 increment(1) 函數(shù)，執(zhí)行時(shí)間等于X。如果再用不同的參數(shù)（例如2）運(yùn)行一次increment函數(shù)，執(zhí)行時(shí)間依然是X。和參數(shù)無關(guān)，increment函數(shù)的性能都一樣。因此，我們說上述函數(shù)的復(fù)雜度是O(1)（常數(shù)）。

線性階O(n)

function sequentialSearch(array, item){ 
  for (var i=0; i<array.length; i++){
    if (item === array[i]){ //{1} 
      return i;
    }
  }
  return -1;
}
復(fù)制代碼

如果將含10個(gè)元素的數(shù)組（[1, ...,10]）傳遞給該函數(shù)，假如搜索1這個(gè)元素，那么，第一次判斷時(shí)就能找到想要搜索的元素。在這里我們假設(shè)每執(zhí)行一次行{1} ，開銷是1。

現(xiàn)在，假如要搜索元素11。行{1}會執(zhí)行10次（遍歷數(shù)組中所有的值，并且找不到要搜索的元素，因而結(jié)果返回 -1）。如果行{1}的開銷是1，那么它執(zhí)行10次的開銷就是10，10倍于第一種假設(shè)

現(xiàn)在，假如該數(shù)組有1000個(gè)元素（[1, ..., 1000]）。搜索1001的結(jié)果是行{1}執(zhí)行了1000次（然后返回-1）

sequentialSearch 函數(shù)執(zhí)行的總開銷取決于數(shù)組元素的個(gè)數(shù)（數(shù)組大?。?，而且也和搜索的值有關(guān)。如果是查找數(shù)組中存在的值，行{1}會執(zhí)行幾次呢？如果查找的是數(shù)組中不存在的值，那么行{1}就會執(zhí)行和數(shù)組大小一樣多次，這就是通常所說的最壞情況

最壞情況下，如果數(shù)組大小是10，開銷就是10；如果數(shù)組大小是1000，開銷就是1000。可以得出 sequentialSearch 函數(shù)的時(shí)間復(fù)雜度是O(n)，n是（輸入）數(shù)組的大小

平方階O(n2)

function swap(arr, i, j){
  [arr[i],arr[j]] = [arr[j],arr[i]]
}
function bubbleSort(array){
 var length = array.length;
 for (var i=0; i<length; i++){ //{1}
  for (var j=0; j<length-1; j++ ){ //{2}
    if (array[j] > array[j+1]){
      swap(array, j, j+1);
    }
  }
 }
}
復(fù)制代碼

bubbleSort 可以對一個(gè)數(shù)字?jǐn)?shù)組進(jìn)行排序運(yùn)算

如果用大小為10的數(shù)組執(zhí)行 bubbleSort ，開銷是_{100。如果用大小為100的數(shù)組執(zhí)行bubbleSort，開銷就是}10000。需要注意，我們每次增加輸入的大小，執(zhí)行都會越來越久

時(shí)間復(fù)雜度O(n)的代碼只有一層循環(huán)，而O(n2)的代碼有雙層嵌套循環(huán)。如果算法有三層遍歷數(shù)組的嵌套循環(huán)，它的時(shí)間復(fù)雜度很可能就是O(n3)

對數(shù)階O(logn)

function fn(arr) {
    const len = arr.length  
    
    for(let i=1;i<len;i=i*2) {
        console.log(arr[i])
    }
}
復(fù)制代碼

這個(gè)算法讀取一個(gè)一維數(shù)組作為入?yún)?，然后對其中的元素進(jìn)行跳躍式的輸出。這個(gè)跳躍的規(guī)則，就是數(shù)組下標(biāo)從1開始，每次會乘以二。

如何計(jì)算這個(gè)函數(shù)的時(shí)間復(fù)雜度呢？在有循環(huán)的地方，我們關(guān)心的永遠(yuǎn)是最內(nèi)層的循環(huán)體。這個(gè)算法中，我們關(guān)心的就是 console.log(arr[i]) 到底被執(zhí)行了幾次，換句話說，也就是要知道 i<n（ len === n） 這個(gè)條件是在 i 遞增多少次后才不成立的。

假設(shè) i 在以 i=i*2 的規(guī)則遞增了 x 次之后， i<n 開始不成立（反過來說也就是 i>=n 成立）。那么此時(shí)我們要計(jì)算的其實(shí)就是這樣一個(gè)數(shù)學(xué)方程： 2^x >= n

x 解出來，就是要大于等于以 2 為底數(shù)的 n 的對數(shù)：

image.png

也就是說，只有當(dāng) x 小于 log2n 的時(shí)候，循環(huán)才是成立的、循環(huán)體才能執(zhí)行。注意涉及到對數(shù)的時(shí)間復(fù)雜度，底數(shù)和系數(shù)都是要被簡化掉的。那么這里的 O(n) 就可以表示為： O(n) = logn

線性對數(shù)階O(nlogn)
將 O(logn) 復(fù)雜度循環(huán)n遍的復(fù)雜度就是 O(nlogn)

function fn(arr) {
    const len = arr.length  
    for(let j=0;j<len;j++){
        i = 1;
        while( i < len ){
            i = i * 2;
        }
    }
}
復(fù)制代碼

空間復(fù)雜度
前面我講過，時(shí)間復(fù)雜度的全稱是漸進(jìn)時(shí)間復(fù)雜度，表示算法的執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。類比一下，空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

空間復(fù)雜度是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度。和時(shí)間復(fù)雜度相似，它是內(nèi)存增長的趨勢。

常見的空間復(fù)雜度有 O(1)、O(n) 和 O(n^2)

O(1)

function traverse(arr) {
    const len = arr.length
    for(let i=0;i<len;i++) {
        console.log(arr[i])
    }
}
復(fù)制代碼

在 traverse 中，占用空間的有以下變量：

arr    
len   
i
復(fù)制代碼

后面盡管咱們做了很多次循環(huán)，但是這些都是時(shí)間上的開銷。循環(huán)體在執(zhí)行時(shí)，并沒有開辟新的內(nèi)存空間。因此，整個(gè) traverse 函數(shù)對內(nèi)存的占用量是恒定的，它對應(yīng)的空間復(fù)雜度就是 O(1)。

O(n)

function init(n) {
    let arr = []
    for(let i=0;i<n;i++) {
        arr[i] = i
    }
    return arr
}
復(fù)制代碼

在這個(gè) init 中，涉及到的占用內(nèi)存的變量有以下幾個(gè)：

n 
arr
i
復(fù)制代碼

注意這里這個(gè) arr，它并不是一個(gè)一成不變的數(shù)組。arr最終的大小是由輸入的 n 的大小決定的，它會隨著 n 的增大而增大、呈一個(gè)線性關(guān)系。因此這個(gè)算法的空間復(fù)雜度就是 O(n)。

由此我們不難想象，假如需要初始化的是一個(gè)規(guī)模為 n*n 的數(shù)組，那么它的空間復(fù)雜度就是 O(n^2) 啦。

最好、最壞情況時(shí)間復(fù)雜度
我們先看一段代碼：

function find(arr,x){
    for(let i=0;i<arr.length;i++){
    if(arr[i] === x){
       return i;
       break;
    }
  }
  return -1;
}

find([2,1,3],1);
復(fù)制代碼

我們在數(shù)組中查找一個(gè)數(shù)據(jù)，并不需要每次都把整個(gè)數(shù)組都遍歷一遍，因?yàn)橛锌赡苤型菊业骄涂梢蕴崆敖Y(jié)束循環(huán)了。

這段代碼的時(shí)間復(fù)雜度還是 O(n) 嗎？因?yàn)橐檎业淖兞?x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個(gè)元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個(gè)數(shù)據(jù)了，那時(shí)間復(fù)雜度就是 O(1)。但如果數(shù)組中不存在變量 x，那我們就需要把整個(gè)數(shù)組都遍歷一遍，時(shí)間復(fù)雜度就成了 O(n)。所以，不同的情況下，這段代碼的時(shí)間復(fù)雜度是不一樣的。

為了表示代碼在不同情況下的不同時(shí)間復(fù)雜度，我們需要引入三個(gè)概念：最好情況時(shí)間復(fù)雜度、最壞情況時(shí)間復(fù)雜度和平均情況時(shí)間復(fù)雜度。

• 最好情況時(shí)間復(fù)雜度就是，在最理想的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度。
• 最壞情況時(shí)間復(fù)雜度就是，在最糟糕的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度分析復(fù)雜，還要涉及概率論的知識。實(shí)際上，在大多數(shù)情況下，我們并不需要區(qū)分最好、最壞、平均情況時(shí)間復(fù)雜度三種情況。很多時(shí)候，我們使用一個(gè)復(fù)雜度就可以滿足需求了。只有同一塊代碼在不同的情況下，時(shí)間復(fù)雜度有量級的差距，我們才會使用這三種復(fù)雜度表示法來區(qū)分。

其實(shí)有一個(gè)很簡單的辦法幫助我們來進(jìn)行粗暴的判斷：

上面最好的情況是 O(1) ，最壞的情況是O(n)，直觀判斷出現(xiàn)O(1)的情況是特別少的。往往都是>1并且小于n的一個(gè)值，但是這個(gè)值依然是一個(gè)變量，因此我們同樣可以認(rèn)為平均時(shí)間復(fù)雜度就是O(n)。

大O表示法其實(shí)本身就是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢，因此別太較真，較真的話也可以去數(shù)學(xué)求導(dǎo)，然后去掉系數(shù)和常量。

排序算法

以面試為導(dǎo)向來看，需要大家著重掌握的排序算法，主要是以下5種：

• 基礎(chǔ)排序算法

  • 冒泡排序
  • 插入排序
  • 選擇排序

• 進(jìn)階排序算法

  • 歸并排序
  • 快速排序

冒泡排序

思路

冒泡排序的過程，就是從第一個(gè)元素開始， 重復(fù)比較相鄰的兩個(gè)項(xiàng) ，若第一項(xiàng)比第二項(xiàng)更大，則交換兩者的位置；反之不動。

每一輪操作，都會將這一輪中最大的元素放置到數(shù)組的末尾。假如數(shù)組的長度是 n ，那么當(dāng)我們重復(fù)完 n 輪的時(shí)候，整個(gè)數(shù)組就有序了。

演示

image

編碼

基礎(chǔ)版：

function bubbleSortBase(arr){
  const len = arr.length;
  for(let i=0;i<len;i++){
    for(let j=0;j<len-1;j++){
      // 前一個(gè)數(shù)字 > 大于后一個(gè)數(shù)字
      if(arr[j]>arr[j+1]){
        [arr[j],arr[j+1]] = [arr[j+1],arr[j]]; // es6 解構(gòu)賦值
      }
    }
  }
  return arr;
}
復(fù)制代碼

隨著外層循環(huán)的進(jìn)行，數(shù)組尾部的元素會漸漸變得有序——當(dāng)我們走完第1輪循環(huán)的時(shí)候，最大的元素被排到了數(shù)組末尾；走完第2輪循環(huán)的時(shí)候，第2大的元素被排到了數(shù)組倒數(shù)第2位；走完第3輪循環(huán)的時(shí)候，第3大的元素被排到了數(shù)組倒數(shù)第3位......以此類推，走完第 n 輪循環(huán)的時(shí)候，數(shù)組的后 n 個(gè)元素就已經(jīng)是有序的。

樓上基本冒泡思路的問題在于，沒有區(qū)別處理這一部分已經(jīng)有序的元素，而是把它和未排序的部分做了無差別的處理，進(jìn)而造成了許多不必要的比較。

為了避免這些冗余的比較動作，我們需要規(guī)避掉數(shù)組中的后 n 個(gè)元素，對應(yīng)的代碼可以這樣寫：

function BubbleSortStable(arr) {
  const len = arr.length
  for(let i=0;i<len;i++) {
    let flag = false;
    // 注意差別在這行，我們對內(nèi)層循環(huán)的范圍作了限制
    for(let j=0;j<len-1-i;j++) { // {1}
      if(arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        flag = true;
      }
    }
    if(!flag) break; // {2}
  }
  return arr;
}
復(fù)制代碼

改動點(diǎn)：

len-1-i

時(shí)間復(fù)雜度
最好時(shí)間復(fù)雜度 ：它對應(yīng)的是數(shù)組本身有序這種情況。在這種情況下，我們只需要作比較（n-1 次），而不需要做交換。時(shí)間復(fù)雜度為 O(n)
最壞時(shí)間復(fù)雜度 ： 它對應(yīng)的是數(shù)組完全逆序這種情況。在這種情況下，每一輪內(nèi)層循環(huán)都要執(zhí)行，重復(fù)的總次數(shù)是 n(n-1)/2 次，因此時(shí)間復(fù)雜度是 O(n^2)
平均時(shí)間復(fù)雜度 ：這個(gè)東西比較難搞，它涉及到一些概率論的知識。實(shí)際面試的時(shí)候也不會有面試官摁著你讓你算這個(gè)，這里記住平均時(shí)間復(fù)雜度是 O(n^2) 即可。
選擇排序
思路
選擇排序的關(guān)鍵字是“ 最小值 ”：循環(huán)遍歷數(shù)組，每次都找出當(dāng)前范圍內(nèi)的最小值，把它放在當(dāng)前范圍的頭部；然后縮小排序范圍，繼續(xù)重復(fù)以上操作，直至數(shù)組完全有序?yàn)橹埂?/p>

演示

image

編碼

function selectSort(arr){
  const len = arr.length; // 緩存數(shù)組長度
  let minIndex;

  for(let i=0;i<len - 1;i++){

    minIndex = i; // 最小值的位置，先定位數(shù)組的第一個(gè)

    for(let j=i;j<len;j++){
      // 若 j 處的數(shù)據(jù)項(xiàng)比當(dāng)前最小值還要小，則更新最小值索引為 j
      if(arr[j]<arr[minIndex]){
        minIndex = j;
      }
    }

    // 如果最小值的位置，不是初始化時(shí)的位置，就可以進(jìn)行交換了。
    if(minIndex !== i){
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }

  }

  return arr;
}

console.log(selectSort([3,5,8,1,4]));

復(fù)制代碼

時(shí)間復(fù)雜度

在時(shí)間復(fù)雜度這方面，選擇排序沒有那么多彎彎繞繞：最好情況也好，最壞情況也罷，兩者之間的區(qū)別僅僅在于元素交換的次數(shù)不同， 但都是要走內(nèi)層循環(huán)作比較的 。因此選擇排序的三個(gè)時(shí)間復(fù)雜度都對應(yīng)兩層循環(huán)消耗的時(shí)間量級： O(n^2)。

插入排序

思路

插入排序的核心思想是“找到元素在它前面那個(gè)序列中的正確位置”。 具體來說，插入排序所有的操作都基于一個(gè)這樣的前提：當(dāng)前元素前面的序列是有序的?；谶@個(gè)前提，從后往前去尋找當(dāng)前元素在前面那個(gè)序列里的正確位置。

演示

image

編碼

function insertSort(arr){
  const len = arr.length;

  let target;

  for(let i=0;i<len;i++){
    let index = i;
    target = arr[i];

    while(index>0 && arr[index-1] > target){
      arr[index] = arr[index-1]; // 這個(gè)步驟相當(dāng)于是把前面一個(gè)值，移動到后面一位來。
      index--;
    }
    // 表明沒有進(jìn)入while循環(huán)，因此沒有發(fā)生位置交換，就不必交換位置了。
    if(arr[index] !== target){
      arr[index] = target ; // 最后確定好的位置，放入上面保存好的值。
    }

  }

  return arr;
}
復(fù)制代碼

時(shí)間復(fù)雜度

• 最好時(shí)間復(fù)雜度 ：它對應(yīng)的數(shù)組本身就有序這種情況。此時(shí)內(nèi)層循環(huán)只走一次，整體復(fù)雜度取決于外層循環(huán)，時(shí)間復(fù)雜度就是一層循環(huán)對應(yīng)的 O(n) 。
• 最壞時(shí)間復(fù)雜度 ：它對應(yīng)的是數(shù)組完全逆序這種情況。此時(shí)內(nèi)層循環(huán)每次都要移動有序序列里的所有元素，因此時(shí)間復(fù)雜度對應(yīng)的就是兩層循環(huán)的 O(n^2)
• 平均時(shí)間復(fù)雜度 ：O(n^2)

所謂基礎(chǔ)排序算法，普遍符合兩個(gè)特征：

1. 易于理解，上手迅速
2. 時(shí)間效率差

上面的三個(gè)算法完美地詮釋了這兩個(gè)特征。

那么在此基礎(chǔ)上，排序效率如何提升、排序算法如何與進(jìn)階的算法思想相結(jié)合？下面我們就來介紹兩個(gè)常用的高級排序算法。

歸并排序

“分治”思想

“分治”，分而治之。其思想就是將一個(gè)大問題分解為若干個(gè)子問題，針對子問題分別求解后，再將子問題的解整合為大問題的解。

利用分治思想解決問題，我們一般分三步走：

• 分解子問題
• 求解每個(gè)子問題
• 合并子問題的解，得出大問題的解

思路

歸并排序是對分治思想的典型應(yīng)用，它按照如下的思路對分治思想“三步走”的框架進(jìn)行了填充：

• 分解子問題 ：將需要被排序的數(shù)組從中間分割為兩半，然后再將分割出來的每個(gè)子數(shù)組各分割為兩半，重復(fù)以上操作，直到單個(gè)子數(shù)組只有一個(gè)元素為止。
• 求解每個(gè)子問題 ：從粒度最小的子數(shù)組開始，兩兩合并、確保每次合并出來的數(shù)組都是有序的。（這里的“子問題”指的就是對每個(gè)子數(shù)組進(jìn)行排序）。
• 合并子問題的解，得出大問題的解 ：當(dāng)數(shù)組被合并至原有的規(guī)模時(shí)，就得到了一個(gè)完全排序的數(shù)組

演示

image

編碼

• 拆分動作：負(fù)責(zé)拆分?jǐn)?shù)組到期望的粒度
• 合并動作：排序合并數(shù)組

const mergeSort = arr => {
  //采用自上而下的遞歸方法
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  // length >> 1 和 Math.floor(len / 2) 等價(jià)
  let middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle); // 拆分為兩個(gè)子數(shù)組
  // 遞歸拆分
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const result = [];

  while (left.length && right.length) {
    // 注意: 判斷的條件是小于或等于，如果只是小于，那么排序?qū)⒉环€(wěn)定.
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  // left 數(shù)組 或者 right 數(shù)組剩余的數(shù)字插入到 result 數(shù)組的后面。
  while (left.length) result.push(left.shift());

  while (right.length) result.push(right.shift());

  return result;
};
復(fù)制代碼

結(jié)合代碼分解：

拆分例如：[1,5,3,2]

[1,5] [3,2]
[1] [5] [3] [2]
在合并動作時(shí)進(jìn)行排序：

[1][5] => [1,5]
[2][3] => [2,3]
然后 [1,5] [2,3] 進(jìn)行合并：

left.length && right.length
while (left.length) result.push(left.shift());

時(shí)間復(fù)雜度
從效率上看，歸并排序可算是排序算法中的佼佼者。假設(shè)數(shù)組長度為 n，那么拆分?jǐn)?shù)組共需 logn 步，又每步都是一個(gè)普通的合并子數(shù)組的過程，時(shí)間復(fù)雜度為 O(n)，故其綜合時(shí)間復(fù)雜度為 O(n log n)。 最佳情況：T(n) = O(n log n)。 最差情況：T(n) = O(n log n)。 平均情況：T(n) = O(n log n)。

快速排序
快速排序的核心思想，依然是分治法。

思路一
先找到一個(gè)基準(zhǔn)點(diǎn)（一般指數(shù)組的中部），然后數(shù)組被該基準(zhǔn)點(diǎn)分為兩部分，依次與該基準(zhǔn)點(diǎn)數(shù)據(jù)比較，如果比它小，放左邊；反之，放右邊；
左右分別用一個(gè)空數(shù)組去存儲比較后的數(shù)據(jù)；
最后遞歸執(zhí)行上述操作，直到數(shù)組長度 <= 1。
演示一
[1,5,3,4,2]

第一步：選擇中間的元素3作為"基準(zhǔn)"。（基準(zhǔn)值可以任意選擇，但是選擇中間的值比較容易理解。）[1,5,3,4,2]
第二步，按照順序，將每個(gè)元素與"基準(zhǔn)"進(jìn)行比較，形成兩個(gè)子集，一個(gè)"小于3"，另一個(gè)"大于等于3"。[1,2] 3 [5,4]
第三步，對兩個(gè)子集不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。[1,2] 3 [5,4]
第四步，遞歸比較。[1] 2 [] + 3 [] 4 [5]
順序就出來了。這種思路有一個(gè)缺點(diǎn)就是需要再定義兩個(gè)數(shù)組來裝比較后的數(shù)據(jù)。但是實(shí)現(xiàn)起來簡單易懂。通常在面試中能答出這種思路就可以了。

編碼一

const quickSort1 = arr => {
  if (arr.length <= 1) {
    return arr;
  }

  //取基準(zhǔn)點(diǎn)
  const midIndex = Math.floor(arr.length / 2);

  //取基準(zhǔn)點(diǎn)的值，splice(index,1) 則返回的是含有被刪除的元素的數(shù)組。
  const valArr = arr.splice(midIndex, 1);

  const midIndexVal = valArr[0];

  const left = []; //存放比基準(zhǔn)點(diǎn)小的數(shù)組
  const right = []; //存放比基準(zhǔn)點(diǎn)大的數(shù)組

  //遍歷數(shù)組，進(jìn)行判斷分配
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midIndexVal) {
      left.push(arr[i]); //比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組
    } else {
      right.push(arr[i]); //比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組
    }
  }
  
  //遞歸執(zhí)行以上操作，對左右兩個(gè)數(shù)組進(jìn)行操作，直到數(shù)組長度為 <= 1
  return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
復(fù)制代碼

思路二
思路二較思路一主要區(qū)別在于，并不會把真的數(shù)組分割開來再合并到一個(gè)新數(shù)組中去，而是直接在原有的數(shù)組內(nèi)部進(jìn)行排序，節(jié)省內(nèi)存空間。

通常我們能想到的辦法就是使用雙指針來代替思路一中的兩個(gè)空數(shù)組。

演示二
[5,4,3,1,2]

left 左指針初始值為0，right 右指針初始值為arr.length - 1，第一個(gè)基準(zhǔn)點(diǎn)是值為3 [5,4,3,1,2]
以3為基準(zhǔn)，左指針開始從下標(biāo)0走起，走到下標(biāo)為0也就是值為5時(shí)，停止下來
右指針，從下標(biāo)4開始走起，第一個(gè)值是2比3小，停止下來。
此時(shí) left = 0，right = 4，在數(shù)組中，讓兩個(gè)互換位置結(jié)果 [2,4,3,1,5]
此時(shí)左指針開始向前走，走下標(biāo)為1，值為4停下來，右指針走到下表為3，值為1停下來
此時(shí) left = 1，right = 3，在數(shù)組中，讓兩個(gè)互換位置結(jié)果 [2,1,3,4,5]
交換完位置后，左指針向前進(jìn)一位，右指針也向左進(jìn)一位，left = 2 ，right = 2
左指針再向前走一位，left = 3 ，右指針再向左走一位，right = 1；
當(dāng)left > right 時(shí)，一輪比較結(jié)束，返回左指針指向的位置。
以左指針為基準(zhǔn)把數(shù)組“劃分”成 [2,1,3] [4,5]
[2,1,3] 都會小于等于 第一輪的基準(zhǔn)值 3；[4,5]都會大于等于基準(zhǔn)值
不斷拆分，不斷遞歸，最后就排好序了。
編碼二

function quickSort(arr,left = 0,right = arr.length -1){
    // 如果數(shù)組只有一項(xiàng)，是不需要進(jìn)行排序的。
  if(arr.length <=1){
    return arr;
  }
  // 每次遞歸分區(qū)，數(shù)組總是不變，變化的是傳入的指針位置，這樣就巧妙的代替了兩個(gè)空數(shù)組
  const nextPointer = partition(arr,left,right); 
  
  // 當(dāng)left左指針小于右指針時(shí)，遞歸調(diào)用
  if(left < nextPointer-1){
    quickSort(arr, left, nextPointer-1);
  }
  
  // 此時(shí) nextPointer 相當(dāng)于拆分后數(shù)組的右數(shù)組的左指針
  if(nextPointer < right){
     quickSort(arr, nextPointer, right);
  }
  
  return arr;
}

function partition(arr,left,right){
    // 獲取基準(zhǔn)值
  let pivotVal = arr[Math.floor(left + (right-left)/2)];
  
  let leftPoint = left; 
  let rightPoint = right;
  
  while(leftPoint<=rightPoint){
    while(arr[leftPoint] < pivotVal){
        leftPoint ++; // 左指針指向的值 小于 基準(zhǔn)值時(shí) 向前走一格;
    }
    
   while(arr[rightPoint] > pivotVal){
        rightPoint --; // 右指針指向的值 大于 基準(zhǔn)值時(shí) 向左走一格;
   }
    
   // 左指針小于等于右指針時(shí)，才進(jìn)行交換位置
   if(leftPoint<=rightPoint){
     // 解構(gòu)賦值交換數(shù)組位置
    [arr[leftPoint], arr[rightPoint]] = [arr[rightPoint], arr[leftPoint]];
     // 每次交換完位置后，指針都移動到下一位
     leftPoint ++;
     rightPoint --;
   }
  }
  
  return leftPoint; 返回左指針的位置，以此為基準(zhǔn)去劃分?jǐn)?shù)組。
}

復(fù)制代碼

有想了解更多的小伙伴可以加Q群鏈接里面看一下，應(yīng)該對你們能夠有所幫助。