Java冒泡排序及優化介紹

Posted on by

什麼是冒泡排序

冒泡排序指重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從小到大）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

思路分析

以{5,3,9,7,1}為例 要求排序後的數組元素順序按從小到大排序。依次比較相鄰的兩個數（藍色），將比較小的數放在前面，比較大的數放在後面。每一輪排序都能得到參與比較的數的最大值（紅色）
第一輪排序
5,3,9,7,1 //如果數大於相鄰的數就交換位置
3,5,9,7,1
3,5,9,7,1
3,5,7,9,1
3,5,7,1,9 //第一輪排序的結果
第二輪排序
3,5,7,1,9
3,5,7,1,9
3,5,7,1,9
3,5,1,7,9 //第二輪排序的結果
第三輪排序
3,5,1,7,9
3,5,1,7,9
3,1,5,7,9 //第三輪排序的結果
第四輪排序
3,1,5,7,9
1,3,5,7,9 //第四輪排序的結果

代碼實現

public class bubble {
    public static void main(String[] args) {
        int[] array = {5,3,9,7,1};
        bubbleSort(array);
    }
    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array){
        int temp;
        //一共進行length-1次排序
        for (int i = 0; i < array.length-1; i++) {
            //數組中沒有元素或者隻有一個元素就無需排序
            if(array==null || array.length < 2 ){
                return;
            }
            //每進行一次排序後參與比較的數量減一
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j]>array[j+1]) {
                    //互換元素位置
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            System.out.println("第"+(i+1)+"輪排序的結果是"+ Arrays.toString(array));
        }
        return;
    }
}

結果輸出

第1輪排序的結果是[3, 5, 7, 1, 9]
第2輪排序的結果是[3, 5, 1, 7, 9]
第3輪排序的結果是[3, 1, 5, 7, 9]
第4輪排序的結果是[1, 3, 5, 7, 9]

Process finished with exit code 0

代碼優化

根據上述算法發現對於長度為n的數組需要進行n-1輪排序才能算出最終的結果,但是並非所有數組都需要n-1次才能等要最終的排序結果,比如{1，2，3，5，4}我們發現這個數組隻需經過一次排序就能得到結果,那麼如何對上面的代碼進行優化呢？隻需判斷一輪排序下來有無出現元素互換位置就可以確定是否完成瞭排序。如果經過一輪排序元素位置沒有發生互換說明排序已經完成

public class bubblePlus {
    public static void main(String[] args) {
        int[] array = {1,2,3,5,4};
        bubboSort(array);
    }
	/**
	*冒泡排序
	*/
    public static void bubboSort(int[] array){
        int temp;
        //判斷是否有元素進行交換
        boolean flag = false;
        for (int i = 0; i < array.length-1; i++) {
            if(array==null || array.length < 2 ){
                return;
            }
            //每進行一次排序後參與比較的數量減一
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j]>array[j+1]) {
                    //位置交換就改為true
                    flag = true;
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            if (!flag){
                //位置沒有發生交換說明排序已經完成
                break;
            }else{
                //位置發生改變需要將flag重新置為false以便於下一輪的判斷
                System.out.println("第"+(i+1)+"輪排序的結果是"+ Arrays.toString(array));
                flag = false;
            }
        }
        return;
    }
}

優化後的結果輸出

第1輪排序的結果是[1, 2, 3, 4, 5]

Process finished with exit code 0

到此這篇關於Java冒泡排序及優化介紹的文章就介紹到這瞭,更多相關Java冒泡排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：