1.
參考資料：
1
）譚浩強
《
c
程序設計》
124
頁
2
）數據結構自考網（
very good
）
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm
?
2.
算法分析：
假如有以下數據：
5 2 4
3
；人是如何排序的呢？如果按從小到大排序，肯定是每次找出一個最小的數，直到排好序；(注：選擇排序就是這個思路，每次找出一個最小值放到合適位置；）類似，計算機實現也是這樣的，最簡單的冒泡排序方法就是如此，每次找出一個最大的值沉底，第一次
5
沉底，第二此
4
沉底，經過
N-1
次后排序完成。
?
3
．具體編碼實現時關鍵是要確定循環次數：
3.1
思路一：
外層循環：
n-1
次
（每次找出一個最大的）
內層循環：
n-i
次
：
外層
i=1,
內層需要
n-1
次兩兩比較才能找出最大值；
外層
i=2,
內層需要
n-2
次兩兩比較才能找出最大值；
……
歸納得到，內層循環需要
n-i
次
?
如此反復，直到排好序為止（若在某一趟冒泡過程中，沒有發現一個逆序，則可結束冒泡排序），所以
冒泡過程最多進行
n-1
趟。
?
代碼實現如下：
?1?void??BubbleSort(RecordType?r[],?int?length?)
?2?/*對記錄數組r做冒泡排序，length為數組的長度*/
?3?{
?4?n=length;????change=TRUE；
?5?for?(?i=1?;?i<=?n-1?&&?change?;++i?)?
?6?{
?7??????change=FALSE；
?8??for?(?j=1?;?j<=?n-i?;?++j)?
?9??if?(r[j].key>?r[j+1].key?)??
10?{
11????????????x=?r[j];
12????????????r[j]=?r[j+1];
13????????????r[j+1]=?x;
14?change=TRUE；
15??????}?
16?}
17?}?/*??BubbleSort??*/?
18?
代碼來自：
西北大學
數據結構
精品教程
交換類排序法
冒泡排序
?
http://jpkc.nwu.edu.cn/datastr/study_online/test_paper.htm
?
3.2
思路二：
以下內容來自：
數據結構自考網
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm
或者
http://www.wjzyzx.com/rjxy/sjjg/gailun/gailun1.3.2.htm
?
提示：注意有序區、無序區的這種思考方法。
冒泡排序
1
、排序方法
???
將被排序的記錄數組
R[1..n]
垂直排列，每個記錄
R[i]
看作是重量為
R[i].key
的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數
組
R
：凡掃描到違反本原則的輕氣泡，就使其向上
"
飄浮
"
。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。
（
1
）初始
???
R[1..n]
為無序區。
（
2
）第一趟掃描
???
從無序區底部向上依次比較相鄰的兩個氣泡的重量，若發現輕者在下、重者在上，則交換二者的位置。即依次比較
(R[n]
，
R[n-1])
，
(R[n-1]
，
R[n-2])
，
…
，
(R[2]
，
R[1])
；對于每對氣泡
(R[j+1]
，
R[j])
，若
R[j+1].key<R[j].key
，則交換
R[j +1]
和
R[j]
的內容。
???
第一趟掃描完畢時，
"
最輕
"
的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置
R[1]
上。
（
3
）第二趟掃描
???
掃描
R[2..n]
。掃描完畢時，
"
次輕
"
的氣泡飄浮到
R[2]
的位置上
……
???
最后，經過
n-1?
趟掃描可得到有序區
R[1..n]
?
注意：
???
第
i
趟掃描時，
R[1..i-1]
和
R[i..n]
分別為當前的有序區和無序區。掃描仍是從無序區底部向上直至該區頂部。掃描完畢時，該區中最輕氣泡飄浮到頂部位置
R[i]
上，結果是
R[1..i]
變為新的有序區。
2
、冒泡排序過程示例
???
對關鍵字序列為
49 38 65 97 76 13 27 49
的文件進行冒泡排序的過程
3
、排序算法
（
1
）分析
???
因為每一趟排序都使有序區增加了一個氣泡，在經過
n-1
趟排序之后，有序區中就有
n-1
個氣泡，而無序區中氣泡的重量總是大于等于有序區中氣泡的重量，所以整個冒泡排序過程至多需要進行
n-1
趟排序。
???
若在某一趟排序中未發現氣泡位置的交換，則說明待排序的無序區中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止。為
此，在下面給出的算法中，引入一個布爾量
exchange
，在每趟排序開始前，先將其置為
FALSE
。若排序過程中發生了交換，則將其置為
TRUE
。各趟
排序結束時檢查
exchange
，若未曾發生過交換則終止算法，不再進行下一趟排序。
（
2
）具體算法
? void BubbleSort(SeqList R)
?? { //R
（
l..n)
是待排序的文件，采用自下向上掃描，對
R
做冒泡排序
???? int i
，
j
；
???? Boolean exchange
；
//
交換標志
???? for(i=1;i<n;i++){ //
最多做
n-1
趟排序
?????? exchange=FALSE
；
//
本趟排序開始前，交換標志應為假
?????? for(j=n-1;j>=i
；
j--) ?//
對當前無序區
R[i..n]
自下向上掃描
??????? if(R[j+1].key<R[j].key){//
交換記錄
????????? R[0]=R[j+1]
；
//R[0]
不是哨兵，僅做暫存單元
????????? R[j+1]=R[j]
；
????????? R[j]=R[0]
；
????????? exchange=TRUE
；
//
發生了交換，故將交換標志置為真
???????? }
?????? if(!exchange) //
本趟排序未發生交換，提前終止算法
???????????? return
；
???? } //endfor(
外循環
)
??? } //BubbleSort
?
4.
算法分析
冒泡排序算法分析：最壞情況下，待排序記錄按關鍵字的逆序進行排列，此時，每一趟冒泡排序需進行i次比較，3i次移動。經過n-1趟冒泡排序后，總的比較次數為n(n-1)/2；總的移動次數為3
n(n-1)/2
次，因此該算法的時間復雜度為O(n2);空間復雜度為O(1)。另外，冒泡排序法是一種穩定的排序方法。
注：
1）
關鍵語句總執行次數的計算：
外層i=1:內層j=n-1;
i=2:j=n-2;
……；
所以，交換語句的總執行次數是（n-1）+(n-2)+(n-3)+…+1=n(n-1)/2;
2）
時間復雜度的概念：
一般情況下，算法中基本操作重復執行的次數是問題規模
n
的某個函數，用
T(n)
表示，若有某個輔助函數
f(n),
使得當
n
趨近于無窮大時，
T
（
n)/f (n)
的極限值為不等于零的常數，則稱
f(n)
是
T(n)
的同數量級函數。記作
T(n)=O(f(n)),
稱
O(f(n))
為算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同算法中，若算法中語句執行次數為一個常數，則時間復雜度為
O(1),
另外，在時間頻度不相同時，時間復雜度有可能相同，如
T(n)=n2+3n+4
與
T(n)=4n2+2n+1
它們的頻度不同，但時間復雜度相同，都為
O(n2)
。
3）
空間復雜度：
與時間復雜度類似，空間復雜度是指算法在計算機內執行時所需存儲空間的度量。記作
:
S(n)=O(f(n))
我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規模。
?
冒泡排序的O(1)表示只需要一個輔助的temp存儲單元來實現交換數據，所以空間復雜度為常量。
?
4
）平均時間復雜度：
設每種情況的出現的概率為
pi,
則為
sum(pi*f(n))
；
以下內容來自：
請教關于“平均時間復雜度
T(n)
”的推導
http://topic.csdn.net/t/20031209/21/2546177.html
問題：
?
? ? ?
今假設
a
中初始輸入數據可能出現
? n! ?
種的排列的概率相等，則
“
關鍵語句
”
的平均執行次數為多少？希望給出具體的推導過程！
?
?
（書上沒給出具體答案，只寫了平均時間復雜度
T(n) ? = ? O(n
平方
)
）
?
解答：
如果
a
中初始輸入數據可能出現
? n! ?
種的排列的概率相等
?
?
則
if( ?
a[j] ? > ? a[j+1] ? )
句成立的概率為
50%
，
?
?
故內層循環執行次數為
i/2
。
?
?
在不考慮
change
的影響是有
T(n)=(1+2+....+n-1)/(2*2)
? = ? (n-1)*n/4 ? = ? O(n^2)
?
5.
算法改進
???
上述的冒泡排序還可做如下的改進：
(1)
記住最后一次交換發生位置
lastExchange
的冒泡排序
在每趟掃描中，記住最后一次交換發生的位置
lastExchange
，（該位置之前的相鄰記錄均已有序）。下一趟排序開始時，
R[1.. lastExchange-1]
是有序區，
R[lastExchange..n]
是無序區。這樣，一趟排序可能使當前有序區擴充多個記錄，從而減少排序的
趟數。具體算法【參見習題】。
(2)
改變掃描方向的冒泡排序
?
①
冒泡排序的不對稱性
能一趟掃描完成排序的情況：
???
只有最輕的氣泡位于
R[n]
的位置，其余的氣泡均已排好序，那么也只需一趟掃描就可以完成排序。
【例】對初始關鍵字序列
12
，
18
，
42
，
44
，
45
，
67
，
94
，
10
就僅需一趟掃描。
需要
n-1
趟掃描完成排序情況：
???
當只有最重的氣泡位于
R[1]
的位置，其余的氣泡均已排好序時，則仍需做
n-1
趟掃描才能完成排序。
【例】對初始關鍵字序列：
94
，
10
，
12
，
18
，
42
，
44
，
45
，
67
就需七趟掃描。
?
②
造成不對稱性的原因
每趟掃描僅能使最重氣泡
"
下沉
"
一個位置，因此使位于頂端的最重氣泡下沉到底部時，需做
n-1
趟掃描。
?
③
改進不對稱性的方法
???
在排序過程中交替改變掃描方向，可改進不對稱性。
?
④
代碼實現如下：
代碼來源：
http://www.goc.ac.cn/liuag/html/algorithms_bibobblesort.html
?
??1?????????????????int
??2??????????????????data[10]={4,8,22,79,-2,0,100,13,12,-100};
??3?????????
??4?
??5?????????????????void
??6??????????????????Bubble_Sort2(int?a[],int?n);
??7?????????
??8?
??9?????????????????void
?10??????????????????Print(int?a[],int?n);
?11?????????
?12?
?13?????????????????main()
?14?????????
?15?
?16?????????????????{
?17?????????
?18?
?19?????????????????
?20???????????????????????????Print(data,10);
?21?????????
?22?
?23?????????????????
?24???????????????????????????Bubble_Sort2(data,10);
?25?????????
?26?
?27?????????????????
?28???????????????????????????Print(data,10);
?29?????????
?30?
?31?????????????????}
?32?????????
?33?
?34?????????????????void
?35??????????????????Print(int?a[],int?n)
?36?????????
?37?
?38?????????????????{
?39?????????
?40?
?41?????????????????
?42?????????????????????????????
?43?????????????????????????int?i;
?44?????????
?45?
?46?????????????????
?47?????????????????????????????
?48?????????????????????????for(i=0;i<n;++i)
?49?????????
?50?
?51?????????????????
?52??????????????????????????????printf("%4d",a[i]);
?53?????????
?54?
?55?????????????????
?56?????????????????????????????printf("\n");
?57?????????
?58?
?59?????????????????}
?60?????????
?61?
?62?????????????????void
?63??????????????????Bubble_Sort2(int?a[?],int?n)
?64?????????
?65?
?66?????????????????{
?67???
?71?????????????????????????int?low=0,high=n-1;
?72??
?76?????????????????????????int?change=1;
?77
?81?????????????????????????int?i,temp;
?82??? ?????????????????????????
?86?????????????????????????while(low<high&&change)
?87
?90???????????????????????????{
?91?
?94?????????????????????????????change=0;
?95????
?99?????????????????????????for(i=low;i<high;i++)
100???
104?????????????????????????if(a[i]>a[i+1])
105????
108???????????????????????????????{
109?????????
110?
113?????????????????????????/*?a[i]<->a[i+1];*/
114????
118?????????????????????????????????temp=a[i];
119????
122?????????????????????????????????a[i]=a[i+1];
123?????????
124?
125?????????????????
126?????????????????????????????????a[i+1]=temp;
127?????????
128?
129?????????????????
130?????????????????????????????????change=1;
131?????????
132?
133?????????????????
134???????????????????????????????}
135?????????
136?
137?????????????????
138?????????????????????????????high--;
139?????????
140?
141?????????????????
142?????????????????????????????
143?????????????????????????for(i=high;i>low;i--)
144?????????
145?
146?????????????????
147???????????????????????????????
148?????????????????????????if(a[i]<a[i-1])
149?????????
150?
151?????????????????
152???????????????????????????????{
153?????????
154?
155?????????????????
156?????????????????????????????????
157?????????????????????????/*?a[i]<->a[i-1];?*/
158?????????????????
159?????????
160?
161?????????????????
162?????????????????????????????????temp=a[i];
163?????????
164?
165?????????????????
166?????????????????????????????????a[i]=a[i-1];
167?????????
168?
169?????????????????
170?????????????????????????????????a[i-1]=temp;
171?????????
172?
173?????????????????
174?????????????????????????????????change=1;
175?????????
176?
177?????????????????
178???????????????????????????????}
179?????????
180?
181?????????????????
182?????????????????????????????low++;
183?????????
184?
185?????????????????
186???????????????????????????}//while
187?????????
188?
189?????????????????}//Bubble_Sort2
190?????????
⑤雙向冒泡排序真的比單向的快？
其實雙向冒泡并不一定比單向的快，只是在排序過程中交替改變掃描方向，可改進冒泡排序的不對稱性。
?
Ok
！
明天學習快速排序法！
Come on
！