104
排序算法係列之冒泡排序
交換排序的基本思想是：兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。應用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。
基本思想
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]變為新的有序區。
算法排序動畫演示
對關鍵字序列為xx,xx,xx,xx（需要自己輸入）進行冒泡排序的過程演示。
【動畫演示過程】
算法實現
1.方法一，按照定義實現的C程序
#include <stdio.h>
void bubbleSort(int arr[], int count)
{
int i = count, j;
int temp;
while(i > 0)
{
for(j = 0; j < i - 1; j++)
{
if(arr[j] > arr[j + 1])
{ temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i--;
}
}
算法性能分析
| 最差時間複雜度 |  |
|---|---|
| 最優時間複雜度 |  |
| 平均時間複雜度 | |
| 最差空間複雜度 | 總共，需要輔助空間
|
算法改進的三種方法
1.設置標誌的冒泡排序
#include <iostream>
using namespace std;
void bubble_sort(int d[], int size)
{
//#假定兩兩交換發生在數組最後的兩個位置#%
int exchange = size - 1;
while(exchange)
{
//#記錄下發生數據交換的位置#%
int bound = exchange;
exchange = 0; //#假定本趟比較沒有數據交換#%
for(int i = 0; i < bound; i++)
{
if (d[i] > d[i + 1])
{
//#交換#%
int t = d[i];
d[i] = d[i + 1];
d[i + 1] = t;
exchange = i;
}
}
}
}
2.記住最後一次交換發生位置的lastExchange冒泡排序
在每趟掃描中，記住最後一次交換發生的位置lastExchange，（該位置之前的相鄰記錄均已有序）。下一趟排序開始時，R[1..lastExchange-1]是有序區，R[lastExchange..n]是無序區。這樣，一趟排序可能使當前有序區擴充多個記錄，從而減少排序的趟數。程序如下：（from author
MoreWindows）
void BubbleSort(int a[], int n)
{
int j, k;
int flag;
flag = n;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
3.冒泡算法的不對稱性
（1）能一趟掃描完成排序的情況：
隻有最輕的氣泡位於R[n]的位置，其餘的氣泡均已排好序，那麼也隻需一趟掃描就可以完成排序。
【例】對初始關鍵字序列12，18，42，44，45，67，94，10就僅需一趟掃描。
需要n-1趟掃描完成排序情況：
當隻有最重的氣泡位於R[1]的位置，其餘的氣泡均已排好序時，則仍需做n-1趟掃描才能完成排序。
【例】對初始關鍵字序列：94，10，12，18，42，44，45，67就需七趟掃描。
（2）造成不對稱性的原因
每趟掃描僅能使最重氣泡"下沉"一個位置，因此使位於頂端的最重氣泡下沉到底部時，需做n-1趟掃描。
（3）改進不對稱性的方法
在排序過程中交替改變掃描方向，可改進不對稱性。
（4）采用交替掃描改進的冒泡算法實現：
（a）改變掃描方向, 改成從頂往底掃描, 則算法偽碼如下 ：
void BubbleSort( SeqList R)
{// R( l11n) 是待排序的文件, 采用自上向下掃描, 對R 做冒泡排序
int i,j;
Boolean exchange; // 交換標誌
for( i= n; i< 2; i- - )
{// 最多做n- 1 趟排序
exchange= FALSE; // 本趟排序開始前, 交換標誌應為假
for(j= 1;j< = i;j+ + ) // 掃描方向從頂到i
if( R[j+ 1] 1key< R[ j] 1key) { // 交換記錄
R[0] = R[j+1]; // R[ 0] 不是哨兵, 僅做暫存單元
R[j+1] = R[j];
R[j] = R[0];
exchange= TRUE; // 發生了交換, 故將交換標誌置為真
}
if( ! exchange) // 本趟排序未發生交換, 提前終止算法
return;
}// endfor( 外循環)
}// BubbleSort
這樣,R[ 1,i] 是無序區, R[ i+ 1,n] 是有序區。
（b）交替改變掃描方向
在排序過程中交替改變掃描方向, 即每趟掃描方向都進行改變, 就可以改變排序的不對稱問題。如第一趟是從底向上, 第二趟是從上向底的交替冒泡排序算法偽碼如下：
void BubbleSort( SeqList R)
{// R( l11n) 是待排序的文件, 采用先下向上掃描, 再從上向下的交替掃描, 對R 做冒泡排序
int i,j, k; // j 控製趟內掃描過程
Boolean exchange; // 交換標誌
i= 1; k= n; // i: 每趟掃描的起始位置; k: 每趟掃描的結束位置即無序區R[ i ,k]
while( i< k) {
exchange= FALSE; // 本趟排序開始前, 交換標誌應為假
for(j= k- 1; j> = i; j- - ) // 對當前無序區R[ i11k] 自下向上掃描
if( R[ j+ 1] 1key< R[j] 1key) {/ / 交換記錄
R[ 0] = R[ j+ 1] ; // R[ 0] 不是哨兵, 僅做暫存單元
R[j+ 1] = R[j] ;
R[j] = R[ 0] ;
exchange= TRUE; // 發生了交換, 故將交換標誌置為真
}
if( ! exchange) return; // 本趟排序未發生交換, 提前終止算法
for(j= i;j< = k- 1; j+ + ) // 對當前無序區R[ i11k] 自上向下掃描
if( R[j+ 1] 1key< R[ j] 1key) { // 交換記錄
R[ 0] = R[ j+ 1] ; // R[ 0] 不是哨兵, 僅做暫存單元
R[j+ 1] = R[j] ;
R[j] = R[ 0] ;
exchange= TRUE; // 發生了交換, 故將交換標誌置為真
}
if( ! exchange) return; // 本趟排序未發生交換, 提前終止算法
}// endfor( 外循環)
}/ BubbleSort
參考文獻：采用交替掃描改進冒泡排序的不對稱性（Improving the Asymmetry of Bubble Sort using Alternate Scanning）。
最後更新：2017-04-03 18:51:47