冒泡排序、快速排序和堆排序的時間復(fù)雜度是多少

冒泡排序的時間復(fù)雜度：最好情況是“O(n)”，最壞情況是“O(n2)”。快速排序的的時間復(fù)雜度：最好情況是“O(nlogn)”，最壞情況是“O(n2)”。堆排序的時間復(fù)雜度是“O(nlogn)”。

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

冒泡排序（Bubble Sort）

時間復(fù)雜度

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

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

空間復(fù)雜度
開辟一個空間交換順序O(1)
穩(wěn)定性
穩(wěn)定，因為if判斷不成立，就不會交換順序，不會交換相同元素

• 冒泡排序它在所有排序算法中最簡單。然而， 從運行時間的角度來看，冒泡排序是最差的一個，它的復(fù)雜度是O(n2)。

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

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

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

具體實現(xiàn)：

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

快速排序

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

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

穩(wěn)定性
快速排序是不穩(wěn)定的，因為可能會交換相同的關(guān)鍵字。
快速排序是遞歸的，
特殊情況：left>right,直接退出。

步驟：

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

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

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

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

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

left>i-1 / i+1>right

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

歸位示意圖：

具體實現(xiàn)：

function quicksort(arr, left, right) {   if (left > right) {     return;   }   var i = left,     j = right,     base = arr[left]; //基準總是取序列開頭的元素   //   var [base, i, j] = [arr[left], left, right]; //以left指針元素為base   while (i != j) {     //i=j，兩個指針相遇時，一次排序完成，跳出循環(huán)     // 因為每次大循環(huán)里面的操作都會改變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); //對base左邊的元素遞歸排序   quicksort(arr, i + 1, right); //對base右邊的元素遞歸排序   return arr; }

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

堆排序

堆的概念

• 堆是一個完全二叉樹。
• 完全二叉樹： 二叉樹除開最后一層，其他層結(jié)點數(shù)都達到最大，最后一層的所有結(jié)點都集中在左邊（左邊結(jié)點排列滿的情況下，右邊才能缺失結(jié)點）。
• 大頂堆：根結(jié)點為最大值，每個結(jié)點的值大于或等于其孩子結(jié)點的值。
• 小頂堆：根結(jié)點為最小值，每個結(jié)點的值小于或等于其孩子結(jié)點的值。
• 堆的存儲： 堆由數(shù)組來實現(xiàn)，相當(dāng)于對二叉樹做層序遍歷。如下圖：
  
  

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

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

穩(wěn)定性
堆排序是不穩(wěn)定的，因為可能會交換相同的子結(jié)點。

步驟一：建堆

• 以升序遍歷為例子，需要先將將初始二叉樹轉(zhuǎn)換成大頂堆，要求滿足：樹中任一非葉子結(jié)點大于其左右孩子。
• 實質(zhì)上是調(diào)整數(shù)組元素的位置，不斷比較，做交換操作。
• 找到第一個非葉子結(jié)點——Math.floor(arr.length / 2 - 1)，從后往前依次遍歷
• 對每一個結(jié)點，檢查結(jié)點和子結(jié)點的大小關(guān)系，調(diào)整成大根堆

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

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

• 建立childMax指針指向child最大值節(jié)點，初始值為2 * cur + 1，指向左節(jié)點
• 當(dāng)左節(jié)點存在時（左節(jié)點索引小于數(shù)組length），進入循環(huán)，遞歸調(diào)整所有節(jié)點位置，直到沒有左節(jié)點為止（cur指向一個葉結(jié)點為止），跳出循環(huán)，遍歷結(jié)束
• 每次循環(huán)，先判斷右節(jié)點存在時，右節(jié)點是否大于左節(jié)點，是則改變childMax的指向
• 然后判斷cur根節(jié)點是否大于childMax，
• 大于的話，說明滿足大頂堆規(guī)律，不需要再調(diào)整，跳出循環(huán)，結(jié)束遍歷
• 小于的話，說明不滿足大頂堆規(guī)律，交換根節(jié)點和子結(jié)點，
• 因為交換了節(jié)點位置，子結(jié)點可能會不滿足大頂堆順序，所以還要判斷子結(jié)點然后，改變cur和childMax指向子結(jié)點，繼續(xù)循環(huán)判斷。

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

步驟三：利用堆進行排序

• 從后往前遍歷大頂堆（數(shù)組），交換堆頂元素a[0]和當(dāng)前元素a[i]的位置，將最大值依次放入數(shù)組末尾。
• 每交換一次，就要重新調(diào)整一下堆，從根節(jié)點開始，調(diào)整根節(jié)點～i-1個節(jié)點（數(shù)組長度為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); //交換最后位置和第一個位置（堆頂最大值）的位置     headAdjust(arr, 0, i); //調(diào)整根節(jié)點～i-1個節(jié)點，重新生成大頂堆   }   return arr; }

完整代碼：

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