冒泡排序

原理：比較相鄰兩個(gè)數(shù)，將較大的數(shù)移至右邊。

思路：

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

如： 排序[3,2,5,4,1]

1. 兩兩交換相鄰的數(shù)字進(jìn)行交換，大的數(shù)字移到右邊，故3和2交換位置；[2,3,5,4,1]
2. 然后重復(fù)上述工作，3和5比較，不用交換，故第一輪下來(lái)結(jié)果為[2,3,4,1,5]
3. 第二輪結(jié)果為[2,3,1,4,5]
4. 經(jīng)過N-1輪排序，也就是4輪，完成排序[1,2,3,4,5]

代碼如下：

核心代碼：

public static void BubbleSort(int[] target) {
        if(target==null||target.length<2){
            return;
        }

        int length = target.length;
        // 這里for循環(huán)表示總共需要比較多少輪
        for (int i = 0; i < length; i++) {
            //這里for循環(huán)表示每輪比較需要參與元素的數(shù)量
            for (int j = 0; j < length - i -1; j++) {
                if (target [j] > target [j+1]) {
                    int temp = target[j+1];
                    target [j+1] = target[j];
                    target [j] = temp;
                }
            }
            //第i輪排序的結(jié)果為
            System.out.print("第"+i+"輪排序后的結(jié)果為:");
            display(target);
        }
    }

完整測(cè)試代碼：

public class Main {

    public static void main(String[] args) {
    // write your code here
        int[] target = {3,2,5,4,1};
        System.out.println("未排序數(shù)組順序?yàn)椋?);
        display(target);
        System.out.println("-----------------------");
        BubbleSort(target);
        System.out.println("-----------------------");
        System.out.print("最終的排序結(jié)果:");
        display(target);
    }

    public static void BubbleSort(int[] target) {
        if(target==null||target.length<2){
            return;
        }

        int length = target.length;
        // 這里for循環(huán)表示總共需要比較多少輪
        for (int i = 0; i < length; i++) {
            //這里for循環(huán)表示每輪比較需要參與元素的數(shù)量
            for (int j = 0; j < length - i -1; j++) {
                if (target [j] > target [j+1]) {
                    int temp = target[j+1];
                    target [j+1] = target[j];
                    target [j] = temp;
                }
            }
            //第i輪排序的結(jié)果為
            System.out.print("第"+i+"輪排序后的結(jié)果為:");
            display(target);
        }
    }

    //顯示數(shù)組
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}

最終結(jié)果：

未排序數(shù)組順序?yàn)椋?3 2 5 4 1 
-----------------------
第0輪排序后的結(jié)果為:2 3 4 1 5 
第1輪排序后的結(jié)果為:2 3 1 4 5 
第2輪排序后的結(jié)果為:2 1 3 4 5 
第3輪排序后的結(jié)果為:1 2 3 4 5 
第4輪排序后的結(jié)果為:1 2 3 4 5 
-----------------------
最終的排序結(jié)果:1 2 3 4 5 

解釋及分析：
解釋：本來(lái)應(yīng)該是 5 輪排序的，因?yàn)榈?4 輪排序之后已經(jīng)是有序數(shù)組了。所以，N個(gè)數(shù)字要排序完成，總共進(jìn)行N-1趟排序，每i趟的排序次數(shù)為(N-i)次；
冒泡排序是由兩個(gè)for循環(huán)構(gòu)成，第一個(gè)for循環(huán)的變量 i 表示總共需要多少輪比較，第二個(gè)for循環(huán)的變量 j 表示每輪參與比較的元素下標(biāo)【0,1，......，length-i】，因?yàn)槊枯啽容^都會(huì)出現(xiàn)一個(gè)最大值放在最右邊，所以每輪比較后的元素個(gè)數(shù)都會(huì)少一個(gè)，這也是為什么 j 的范圍是逐漸減小的。

性能分析：

冒泡排序總的平均時(shí)間復(fù)雜度為：O(n*n)。