發(fā)布時間：2016-05-28 08:03

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

冒泡排序算法

一、基本思想

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

第1趟：

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

第2趟：

　　仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。

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

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

需要排序的數(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 三、代碼示例

冒泡排序

運行結(jié)果：

四、算法改進

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

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

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

2、雙向冒泡排序

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

代碼如下：

雙向冒泡排序

五、算法分析

1、時間復雜度

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

2、空間復雜度

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

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

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

posted on

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

本文編號：50946