image

??冒泡排序法（Bubble Sort）是所有排序算法中最簡單、最基本的一種。冒泡排序法的思路就是交換排序，通過相鄰數(shù)據(jù)的交換來達(dá)到排序目的。

冒泡排序算法

冒泡排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：

1. 對數(shù)組中的各數(shù)據(jù)，依次比較相鄰的兩元素的大小。
2. 如果前面的數(shù)據(jù)大魚后面的數(shù)據(jù)，就交換這兩個數(shù)據(jù)。經(jīng)過第一輪的多次比較排序后，變可把最小的數(shù)據(jù)排好。
3. 再用同樣的方法把剩下的數(shù)據(jù)逐個進(jìn)行比較，最后便可按照從小到大的順序排好數(shù)組各數(shù)據(jù)的順序。

??為了更清晰地理解冒泡排序算法的執(zhí)行過程，這里我們舉一個實(shí)際數(shù)據(jù)的例子來一步步的執(zhí)行冒泡排序算法。對于五個整型數(shù)據(jù) 118、101、105、127、112，這是一組無序的數(shù)據(jù)。對其執(zhí)行冒泡排序的過程，如下圖所示。冒泡排序算法執(zhí)行步驟如下：

image

1. 第1次排序，從數(shù)組的尾部開始向前依次比較。首先是127和112比較，由于127大于112，因此將數(shù)據(jù)112向上移動一位；同理，118和101比較，將數(shù)據(jù)101向前移動一位。此時排序后的數(shù)據(jù)為 101、118、105、112、127.
2. 第2次排序，從數(shù)組的尾部開始向前依次比較。由于105和118比較，可以將數(shù)據(jù)105向前移動一位。此時排序后的數(shù)據(jù)為 101、105、118、112、127.
3. 第3次排序，從數(shù)組的尾部開始向前依次比較。由于 112 和 118 比較，可以將數(shù)據(jù)118向前移動一位。此時排序后的數(shù)據(jù)為 101、105、112、118、127。
4. 第4次排序，此時，各個數(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步的中間排序。這種排序方法思路簡單直觀，但是缺點(diǎn)就是執(zhí)行的步驟有點(diǎn)長，效率不是很高。

??一種改進(jìn)的方法，就是在每次中間排序后，比較一下數(shù)據(jù)是否已經(jīng)按照順序排列完成。如果排列完成則退出排序過程，否則就繼續(xù)進(jìn)行冒泡排序。這樣，對于數(shù)據(jù)比較有規(guī)則的，可以加速算法執(zhí)行過程。

冒泡排序算法的示例代碼如下：

void bubbleSort(int[] datas) {
        int temp;
        for (int i = 1; i < datas.length; i++) {
            for (int j = 0; j < datas.length - i; j++) {
                if (datas[j] > datas[j + 1]) {
                    temp = datas[j];
                    datas[j] = datas[j + 1];
                    datas[j + 1] = temp;
                }
            }
            System.out.print("第" + i + "步排序結(jié)果：");
            for (int k = 0; k < datas.length; k++) {
                System.out.print(" " + datas[k]);
            }
            System.out.print("\n");
        }
    }

??在這里，輸入?yún)?shù)datas一般為一個數(shù)組的首地址。待排序的原數(shù)據(jù)便保存在數(shù)組 datas中，程序中通過兩層循環(huán)來對數(shù)據(jù)進(jìn)行冒泡排序。我們可以結(jié)合前面的冒泡排序算法加深理解。

冒泡排序算法實(shí)例

??有了前面的冒泡排序算法的基本思想和算法之后。這里通過一個完整的例子說明冒泡排序法在整型數(shù)組中的應(yīng)用，程序代碼如下：

public class BubbleSort {

    static final int SIZE = 10;

    public static void bubbleSort(int[] datas) {
        int temp;
        for (int i = 1; i < datas.length; i++) {
            for (int j = 0; j < datas.length - i; j++) {
                if (datas[j] > datas[j + 1]) {
                    temp = datas[j];
                    datas[j] = datas[j + 1];
                    datas[j + 1] = temp;
                }
            }
            System.out.print("第" + i + "步排序結(jié)果：");
            for (int k = 0; k < datas.length; k++) {
                System.out.print(" " + datas[k]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        int[] datas = new int[SIZE];
        int i;
        for (i = 0; i < SIZE; i++) {
            datas[i] = (int) (100 + Math.random() * (100 + 1));
        }
        System.out.print("排序前的數(shù)組為：\n");
        for (i = 0; i < SIZE; i++) {
            System.out.print(datas[i] + " ");
        }
        System.out.print("\n");
        bubbleSort(datas);
        System.out.print("排序后的數(shù)組為：\n");
        for (i = 0; i < SIZE; i++) {
            System.out.print(datas[i] + " ");
        }
    }
}    

??在這里，程序定義符號常亮SIZE，用于表示需要排序的整型數(shù)組的大小。在主方法中，首先定義一個整型數(shù)組，對數(shù)組進(jìn)行隨機(jī)初始化，并輸出數(shù)組內(nèi)容。接著調(diào)用冒泡排序算法的方法對數(shù)組排序。最后，輸出排序后的數(shù)組。

??程序的執(zhí)行結(jié)果如下圖所示。這里，顯示了每一步的排序結(jié)果。從中可以看出從第六步開始，便已經(jīng)完成對數(shù)據(jù)的排序，但算法還是進(jìn)行了后續(xù)的比較步驟。通過前面的說明，加入判斷部分，使其盡早的將誒書排序過程，從而提高執(zhí)行效率。

image