本專欄內(nèi)容為：八大排序匯總 通過本專欄的深入學(xué)習(xí)，你可以了解并掌握八大排序以及相關(guān)的排序算法。

💓博主csdn個(gè)人主頁(yè)：小小unicorn
?專欄分類：八大排序匯總
🚚代碼倉(cāng)庫(kù)：小小unicorn的代碼倉(cāng)庫(kù)🚚
🌹🌹🌹關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)

無論你學(xué)習(xí)哪種編程語言，在學(xué)到循環(huán)和數(shù)組時(shí)，通常都會(huì)介紹一種排序算法來作為例子，而這個(gè)算法一般就是冒泡排序。并不是它的名稱很好聽，而是說這個(gè)算法的思路最簡(jiǎn)單，最容易理解。因此，哪怕大家可能都已經(jīng)學(xué)過冒泡排序了，我們還是從這個(gè)算法開始我們的排序之旅。

最簡(jiǎn)單排序的實(shí)現(xiàn)

冒泡排序(Bubble Sort)是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。

冒泡的實(shí)現(xiàn)在細(xì)節(jié)上可以有很多種變化，我們將分別就3種不同的冒泡實(shí)現(xiàn)代碼，來講解冒泡排序的思想。這里，我們就先來看看比較容易理解的一段。

注意：排序用到的結(jié)構(gòu)與函數(shù)在第一部分：排序的基本概念與分類。我們已經(jīng)實(shí)現(xiàn)。詳情請(qǐng)點(diǎn)擊：八大排序（一）--------排序的基本概念與分類

//對(duì)順序表L作交換排序（冒泡排序初級(jí)版本）
void BubbleSort0(SqList* L)
{int i = 0, j = 0;for (i = 1; i < L->length; i++){for (j = i+1; j <= L->length; j++){if (L ->r[i] > L->r[j]){swap(L, i, j);   //交換L->r[i]與r->[j]}}}
}

這段代碼嚴(yán)格意義上說，不算是標(biāo)準(zhǔn)的冒泡排序算法，因?yàn)樗粷M足“兩兩比較相鄰記錄”的冒泡排序思想，它更應(yīng)該是最簡(jiǎn)單的交換排序而已。它的思路就是讓每一個(gè)關(guān)鍵字，都和它后面的每一個(gè)關(guān)鍵字比較，如果大則交換，這樣第一位置的關(guān)鍵字在一次循環(huán)后一定變成最小值。

如下圖所示，假設(shè)我們待排序的關(guān)鍵字序列是{9,1,5,8,3,7,4,6,2}
當(dāng)i=1時(shí)，9與1交換后，在第一位置的1與后面的關(guān)鍵字比較都小，因此它就是最小值。

當(dāng)i=2時(shí)，第二位置先后由9換成5，換成3，換成2，完成了第二小的數(shù)字交換。后面的數(shù)字變換類似，這里不再介紹。

這應(yīng)該算是最容易寫出的排序代碼了，不過這個(gè)簡(jiǎn)單易懂的代碼，卻是有缺陷的。觀察后發(fā)現(xiàn)，在排序好1和2的位置后，對(duì)其余關(guān)鍵字的排序沒有什么幫助(數(shù)字3反而還被換到了最后一位)。也就是說，這個(gè)算法的效率是非常低的。

冒泡排序算法

我們來看看正宗的冒泡算法，有沒有什么改進(jìn)的地方。

//對(duì)順序表L作冒泡排序
void BubbleSort(SqList* L)
{int i = 0, j = 0;for (i = 1; i < L->length; i++){for (j = L->length-1; j >= i; j--)    //j從后往前循環(huán){if (L->r[i] > L->r[j+1])          //若前者大于后者{swap(L, i, j+1);   //交換L->r[i]與r->[j+1]的值}}}
}

依然假設(shè)我們待排序的關(guān)鍵字序列是{9,1,5,8,3,7,4,6,2}

當(dāng)i=1時(shí)，變量j由8反向循環(huán)到1，逐個(gè)比較，將較小值交換到前面，直到最后找到最小值放置在了第1的位置。

如下圖所示，當(dāng)i=1,j=8時(shí)，我們發(fā)現(xiàn)6＞2，因此交換了它們的位置，j=7時(shí)，4>2，所以交換……直到=2時(shí)，因?yàn)?<2，所以不交換。j=1時(shí)，9＞1，交換，最終得到最小值1放置第1的位置。

事實(shí)上，在不斷循環(huán)的過程中，除了將關(guān)鍵字1放到第1的位置，我們還將關(guān)鍵字2從第9位置提到了第3的位置，顯然這一算法比前面的要有進(jìn)步，在上十萬條數(shù)據(jù)的排序過程中，這種差異會(huì)體現(xiàn)出來。圖中較小的數(shù)字如同氣泡般慢慢浮到上面，因此就將此算法命名為冒泡算法。

后面的數(shù)字變換就很簡(jiǎn)單，這里就不在敘述了。

冒泡排序優(yōu)化

這樣的冒泡程序是否還可以優(yōu)化呢？答案是肯定的。試想一下，如果我們待排序的序列是{2,1,3,4,5,6,7,8,9}也就是說，除了第1和第2的關(guān)鍵字需要交換外，別的都已經(jīng)是正常的順序。

當(dāng)i=1時(shí)，交換了2和1，此時(shí)序列已經(jīng)有序，但是算法仍然不依不饒地將i=2～9以及每個(gè)循環(huán)中的循環(huán)都執(zhí)行了一遍，盡管并沒有交換數(shù)據(jù)，但是之后的大量比較還是大大地多余了，如下圖所示。

當(dāng)i=2時(shí)，我們已經(jīng)對(duì)9與8，8與7，…，3與2作了比較，沒有任何數(shù)據(jù)交換，這就說明此序列已經(jīng)有序，不需要再繼續(xù)后面的循環(huán)判斷工作了。為了實(shí)現(xiàn)這個(gè)想法，我們需要改進(jìn)一下代碼，增加一個(gè)標(biāo)記變量flag來實(shí)現(xiàn)這一算法的改進(jìn)。

//對(duì)順序表L作冒泡排序（改進(jìn)版本）
void BubbleSort(SqList* L)
{int i = 0, j = 0;status flag = 1;                          //用flag進(jìn)行標(biāo)記for (i = 1; i < L->length && flag; i++)   //若flag為1則有效數(shù)據(jù)交換{flag = 0;for (j = L->length-1; j >= i; j--)    //j從后往前循環(huán){if (L->r[i] > L->r[j+1])          //若前者大于后者{swap(L, i, j+1);              //交換L->r[i]與r->[j+1]的值flag = 1;                     //如果有數(shù)據(jù)交換，則flag為1}}}
}

代碼改動(dòng)的關(guān)鍵就是在變量的for循環(huán)中，增加了對(duì)flag是否為1的判斷。

經(jīng)過這樣的改進(jìn)，冒泡排序在性能上就有了一些提升，可以避免已經(jīng)有序的情況下的無意義循環(huán)判斷。

冒泡排序復(fù)雜度分析

分析一下它的時(shí)間復(fù)雜度。

當(dāng)最好的情況，也就是要排序的表本身就是有序的，那么我們比較次數(shù)，根據(jù)最后改進(jìn)的代碼，可以推斷出就是n-1次的比較，沒有數(shù)據(jù)交換，時(shí)間復(fù)雜度為O(n)。

當(dāng)最壞的情況，即待排序表是逆序的情況，此時(shí)需要比較之${\sum }_{i=2}^n(i?1)=1+2+3+\dots +(n?1)=n(n?1)/2$次，并作等數(shù)量級(jí)的記錄移動(dòng)。因此，總的時(shí)間復(fù)雜度為O(n2)。