一、什么是冒泡排序

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

而冒泡排序之所以叫冒泡排序，正是因?yàn)檫@種排序算法的每一個(gè)元素都可以像小氣泡一樣，根據(jù)自身的大小，一點(diǎn)一點(diǎn)的向著數(shù)組的一側(cè)移動(dòng)。

二、圖解冒泡排序

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

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

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

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

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

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

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

三、代碼實(shí)現(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、整體的思路

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

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

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

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;
                    //因?yàn)橛性剡M(jìn)行交換，所以不是有序的，標(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)之冒泡排序快速理解的詳細(xì)內(nèi)容，更多關(guān)于Java 冒泡排序的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論