編程技術(shù)中冒泡排序、快速排序和堆排序的時(shí)間復(fù)雜度是多少

這篇文章主要介紹編程技術(shù)中冒泡排序、快速排序和堆排序的時(shí)間復(fù)雜度是多少，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

冒泡排序的時(shí)間復(fù)雜度：最好情況是“O(n)”，最壞情況是“O(n2)”?？焖倥判虻牡臅r(shí)間復(fù)雜度：最好情況是“O(nlogn)”，最壞情況是“O(n2)”。堆排序的時(shí)間復(fù)雜度是“O(nlogn)”。

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

冒泡排序（Bubble Sort）

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

最好的情況：數(shù)組本身是順序的，外層循環(huán)遍歷一次就完成O(n)

最壞的情況：數(shù)組本身是逆序的，內(nèi)外層遍歷O(n2)

空間復(fù)雜度
開(kāi)辟一個(gè)空間交換順序O(1)
穩(wěn)定性
穩(wěn)定，因?yàn)閕f判斷不成立，就不會(huì)交換順序，不會(huì)交換相同元素

• 冒泡排序它在所有排序算法中最簡(jiǎn)單。然而， 從運(yùn)行時(shí)間的角度來(lái)看，冒泡排序是最差的一個(gè)，它的復(fù)雜度是O(n2)。

• 冒泡排序比較任何兩個(gè)相鄰的項(xiàng)，如果第一個(gè)比第二個(gè)大，則交換它們。元素項(xiàng)向上移動(dòng)至正確的順序，就好像氣泡升至表面一樣，冒泡排序因此得名。

• 交換時(shí)，我們用一個(gè)中間值來(lái)存儲(chǔ)某一交換項(xiàng)的值。其他排序法也會(huì)用到這個(gè)方法，因此我 們聲明一個(gè)方法放置這段交換代碼以便重用。使用ES6（ECMAScript 2015）**增強(qiáng)的對(duì)象屬性——對(duì)象數(shù)組的解構(gòu)賦值語(yǔ)法，**這個(gè)函數(shù)可以寫成下面 這樣：

[array[index1], array[index2]] = [array[index2], array[index1]];

具體實(shí)現(xiàn)：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {//外循環(huán)（行{2}）會(huì)從數(shù)組的第一位迭代 至最后一位，它控制了在數(shù)組中經(jīng)過(guò)多少輪排序
    for (let j = 0; j < arr.length - i; j++) {//內(nèi)循環(huán)將從第一位迭代至length - i位，因?yàn)楹骾位已經(jīng)是排好序的，不用重新迭代
      if (arr[j] > arr[j + 1]) {//如果前一位大于后一位
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交換位置
      }
    }
  }
  return arr;
}

快速排序

時(shí)間復(fù)雜度
最好的情況：每一次base值都剛好平分整個(gè)數(shù)組，O(nlogn)
最壞的情況：每一次base值都是數(shù)組中的最大/最小值，O(n2)

空間復(fù)雜度
快速排序是遞歸的，需要借助棧來(lái)保存每一層遞歸的調(diào)用信息，所以空間復(fù)雜度和遞歸樹(shù)的深度一致
最好的情況：每一次base值都剛好平分整個(gè)數(shù)組，遞歸樹(shù)的深度O(logn)
最壞的情況：每一次base值都是數(shù)組中的最大/最小值，遞歸樹(shù)的深度O(n)

穩(wěn)定性
快速排序是不穩(wěn)定的，因?yàn)榭赡軙?huì)交換相同的關(guān)鍵字。
快速排序是遞歸的，
特殊情況：left>right,直接退出。

步驟：

(1) 首先，從數(shù)組中選擇中間一項(xiàng)作為主元base，一般取第一個(gè)值。

(2) 創(chuàng)建兩個(gè)指針，左邊一個(gè)指向數(shù)組第一個(gè)項(xiàng)，右邊一個(gè)指向數(shù)組最后一個(gè)項(xiàng)。移動(dòng)右指針直到找到一個(gè)比主元小的元素，接著，移動(dòng)左指 針直到我們找到一個(gè)比主元大的元素，然后交 換它們，重復(fù)這個(gè)過(guò)程，直到左指針遇見(jiàn)了右指針。這個(gè)過(guò)程將使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。這一步叫作劃分操作。

(3)然后交換主元和指針停下來(lái)的位置的元素（等于說(shuō)是把這個(gè)元素歸位，這個(gè)元素左邊的都比他小，右邊的都比他大，這個(gè)位置就是他最終的位置）

(4) 接著，算法對(duì)劃分后的小數(shù)組（較主元小的值組成的子數(shù)組，以及較主元大的值組成的 子數(shù)組）重復(fù)之前的兩個(gè)步驟(遞歸方法），

遞歸的出口為left/right=i，也就是：

left>i-1 / i+1>right

此時(shí)，子數(shù)組數(shù)組已排序完成。

歸位示意圖：

具體實(shí)現(xiàn)：

function quicksort(arr, left, right) {
  if (left > right) {
    return;
  }
  var i = left,
    j = right,
    base = arr[left]; //基準(zhǔn)總是取序列開(kāi)頭的元素
  //   var [base, i, j] = [arr[left], left, right]; //以left指針元素為base
  while (i != j) {
    //i=j，兩個(gè)指針相遇時(shí)，一次排序完成，跳出循環(huán)
    // 因?yàn)槊看未笱h(huán)里面的操作都會(huì)改變i和j的值，所以每次循環(huán)/操作前都要判斷是否滿足i<j
    while (i < j && arr[j] >= base) {
      //尋找小于base的右指針元素a，跳出循環(huán)，否則左移一位
      j--;
    }
    while (i < j && arr[i] <= base) {
      //尋找大于base的左指針元素b，跳出循環(huán)，否則右移一位
      i++;
    }
    if (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; //交換a和b
    }
  }
  [arr[left], arr[j]] = [arr[j], arr[left]]; //交換相遇位置元素和base，base歸位
  //   let k = i;
  quicksort(arr, left, i - 1); //對(duì)base左邊的元素遞歸排序
  quicksort(arr, i + 1, right); //對(duì)base右邊的元素遞歸排序
  return arr;
}

參考：https://www.cnblogs.com/venoral/p/5180439.html

堆排序

堆的概念

• 堆是一個(gè)完全二叉樹(shù)。

• 完全二叉樹(shù)： 二叉樹(shù)除開(kāi)最后一層，其他層結(jié)點(diǎn)數(shù)都達(dá)到最大，最后一層的所有結(jié)點(diǎn)都集中在左邊（左邊結(jié)點(diǎn)排列滿的情況下，右邊才能缺失結(jié)點(diǎn)）。

• 大頂堆：根結(jié)點(diǎn)為最大值，每個(gè)結(jié)點(diǎn)的值大于或等于其孩子結(jié)點(diǎn)的值。

• 小頂堆：根結(jié)點(diǎn)為最小值，每個(gè)結(jié)點(diǎn)的值小于或等于其孩子結(jié)點(diǎn)的值。

• 堆的存儲(chǔ)： 堆由數(shù)組來(lái)實(shí)現(xiàn)，相當(dāng)于對(duì)二叉樹(shù)做層序遍歷。如下圖：
  
  

時(shí)間復(fù)雜度
總時(shí)間為建堆時(shí)間+n次調(diào)整堆 —— O(n)+O(nlogn)=O(nlogn)
建堆時(shí)間：從最后一個(gè)非葉子節(jié)點(diǎn)遍歷到根節(jié)點(diǎn)，復(fù)雜度為O(n)
n次調(diào)整堆：每一次調(diào)整堆最長(zhǎng)的路徑是從樹(shù)的根節(jié)點(diǎn)到葉子結(jié)點(diǎn)，也就是樹(shù)的高度logn，所以每一次調(diào)整時(shí)間復(fù)雜度是O(logn)，一共是O(nlogn)

空間復(fù)雜度
堆排序只需要在交換元素的時(shí)候申請(qǐng)一個(gè)空間暫存元素，其他操作都是在原數(shù)組操作，空間復(fù)雜度為O(1)

穩(wěn)定性
堆排序是不穩(wěn)定的，因?yàn)榭赡軙?huì)交換相同的子結(jié)點(diǎn)。

步驟一：建堆

• 以升序遍歷為例子，需要先將將初始二叉樹(shù)轉(zhuǎn)換成大頂堆，要求滿足：樹(shù)中任一非葉子結(jié)點(diǎn)大于其左右孩子。

• 實(shí)質(zhì)上是調(diào)整數(shù)組元素的位置，不斷比較，做交換操作。

• 找到第一個(gè)非葉子結(jié)點(diǎn)——Math.floor(arr.length / 2 - 1)，從后往前依次遍歷

• 對(duì)每一個(gè)結(jié)點(diǎn)，檢查結(jié)點(diǎn)和子結(jié)點(diǎn)的大小關(guān)系，調(diào)整成大根堆

// 建立大頂堆
function buildHeap(arr) {
  //從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，向前遍歷，
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    headAdjust(arr, i, arr.length); //對(duì)每一個(gè)節(jié)點(diǎn)都調(diào)整堆，使其滿足大頂堆規(guī)則
  }
}

步驟二：調(diào)整指定結(jié)點(diǎn)形成大根堆

• 建立childMax指針指向child最大值節(jié)點(diǎn)，初始值為2 * cur + 1，指向左節(jié)點(diǎn)

• 當(dāng)左節(jié)點(diǎn)存在時(shí)（左節(jié)點(diǎn)索引小于數(shù)組length），進(jìn)入循環(huán)，遞歸調(diào)整所有節(jié)點(diǎn)位置，直到沒(méi)有左節(jié)點(diǎn)為止（cur指向一個(gè)葉結(jié)點(diǎn)為止），跳出循環(huán)，遍歷結(jié)束

• 每次循環(huán)，先判斷右節(jié)點(diǎn)存在時(shí)，右節(jié)點(diǎn)是否大于左節(jié)點(diǎn)，是則改變childMax的指向

• 然后判斷cur根節(jié)點(diǎn)是否大于childMax，

• 大于的話，說(shuō)明滿足大頂堆規(guī)律，不需要再調(diào)整，跳出循環(huán)，結(jié)束遍歷

• 小于的話，說(shuō)明不滿足大頂堆規(guī)律，交換根節(jié)點(diǎn)和子結(jié)點(diǎn)，

• 因?yàn)榻粨Q了節(jié)點(diǎn)位置，子結(jié)點(diǎn)可能會(huì)不滿足大頂堆順序，所以還要判斷子結(jié)點(diǎn)然后，改變cur和childMax指向子結(jié)點(diǎn)，繼續(xù)循環(huán)判斷。

//從輸入節(jié)點(diǎn)處調(diào)整堆
function headAdjust(arr, cur, len) {
  let intialCur = arr[cur]; //存放最初始的
  let childMax = 2 * cur + 1; //指向子樹(shù)中較大的位置，初始值為左子樹(shù)的索引

  //子樹(shù)存在（索引沒(méi)超過(guò)數(shù)組長(zhǎng)度）而且子樹(shù)值大于根時(shí)，此時(shí)不符合大頂堆結(jié)構(gòu)，進(jìn)入循環(huán)，調(diào)整堆的結(jié)構(gòu)
  while (childMax < len) {
    //判斷左右子樹(shù)大小,如果右子樹(shù)更大，而且右子樹(shù)存在，childMax指針指向右子樹(shù)
    if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
    //子樹(shù)值小于根節(jié)點(diǎn)，不需要調(diào)整，退出循環(huán)
    if (arr[childMax] < arr[cur]) break;
    //子樹(shù)值大于根節(jié)點(diǎn)，需要調(diào)整，先交換根節(jié)點(diǎn)和子節(jié)點(diǎn)
    swap(arr, childMax, cur);
    cur = childMax; //根節(jié)點(diǎn)指針指向子節(jié)點(diǎn)，檢查子節(jié)點(diǎn)是否滿足大頂堆規(guī)則
    childMax = 2 * cur + 1; //子節(jié)點(diǎn)指針指向新的子節(jié)點(diǎn)
  }
}

步驟三：利用堆進(jìn)行排序

• 從后往前遍歷大頂堆（數(shù)組），交換堆頂元素a[0]和當(dāng)前元素a[i]的位置，將最大值依次放入數(shù)組末尾。

• 每交換一次，就要重新調(diào)整一下堆，從根節(jié)點(diǎn)開(kāi)始，調(diào)整根節(jié)點(diǎn)～i-1個(gè)節(jié)點(diǎn)（數(shù)組長(zhǎng)度為i），重新生成大頂堆
  
  

// 堆排序
function heapSort(arr) {
  if (arr.length <= 1) return arr;
  //構(gòu)建大頂堆
  buildHeap(arr);
  //從后往前遍歷，
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, i, 0); //交換最后位置和第一個(gè)位置（堆頂最大值）的位置
    headAdjust(arr, 0, i); //調(diào)整根節(jié)點(diǎn)～i-1個(gè)節(jié)點(diǎn)，重新生成大頂堆
  }
  return arr;
}

完整代碼：

// 交換數(shù)組元素
function swap(a, i, j) {
  [a[i], a[j]] = [a[j], a[i]];
}
//從輸入節(jié)點(diǎn)處調(diào)整堆
function headAdjust(arr, cur, len) {
  let intialCur = arr[cur]; //存放最初始的
  let childMax = 2 * cur + 1; //指向子樹(shù)中較大的位置，初始值為左子樹(shù)的索引

  //子樹(shù)存在（索引沒(méi)超過(guò)數(shù)組長(zhǎng)度）而且子樹(shù)值大于根時(shí)，此時(shí)不符合大頂堆結(jié)構(gòu)，進(jìn)入循環(huán)，調(diào)整堆的結(jié)構(gòu)
  while (childMax < len) {
    //判斷左右子樹(shù)大小,如果右子樹(shù)更大，而且右子樹(shù)存在，childMax指針指向右子樹(shù)
    if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
    //子樹(shù)值小于根節(jié)點(diǎn)，不需要調(diào)整，退出循環(huán)
    if (arr[childMax] < arr[cur]) break;
    //子樹(shù)值大于根節(jié)點(diǎn)，需要調(diào)整，先交換根節(jié)點(diǎn)和子節(jié)點(diǎn)
    swap(arr, childMax, cur);
    cur = childMax; //根節(jié)點(diǎn)指針指向子節(jié)點(diǎn)，檢查子節(jié)點(diǎn)是否滿足大頂堆規(guī)則
    childMax = 2 * cur + 1; //子節(jié)點(diǎn)指針指向新的子節(jié)點(diǎn)
  }
}
// 建立大頂堆
function buildHeap(arr) {
  //從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，向前遍歷，
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    headAdjust(arr, i, arr.length); //對(duì)每一個(gè)節(jié)點(diǎn)都調(diào)整堆，使其滿足大頂堆規(guī)則
  }
}
// 堆排序
function heapSort(arr) {
  if (arr.length <= 1) return arr;
  //構(gòu)建大頂堆
  buildHeap(arr);
  //從后往前遍歷，
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, i, 0); //交換最后位置和第一個(gè)位置（堆頂最大值）的位置
    headAdjust(arr, 0, i); //調(diào)整根節(jié)點(diǎn)～i-1個(gè)節(jié)點(diǎn)，重新生成大頂堆
  }
  return arr;
}

以上是“編程技術(shù)中冒泡排序、快速排序和堆排序的時(shí)間復(fù)雜度是多少”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！