寫(xiě)在前邊的話：今天記錄一下關(guān)于算法中冒泡排序的一些理解和心得。
主要分為以下3個(gè)方面介紹

• 冒泡排序的思想
• 分析
• 標(biāo)準(zhǔn)實(shí)現(xiàn)方式
• 優(yōu)化
• 時(shí)間復(fù)雜度

冒泡排序的思想

1：給定一個(gè)具有N位數(shù)據(jù)的數(shù)組,從起始位置依次與其后一位數(shù)據(jù)進(jìn)行 “兩兩比較”，“若當(dāng)前值比其后一位值要小(大)，則交換2者的數(shù)據(jù)”。
2：“繼續(xù)從下一位開(kāi)始此操作”，直至計(jì)算出最小(大)值(這樣一趟下來(lái)，必能找出一個(gè)最小(大)值)。
3：重復(fù)上述操作N-1次，直到數(shù)組中所有數(shù)據(jù)滿足降(升)序?yàn)橹埂?/p>

分析

• 冒泡排序的話是 兩兩比較，即當(dāng)前值與其下一位。
• swap操作。
• swap操作結(jié)束之后，繼續(xù)移動(dòng)指針到下一位，重復(fù)前兩次操作。
• 有N個(gè)數(shù)據(jù)，就需要執(zhí)行N-1次循環(huán)。因?yàn)橐惶搜h(huán)走下來(lái)，只能確立一個(gè)最小(大)值。

標(biāo)準(zhǔn)實(shí)現(xiàn)方式

    public static void main(String[] args){
        Integer[] array1 = createRandomArray();
        Integer[] array3 = Arrays.copyOf(array1, array1.length);

        bubbleSort2(array1);
        Util.print(array1);

        test(array3);
        Util.print(array3);
    }

    /**
     * 冒泡排序
     * @param src 數(shù)據(jù)源
     */
    private static void bubbleSort2(Integer[] src){
        Util.checkSrc(src);

        for(int end = 0; end < src.length - 1; end++){      //n-1次循環(huán)
            for(int j = 0; j < src.length - 1 - end; j++){  //只比較從0開(kāi)始，到第n-end數(shù)
                if(src[j] > src[j + 1]){                    //兩兩比較(不直接與最后一個(gè)比較)
                    int temp = src[j];
                    src[j] = src[j + 1];
                    src[j + 1] = temp;
                }
            }
        }
    ｝

    /**
     * 對(duì)數(shù)器(采用系統(tǒng)提供的排序算法，絕對(duì)正確)
     * @param src 數(shù)據(jù)源
     */
    private static void test(Integer[] src){
        Arrays.sort(src);
    }

   /**
     * 返回隨機(jī)創(chuàng)建的一維數(shù)組
     */
    private static Integer[] createRandomArray(){
        int count = 20;
        int base = 100;

        Integer[] arrays = new Integer[count];
        for(int i = 0; i < arrays.length; i++){
            arrays[i] = (int)(Math.random() * base);
        }

        return arrays;
    }

查看下log

Result:8---13---20---28---31---36---45---50---51---51---54---57---58---60---65---71---76---89---90---97
Result:8---13---20---28---31---36---45---50---51---51---54---57---58---60---65---71---76---89---90---97

優(yōu)化

    /**
     * 冒泡排序(優(yōu)化冒泡-1)
     * @param src 數(shù)據(jù)源
     */
    private static void bubbleSort2_1(Integer[] src){
        Util.checkSrc(src);

        //作用:如果內(nèi)部循環(huán)(swap循環(huán))執(zhí)行完事之后,再判斷是否需要執(zhí)行下次循環(huán)。
        //1:此值為false,表明 該序列已然是有序數(shù)列,不再繼續(xù)后續(xù)操作,此方法執(zhí)行結(jié)束(eg:2,4,5,6,10)。
        //2:此值為true,表明 當(dāng)前循環(huán)執(zhí)行了swap操作,此次循環(huán)操作不能保證 該序列是有序的,需要再次循環(huán)判斷一下(eg:3,1,2,5,6)。
        boolean flag = true;                                  //方法是否需要繼續(xù)執(zhí)行標(biāo)記

        for(int i = 0; i < src.length - 1 && flag; i++){      //n-1次循環(huán)
            flag = false;

            for(int j = 0; j < src.length - 1 - i; j++){      //只比較從0開(kāi)始，到第n-end數(shù)
                if(src[j] > src[j + 1]){                      //兩兩比較
                    int temp = src[j];
                    src[j] = src[j + 1];
                    src[j + 1] = temp;

                    flag = true;
                }
                
                if(!flag){
                  break;
                }

                Util.print(src, "Sort2-1--第:" + i + "循環(huán)" + "--j:" + j + "---");
            }
        }
    }
  
    public static void main(String[] args){
        //Integer[] array1 = createRandomArray();
        Integer[] array1 = {3, 1, 2, 6, 7, 20};
        Integer[] array2 = Arrays.copyOf(array1, array1.length);
        Integer[] array3 = Arrays.copyOf(array1, array1.length);

        System.out.println("數(shù)據(jù)源：" + Arrays.toString(array1) + "---------------------------------");

        bubbleSort2(array1);
        Util.print(array1 , "Sort-Nomal");

        System.out.println("------------------------------------------------------");

        bubbleSort2_1(array2);
        Util.print(array2 , "Sort-Better");

        System.out.println("------------------------------------------------------");

        test(array3);
        Util.print(array3, "Result");
    }

查看log

數(shù)據(jù)源：[3, 1, 2, 6, 7, 20]---------------------------------
Sort2--第:0循環(huán)--j:0---:1---3---2---6---7---20
Sort2--第:0循環(huán)--j:1---:1---2---3---6---7---20
Sort2--第:0循環(huán)--j:2---:1---2---3---6---7---20
Sort2--第:0循環(huán)--j:3---:1---2---3---6---7---20
Sort2--第:0循環(huán)--j:4---:1---2---3---6---7---20
Sort2--第:1循環(huán)--j:0---:1---2---3---6---7---20
Sort2--第:1循環(huán)--j:1---:1---2---3---6---7---20
Sort2--第:1循環(huán)--j:2---:1---2---3---6---7---20
Sort2--第:1循環(huán)--j:3---:1---2---3---6---7---20
Sort2--第:2循環(huán)--j:0---:1---2---3---6---7---20
Sort2--第:2循環(huán)--j:1---:1---2---3---6---7---20
Sort2--第:2循環(huán)--j:2---:1---2---3---6---7---20
Sort2--第:3循環(huán)--j:0---:1---2---3---6---7---20
Sort2--第:3循環(huán)--j:1---:1---2---3---6---7---20
Sort2--第:4循環(huán)--j:0---:1---2---3---6---7---20
Sort-Nomal:1---2---3---6---7---20
------------------------------------------------------
Sort2-1--第:0循環(huán)--j:0---:1---3---2---6---7---20
Sort2-1--第:0循環(huán)--j:1---:1---2---3---6---7---20
Sort2-1--第:0循環(huán)--j:2---:1---2---3---6---7---20
Sort2-1--第:0循環(huán)--j:3---:1---2---3---6---7---20
Sort2-1--第:0循環(huán)--j:4---:1---2---3---6---7---20
Sort2-1--第:1循環(huán)--j:0---:1---2---3---6---7---20
Sort2-1--第:1循環(huán)--j:1---:1---2---3---6---7---20
Sort2-1--第:1循環(huán)--j:2---:1---2---3---6---7---20
Sort2-1--第:1循環(huán)--j:3---:1---2---3---6---7---20
Sort-Better:1---2---3---6---7---20
------------------------------------------------------
Result:1---2---3---6---7---20

時(shí)間復(fù)雜度

結(jié)論:O(n^2)

分析:
假如有n=5個(gè)數(shù)要排序，總共需要執(zhí)行n-1=4次循環(huán)操作
第1次：需要比較n-1=4次
第2次：需要比較n-2=3次
第3次：需要比較n-3=2次
第4次：需要比較n-4=1次

總共執(zhí)行的次數(shù)是多少呢？
我們發(fā)現(xiàn)這個(gè)有點(diǎn)像求 “1+2+3+...+100”，這不就是等差數(shù)列嗎？
那么整個(gè)執(zhí)行的次數(shù)應(yīng)該為:(n-1+n-2+...+2+1)=n^2/2
所以“冒泡排序的時(shí)間復(fù)雜度為 O(n^2)”