冒泡排序（Bubble Sort）算法是所有排序算法中最簡單驻呐、最基本的一種唠粥。冒泡排序算法的思路就是交換排序蒜焊，通過相鄰數(shù)據(jù)的交換來達(dá)到排序的目的。
冒泡排序算法?
冒泡排序算法通過多次比較和交換來實現(xiàn)排序照棋，其排序流程如下：
⑴對數(shù)組中的各數(shù)據(jù)资溃，依次比較相鄰的兩個元素的大小。
⑵如果前面的數(shù)據(jù)大于后面的數(shù)據(jù)必怜，就交換這兩個數(shù)據(jù)肉拓。經(jīng)過第一輪的多次比較排序后，便可將最小的數(shù)據(jù)排好梳庆。
⑶再用同樣的方法把剩下的數(shù)據(jù)逐個進(jìn)行比較暖途，最后便可按照從小到大的順序排好數(shù)組各數(shù)據(jù)。
為了更好地理解冒泡排序算法的執(zhí)行過程膏执，下面舉一個實際數(shù)據(jù)的例子一步一步地執(zhí)行冒泡排序算法驻售。對于5個整型數(shù)據(jù)118、101更米、105欺栗、127、112征峦，這是一組無序的數(shù)據(jù)迟几。對于執(zhí)行冒泡排序過程，如圖1所示栏笆。
冒泡排序算法的執(zhí)行步驟如下：
⑴第一次排序类腮，從數(shù)組的尾部開始向前依次比較。首先是127和112比較蛉加，由于127大于112蚜枢，因此將數(shù)據(jù)112向上移了一位缸逃；同理118和101比較，將數(shù)據(jù)101向前移了一位厂抽。此時排序后的數(shù)據(jù)為101需频、118、105筷凤、112窥岩、127恩尾。
⑵第二次排序憋肖，從數(shù)組的尾部開始向前依次比較官疲。105和118比較鞠鲜，可以將數(shù)據(jù)105向前移一位难菌。此時排序后的數(shù)據(jù)為101珠移、105的畴、118硫眨、112足淆、127。
⑶第三次排序礁阁，從數(shù)組的尾部開始向前依次比較巧号。由于112和118比較，可以將數(shù)據(jù)118向前移一位姥闭。此時排序后的數(shù)據(jù)為101丹鸿、105、112棚品、118靠欢、127。
⑷第四次排序時铜跑，此時门怪，各個數(shù)據(jù)已經(jīng)按順序排列好，所以無須再進(jìn)行數(shù)據(jù)交換锅纺。此時掷空，排序的結(jié)果為101、105囤锉、112坦弟、118、127官地。
從上面的例子可以非常直觀地了解到冒泡排序算法的執(zhí)行過程酿傍。整個排序過程就像水泡的浮起過程，故因此而得名区丑。冒泡排序算法在對n個數(shù)據(jù)進(jìn)行排序時拧粪，無論原數(shù)據(jù)有無順序修陡，都需要進(jìn)行n-1步的中間排序。這種排序方法思路簡單直觀可霎，但是缺點是執(zhí)行的步驟稍長魄鸦，效率不高。
一種改進(jìn)的方法癣朗，即在每次中間排序之后拾因，比較一下數(shù)據(jù)是否已經(jīng)按照順序排列完成。如果排列完成則退出排序過程旷余，否則便繼續(xù)進(jìn)行冒泡排序绢记。這樣，對于數(shù)據(jù)比較有規(guī)則的正卧，可以加速算法的執(zhí)行過程蠢熄。
冒泡排序算法的示例代碼如下：
void bubbleSort(int[] a) {
int temp;
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < a.length - 1; j++) {
if(a[j]>a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
System.out.print("第" + i + "步排序結(jié)果:");
for (int k = 0; k < a.length; k++) {
System.out.print(" " + a[k]);
}
System.out.print("\n");
}
}
在上訴代碼中，輸入?yún)?shù)a一般為一個數(shù)組的首地址炉旷。待排序的原數(shù)據(jù)便保存在數(shù)組a中签孔，程序中通過兩層循環(huán)來對數(shù)據(jù)進(jìn)行冒泡排序。結(jié)合前面的冒泡排序算法加深理解窘行。為了清除排序算法的執(zhí)行過程饥追，在排序的每一步都輸出了當(dāng)前的排序結(jié)果。
冒泡排序算法實例
學(xué)習(xí)了前面的冒泡排序算法的基本思想和算法之后罐盔。下面通過一個完整的例子說明冒泡排序法在整型數(shù)組排序中的應(yīng)用但绕，程序示例如下：
【程序】
public class Bubble_Sort {
static final int SIZE = 10;
public static void bubbleSort(int[] a) {
int temp;
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {// 將相鄰兩個數(shù)進(jìn)行比較，較大的數(shù)往后冒泡
// 交換相鄰兩個數(shù)
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
System.out.print("第" + i + "步排序結(jié)果:");
for (int k = 0; k < a.length; k++) {
System.out.print(" " + a[k]);
}
System.out.print("\n");
}
}
public static void main(String[] args) {
int[] shuzu = new int[SIZE];
int i;
for (i = 0; i < SIZE; i++) {
shuzu[i] = (int) (100 + Math.random() * (100 + 1));
}
System.out.print("排序前的數(shù)組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
bubbleSort(shuzu);
System.out.print("排序后的數(shù)組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
}
}
在上訴代碼中惶看，程序定義了符號常量SIZE捏顺，用于表征需要排序整型數(shù)組的大小。在主方法中碳竟，首先聲明一個整型數(shù)組草丧，然后對數(shù)組進(jìn)行隨機(jī)初始化，并輸出排序前的數(shù)組內(nèi)容莹桅。接著昌执，調(diào)用冒泡排序算法的方法來對數(shù)組進(jìn)行排序。最后诈泼，輸出排序后的數(shù)組懂拾。
該程序的執(zhí)行結(jié)果，如圖2所示铐达。圖中顯示了每一步排序的中間結(jié)果岖赋。從中可以看出從第7步之后便已經(jīng)完成對數(shù)據(jù)的排序，但是算法仍然需要進(jìn)行后續(xù)的比較步驟瓮孙。我們可以根據(jù)前面介紹的思路唐断，加入判斷部分选脊，使之能夠盡早結(jié)束排序過程，從而提高程序的執(zhí)行效率脸甘。
? ??????????????????????????????????????????????????????????????????????????????????????????????????-------《Java常用算法手冊》
