Java最簡潔數(shù)據(jù)結(jié)構(gòu)之冒泡排序快速理解

更新時間：2021年11月15日 14:47:20 作者：AXiYa_Ari

冒泡排序是編程中數(shù)據(jù)結(jié)構(gòu)繞不過的一個基礎(chǔ)點，有關(guān)于冒泡排序的文章也有很多，但可能會比較繚亂未能理解，本章將一子u為簡潔明了的例圖帶你通關(guān)冒泡排序

一、什么是冒泡排序

冒泡排序的英文是bubble sort，它是一種基礎(chǔ)的交換排序。說到冒泡是不是就想起了快樂肥宅水呢？汽水中有許多小小的水泡嘩啦嘩啦的浮到上面來。這是因為組成小氣泡的二氧化碳比水輕，所以小氣泡可以一點一點地向上浮動。

而冒泡排序之所以叫冒泡排序，正是因為這種排序算法的每一個元素都可以像小氣泡一樣，根據(jù)自身的大小，一點一點的向著數(shù)組的一側(cè)移動。

二、圖解冒泡排序

我們先看一個例子，有七個數(shù)字組成一個無序數(shù)列{5，6，3，4，1，7}，對他進行冒泡排序。

按照冒泡排序的思想：把相鄰的兩個數(shù)字兩兩比較，當(dāng)一個數(shù)字大于右側(cè)相鄰的數(shù)字時，交換他們的位置，當(dāng)一個數(shù)字和他右側(cè)的數(shù)字小于或等于的時候，不交換。

這樣，作為數(shù)列中的最大的數(shù)字7就交換到了最右側(cè)。這時第一輪冒泡結(jié)束。（有效區(qū)域只有最后一個）

根據(jù)第一輪的交換細節(jié)，第二輪到第六輪的狀態(tài)為下圖。

到此為止，所有的數(shù)字都是有序的了，冒泡排序是一種穩(wěn)定排序，由于該排序算法的每一輪都要遍歷所有的數(shù)字，一共要遍歷n-1，所以時間復(fù)雜度為O(n^2)。

那么我們?nèi)绾螀^(qū)分排序算法是否穩(wěn)定呢？

如果我們交換的時候，遇到兩個相同的數(shù)字，如果兩個相同的數(shù)字在排序之后相對位置沒有交換，那么就是穩(wěn)定的排序，反之則是不穩(wěn)定的排序。

三、代碼實現(xiàn)

    public static void bubbleSort(int arr[]){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j <arr.length-i-1 ; j++) {
                int tmp=0;
                if(arr[j]>arr[j+1]){
                    tmp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = new int[]{5,6,3,2,4,1,7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

四、代碼的優(yōu)化

1、整體的思路

從上面的例子不難看出，我們可以對原來的冒泡排序進行優(yōu)化。我們?nèi)匀挥蒙厦婺貍€數(shù)列{5，6，3，4，1，7}為例子，從上面的圖解可以看出在第五輪排序后，整個數(shù)列已經(jīng)是有序的，但是排序算法還是執(zhí)行了第六輪排序。

優(yōu)化的思路是：如果能判斷出數(shù)列已經(jīng)是有序的了，并且做出標(biāo)記，那么就不會執(zhí)行多余的排序。

所以我們可以用布爾變量isSorted作為標(biāo)記，如果在本輪排序中有元素進行交換，則說明數(shù)列無序；如果在本輪排序中，沒有元素進行交換，我們則認為此時數(shù)列已經(jīng)為有序的，不需要再去進行下一輪的排序。

2、代碼示例

    public static void bubbleSort(int arr[]){
        for (int i = 0; i < arr.length-1; i++) {
            //有序標(biāo)記，每一輪的初始值都是true
            boolean isSorted=true;
            for (int j = 0; j < arr.length-i-1; j++) {
                int tmp=0;
                if (arr[j]>arr[j+1]){
                    tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    //因為有元素進行交換，所以不是有序的，標(biāo)記變?yōu)閒alse
                    isSorted=false;
                }
            }
            if (isSorted){
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{5,6,3,2,4,1,7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

以上就是Java最簡潔數(shù)據(jù)結(jié)構(gòu)之冒泡排序快速理解的詳細內(nèi)容，更多關(guān)于Java 冒泡排序的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: