基本思想：
在要排序的一組數中，對目前還未排好序的範圍内的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就将它們互換。
冒泡排序的示例：
算法的實作：
public void bubbleSort(int[] a) {
for(int i = a.length - 1; i > 0; i--) {
for(int j = 0; j < i; j++) {
if(a[j] > a[j+1])
//交換，具體實作略
swap(a, j, j+1);
}
}
} 算法優化(一)：設定是否交換的标志exchange
我們可以假設一種場景，比如 8 1 2 3 5 7，進行一次排序之後，結果就變成了 1 2 3 5 7 8，那我們還有必要再像上面代碼裡那樣繼續循環下去嗎？肯定沒有必要了，因為這已經是最終結果了。
那針對上面的代碼，我們優化的點主要在于：假如某一趟排序之後已經有序，我們需要減少排序的趟數。否則就做了很多無用功。
針對這個問題，我們可以考慮在算法中加入一個 變量，來辨別該輪有沒有進行資料的交換，若在某一趟排序中未發現資料位置的交換，則說明待排序的無序區中所有的項均已滿足排序後的結果。那麼就沒有必要再次排序下去了。可以如下改造：
#include"stdio.h"
#include <string.h>
int bubbleSort(int a[], int num)
{
int exchange;
int n = 0; //用來表示一共進行了多少次外層排序
int i, j;
int swap;
for(i = num - 1; i > 0; i--)
{
exchange = 0;
for(j = 0; j < i; j++)
{
if(a[j] > a[j+1]) {
swap = a[j];
a[j] = a[j+1];
a[j+1] = swap;
exchange = 1;
}
}
++n;
if(!exchange)
return n;
}
return n;
}
int main()
{
int b[] = {3, 2, 1, 4, 5};
printf(" %d ,%d \n", sizeof(b)/sizeof(int), bubbleSort(b, 5));
return 0;
} 算法優化(二)：設定最後一次交換的位置
這種方式可以獲得最好情況，即已經排号序了，第一次就可以結束
設定一标志性變量pos,用于記錄每趟排序中最後一次進行交換的位置。由于pos位置之後的記錄均已交換到位,故在進行下一趟排序時隻要掃描到pos位置即可。
改進後算法如下:
#include <stdio.h>
#include <iostream>
using namespace std;
void print(int a[],int i)
{
cout<<i <<" : ";
for(int j= 0; j<10; j++)
{
cout<<a[j] <<" ";
}
cout<<endl;
}
void Bubble_2( int r[], int n) {
int i= n -1, j; //初始時,最後位置保持不變
int tmp;
while ( i > 0)
{
int pos= 0; //每趟開始時,無記錄交換
for (j = 0; j < i; j++)
{
if (r[j] > r[j+1]) {
pos = j; //記錄交換的位置
tmp = r[j];
r[j] = r[j+1];
r[j+1] = tmp;
}
}
i = pos; //為下一趟排序作準備
print(r, i);
}
}
int main()
{
int H[10] = {3,1,5,7,2,4,9,6,10,8};
Bubble_2(H,10);
return 0;
} 運作結果：
8 : 1 3 5 2 4 7 6 9 8 10
7 : 1 3 2 4 5 6 7 8 9 10
1 : 1 2 3 4 5 6 7 8 9 10
0 : 1 2 3 4 5 6 7 8 9 10 算法優化(三)：同時交換最大值和最小值
傳統冒泡排序中每一趟排序操作隻能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 進而使排序趟數幾乎減少了一半。
#include <stdio.h>
#include <iostream>
using namespace std;
void print(int a[],int i)
{
cout<<i <<" : ";
for(int j= 0; j<10; j++)
{
cout<<a[j] <<" ";
}
cout<<endl;
}
void Bubble_2 ( int r[], int n){
int low = 0;
int high= n -1; //設定變量的初始值
int tmp,j;
while (low < high)
{
for (j= low; j< high; ++j) //正向冒泡,找到最大者
{
if (r[j] > r[j+1]) {
tmp = r[j];
r[j] = r[j+1];
r[j+1] = tmp;
}
}
--high; //修改high值, 前移一位
for (j = high; j>low; --j) //反向冒泡,找到最小者
{
if (r[j] < r[j-1]) {
tmp = r[j];
r[j] = r[j-1];
r[j-1] = tmp;
}
}
++low; //修改low值,後移一位
print(r, low);
}
}
int main()
{
int H[10] = {3,1,5,7,2,4,9,6,10,8};
Bubble_2(H,10);
return 0;
} 1 : 1 2 3 5 4 6 7 8 9 10
2 : 1 2 3 4 5 6 7 8 9 10
3 : 1 2 3 4 5 6 7 8 9 10
4 : 1 2 3 4 5 6 7 8 9 10
5 : 1 2 3 4 5 6 7 8 9 10