一文了解冒泡排序

要點(diǎn)

冒泡排序是一種交換排序。

什么是交換排序呢？

交換排序：兩兩比較待排序的關(guān)鍵字，并交換不滿足次序要求的那對(duì)數(shù)，直到整個(gè)表都滿足次序要求為止。

算法思想

它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。

這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

假設(shè)有一個(gè)大小為 N 的無(wú)序序列。冒泡排序就是要每趟排序過(guò)程中通過(guò)兩兩比較，找到第 i 個(gè)小（大）的元素，將其往上排。

以上圖為例，演示一下冒泡排序的實(shí)際流程：

假設(shè)有一個(gè)無(wú)序序列 { 4. 3. 1. 2, 5 }

第一趟排序：通過(guò)兩兩比較，找到第一小的數(shù)值 1 ，將其放在序列的第一位。

第二趟排序：通過(guò)兩兩比較，找到第二小的數(shù)值 2 ，將其放在序列的第二位。

第三趟排序：通過(guò)兩兩比較，找到第三小的數(shù)值 3 ，將其放在序列的第三位。

至此，所有元素已經(jīng)有序，排序結(jié)束。

要將以上流程轉(zhuǎn)化為代碼，我們需要像機(jī)器一樣去思考，不然編譯器可看不懂。

假設(shè)要對(duì)一個(gè)大小為 N 的無(wú)序序列進(jìn)行升序排序（即從小到大）。

(1) 每趟排序過(guò)程中需要通過(guò)比較找到第 i 個(gè)小的元素。

所以，我們需要一個(gè)外部循環(huán)，從數(shù)組首端(下標(biāo) 0) 開始，一直掃描到倒數(shù)第二個(gè)元素（即下標(biāo) N - 2) ，剩下最后一個(gè)元素，必然為最大。

(2) 假設(shè)是第 i 趟排序，可知，前 i-1 個(gè)元素已經(jīng)有序?，F(xiàn)在要找第 i 個(gè)元素，只需從數(shù)組末端開始，掃描到第 i 個(gè)元素，將它們兩兩比較即可。

所以，需要一個(gè)內(nèi)部循環(huán)，從數(shù)組末端開始（下標(biāo) N - 1），掃描到 (下標(biāo) i + 1)。

核心代碼

publicvoidbubbleSort(int[]list){

inttemp=0;// 用來(lái)交換的臨時(shí)數(shù)

// 要遍歷的次數(shù)

for(inti=0;i

// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上

for(intj=list.length-1;j>i;j--){

// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換

if(list[j-1]>list[j]){

temp=list[j-1];

list[j-1]=list[j];

list[j]=temp;

}

}

System.out.format("第 %d 趟： ",i);

printAll(list);

}

}

冒泡排序算法的性能

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

若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時(shí)間復(fù)雜度為O(N)。

若初始文件是反序的，需要進(jìn)行 N -1 趟排序。每趟排序要進(jìn)行 N - i 次關(guān)鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：

Cmax = N(N-1)/2 = O(N2)

Mmax = 3N(N-1)/2 = O(N2)

冒泡排序的最壞時(shí)間復(fù)雜度為O(N2)。

因此，冒泡排序的平均時(shí)間復(fù)雜度為O(N2)。

總結(jié)起來(lái)，其實(shí)就是一句話：當(dāng)數(shù)據(jù)越接近正序時(shí)，冒泡排序性能越好。

算法穩(wěn)定性

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。

所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

優(yōu)化

對(duì)冒泡排序常見的改進(jìn)方法是加入標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過(guò)程中是否有數(shù)據(jù)交換。

如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說(shuō)明所有數(shù)據(jù)已經(jīng)有序，可立即結(jié)束排序，避免不必要的比較過(guò)程。

核心代碼

// 對(duì) bubbleSort 的優(yōu)化算法

publicvoidbubbleSort_2(int[]list){

inttemp=0;// 用來(lái)交換的臨時(shí)數(shù)

booleanbChange=false;// 交換標(biāo)志

// 要遍歷的次數(shù)

for(inti=0;i

bChange=false;

// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上

for(intj=list.length-1;j>i;j--){

// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換

if(list[j-1]>list[j]){

temp=list[j-1];

list[j-1]=list[j];

list[j]=temp;

bChange=true;

}

}

// 如果標(biāo)志為false，說(shuō)明本輪遍歷沒有交換，已經(jīng)是有序數(shù)列，可以結(jié)束排序

if(false==bChange)

break;

System.out.format("第 %d 趟： ",i);

printAll(list);

}

}

完整參考代碼

packagenotes.javase.algorithm.sort;

importjava.util.Random;

publicclassBubbleSort{

publicvoidbubbleSort(int[]list){

inttemp=0;// 用來(lái)交換的臨時(shí)數(shù)

// 要遍歷的次數(shù)

for(inti=0;i

// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上

for(intj=list.length-1;j>i;j--){

// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換

if(list[j-1]>list[j]){

temp=list[j-1];

list[j-1]=list[j];

list[j]=temp;

}

}

System.out.format("第 %d 趟： ",i);

printAll(list);

}

}

// 對(duì) bubbleSort 的優(yōu)化算法

publicvoidbubbleSort_2(int[]list){

inttemp=0;// 用來(lái)交換的臨時(shí)數(shù)

booleanbChange=false;// 交換標(biāo)志

// 要遍歷的次數(shù)

for(inti=0;i

bChange=false;

// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上

for(intj=list.length-1;j>i;j--){

// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換

if(list[j-1]>list[j]){

temp=list[j-1];

list[j-1]=list[j];

list[j]=temp;

bChange=true;

}

}

// 如果標(biāo)志為false，說(shuō)明本輪遍歷沒有交換，已經(jīng)是有序數(shù)列，可以結(jié)束排序

if(false==bChange)

break;

System.out.format("第 %d 趟： ",i);

printAll(list);

}

}

// 打印完整序列

publicvoidprintAll(int[]list){

for(intvalue:list){

System.out.print(value+" ");

}

System.out.println();

}

publicstaticvoidmain(String[]args){

// 初始化一個(gè)隨機(jī)序列

finalintMAX_SIZE=10;

int[]array=newint[MAX_SIZE];

Randomrandom=newRandom();

for(inti=0;i

array[i]=random.nextInt(MAX_SIZE);

}

// 調(diào)用冒泡排序方法

BubbleSortbubble=newBubbleSort();

System.out.print("排序前: ");

bubble.printAll(array);

// bubble.bubbleSort(array);

bubble.bubbleSort_2(array);

System.out.print("排序后: ");

bubble.printAll(array);

}

}

運(yùn)行結(jié)果