這篇文章主要介紹編程技術(shù)中冒泡排序、快速排序和堆排序的時(shí)間復(fù)雜度是多少，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！
目前成都創(chuàng)新互聯(lián)公司已為千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、石林網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
冒泡排序的時(shí)間復(fù)雜度：最好情況是“O(n)”，最壞情況是“O(n2)”。快速排序的的時(shí)間復(fù)雜度：最好情況是“O(nlogn)”，最壞情況是“O(n2)”。堆排序的時(shí)間復(fù)雜度是“O(nlogn)”。
本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。
時(shí)間復(fù)雜度
最好的情況：數(shù)組本身是順序的，外層循環(huán)遍歷一次就完成O(n)
最壞的情況：數(shù)組本身是逆序的，內(nèi)外層遍歷O(n2)
空間復(fù)雜度
開辟一個(gè)空間交換順序O(1)
穩(wěn)定性穩(wěn)定，因?yàn)閕f判斷不成立，就不會(huì)交換順序，不會(huì)交換相同元素
冒泡排序它在所有排序算法中最簡(jiǎn)單。然而， 從運(yùn)行時(shí)間的角度來看，冒泡排序是最差的一個(gè)，它的復(fù)雜度是O(n2)。
冒泡排序比較任何兩個(gè)相鄰的項(xiàng)，如果第一個(gè)比第二個(gè)大，則交換它們。元素項(xiàng)向上移動(dòng)至正確的順序，就好像氣泡升至表面一樣，冒泡排序因此得名。
交換時(shí)，我們用一個(gè)中間值來存儲(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)過多少輪排序
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ù)雜度
快速排序是遞歸的，需要借助棧來保存每一層遞歸的調(diào)用信息，所以空間復(fù)雜度和遞歸樹的深度一致
最好的情況：每一次base值都剛好平分整個(gè)數(shù)組，遞歸樹的深度O(logn)
最壞的情況：每一次base值都是數(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è)過程，直到左指針遇見了右指針。這個(gè)過程將使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。這一步叫作劃分操作。
(3)然后交換主元和指針停下來的位置的元素（等于說是把這個(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)總是取序列開頭的元素
// 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= 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è)完全二叉樹。
完全二叉樹： 二叉樹除開最后一層，其他層結(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ù)組來實(shí)現(xiàn)，相當(dāng)于對(duì)二叉樹做層序遍歷。如下圖：
時(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)的路徑是從樹的根節(jié)點(diǎn)到葉子結(jié)點(diǎn)，也就是樹的高度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)。
步驟一：建堆
以升序遍歷為例子，需要先將將初始二叉樹轉(zhuǎn)換成大頂堆，要求滿足：樹中任一非葉子結(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)開始，向前遍歷，
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)位置，直到沒有左節(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，
大于的話，說明滿足大頂堆規(guī)律，不需要再調(diào)整，跳出循環(huán)，結(jié)束遍歷
小于的話，說明不滿足大頂堆規(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ù)組長(zhǎng)度）而且子樹值大于根時(shí)，此時(shí)不符合大頂堆結(jié)構(gòu)，進(jìn)入循環(huán)，調(diào)整堆的結(jié)構(gòu)
while (childMax < len) {
//判斷左右子樹大小,如果右子樹更大，而且右子樹存在，childMax指針指向右子樹
if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
//子樹值小于根節(jié)點(diǎn)，不需要調(diào)整，退出循環(huán)
if (arr[childMax] < arr[cur]) break;
//子樹值大于根節(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)開始，調(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ù)組長(zhǎng)度）而且子樹值大于根時(shí)，此時(shí)不符合大頂堆結(jié)構(gòu)，進(jìn)入循環(huán)，調(diào)整堆的結(jié)構(gòu)
while (childMax < len) {
//判斷左右子樹大小,如果右子樹更大，而且右子樹存在，childMax指針指向右子樹
if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
//子樹值小于根節(jié)點(diǎn)，不需要調(diào)整，退出循環(huán)
if (arr[childMax] < arr[cur]) break;
//子樹值大于根節(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)開始，向前遍歷，
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)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
