基本思想：
將n個(gè)記錄看作按縱向排列叭莫，在要排序的一組數(shù)中蹈集，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整雇初，讓較大的數(shù)往下沉拢肆，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換郭怪，整個(gè)排序過程共進(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)
對(duì)冒泡排序常見的改進(jìn)方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換鄙才，如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換颂鸿，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序攒庵，避免不必要的比較過程嘴纺。本文再提供以下兩種改進(jìn)算法：
1、設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置浓冒。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可栽渴。
改進(jìn)后算法如下:
// 冒泡排序改進(jìn)1（Bubble Sort）
void bubbleSort1(int array[], int length) {
int i = length - 1; // 初始時(shí)，最后位置保持不變
while (i > 0) {
int pos = 0; // 每趟開始時(shí)稳懒，無記錄交換
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)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(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í)，可以采用装哆。數(shù)據(jù)規(guī)模比較大時(shí)罐脊，最好用其它排序方法。
