基本思想：
將n個記錄看作按縱向排列，在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換，整個排序過程共進(jìn)行n-1趟。如下所示：
初態(tài) 第1趟 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟
49 38 38 38 38 13 13 13
38 49 49 49 13 27 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 76
49 97
算法的實(shí)現(xiàn)：
// 輸出數(shù)組內(nèi)容
void print(int array[], int length, int i) {
printf("i=%d:",i);
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 冒泡排序（Bubble Sort）
void bubbleSort(int array[], int length) {
if(NULL == array || 0 == length) {
return;
}
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
print(array, length, i); // 打印每趟排序的結(jié)果
}
return;
}
int main(int argc, const char * argv[]) {
int arrayBubbleSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
bubbleSort(arrayBubbleSort, 8);
printf("\n");
return 0;
}
冒泡排序算法的改進(jìn)
對冒泡排序常見的改進(jìn)方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換，如果進(jìn)行某一趟排序時并沒有進(jìn)行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過程。本文再提供以下兩種改進(jìn)算法：
1、設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時只要掃描到pos位置即可。
改進(jìn)后算法如下:
// 冒泡排序改進(jìn)1（Bubble Sort）
void bubbleSort1(int array[], int length) {
int i = length - 1; // 初始時，最后位置保持不變
while (i > 0) {
int pos = 0; // 每趟開始時，無記錄交換
for (int j = 0; j < i; j ++) {
if (array[j] > array[j+1]) {
pos = j; // 記錄交換的位置
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
print(array, length, i); // 打印每趟排序的結(jié)果
i = pos; // 為下一趟排序作準(zhǔn)備
}
}
2、傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。
改進(jìn)后算法如下:
// 冒泡排序改進(jìn)2（Bubble Sort）
void bubbleSort2(int array[], int length) {
int low = 0;
int high = length - 1; // 設(shè)置變量的初始值
int temp,j;
while (low < high) {
for (j = low; j < high; j ++) { // 正向冒泡，找到最大值
if (array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
--high; // 修改high值，前移一位
for (j = high; j > low; j --) { // 反射冒泡，找到最小值
if (array[j] < array[j-1]) {
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
++low; // 修改low值，后移一位
}
}
總結(jié)
冒泡排序畢竟是一種效率低下的排序方法，在數(shù)據(jù)規(guī)模很小時，可以采用。數(shù)據(jù)規(guī)模比較大時，最好用其它排序方法。
