本文關(guān)鍵詞：冒泡排序算法，由筆耕文化傳播整理發(fā)布。

冒泡排序算法

一、基本思想

依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

第1趟：

　　首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。

第2趟：

　　仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。

如此下去，重復(fù)以上過程，直至最終完成排序。

由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升，所以稱作冒泡排序。 二、排序過程

需要排序的數(shù)列：49 38 65 97 76 13 27

排序過程：

38 49 65 76 13 27 97

38 49 65 13 27 76 97

38 49 13 27 65 76 97

38 13 27 49 65 76 97

13 27 38 49 65 76 97

13 27 38 49 65 76 97

13 27 38 49 65 76 97 三、代碼示例

冒泡排序

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

四、算法改進(jìn)

1、設(shè)置標(biāo)志位表明數(shù)列已排好序

　　假設(shè)需用冒泡排序?qū)?、5、7、1、2、3這6個(gè)數(shù)排序。在該列中，第三趟排序結(jié)束后，數(shù)組已排好序，但計(jì)算機(jī)此時(shí)并不知道，因此還需要進(jìn)行一趟比較。如果這一趟比較中未發(fā)生任何數(shù)據(jù)交換，則計(jì)算機(jī)知道已排序好，可以不再進(jìn)行比較了。因而第四趟比較需要進(jìn)行，但第五趟比較則是不必要的。為此，我們可以考慮程序的優(yōu)化。

　　為了標(biāo)志是否需要繼續(xù)比較，聲明一個(gè)布爾量flag，在進(jìn)行每趟比較前將flag置true。如果在比較中發(fā)生了數(shù)據(jù)交換，則將flag置為false，，在一趟比較結(jié)束后，再判斷flag，如果它仍為true（表明在該趟比較中未發(fā)生一次數(shù)據(jù)交換）則結(jié)束排序，否則進(jìn)行下一趟比較。

2、雙向冒泡排序

　　又叫雞尾酒排序算法，和冒泡排序的“編程復(fù)雜度”一樣，但對(duì)隨機(jī)序列排序性能稍高于普通冒泡排序，但是因?yàn)槭请p向冒泡，每次循環(huán)都雙向檢查，極端環(huán)境下會(huì)出現(xiàn)額外的比較，導(dǎo)致算法性能的退化，比如“4、5、7、1、2、3”這個(gè)序列就會(huì)出現(xiàn)退化

代碼如下：

雙向冒泡排序

五、算法分析

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

若記錄序列的初始狀態(tài)為"正序"，則冒泡排序過程只需進(jìn)行一趟排序，在排序過程中只需進(jìn)行n-1次交換，且不移動(dòng)記錄；反之，若記錄序列的初始狀態(tài)為"逆序"，則需進(jìn)行n(n-1)/2次比較和記錄移動(dòng)。因此冒泡排序總的時(shí)間復(fù)雜度為O(n*n)（即n的平方）。

2、空間復(fù)雜度

在冒泡排序的過程中，設(shè)置一個(gè)變量用來交換元素，所以空間復(fù)雜度為O(1)

3、排序穩(wěn)定性

冒泡排序是穩(wěn)定的

posted on

  本文關(guān)鍵詞：冒泡排序算法，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：50946