Java如何實現冒泡排序及優化

這篇文章給大家分享的是有關Java如何實現冒泡排序及優化的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

什么是冒泡排序

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

思路分析

以{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如何實現冒泡排序及優化”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！