Java冒泡排序?qū)嵗治?/h1>

發(fā)布時間：2022-01-15 14:02:08 來源：億速云 閱讀：154 作者：iii 欄目：大數(shù)據(jù)

這篇文章主要介紹了Java冒泡排序?qū)嵗治龅南嚓P(guān)知識，內(nèi)容詳細(xì)易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java冒泡排序?qū)嵗治鑫恼露紩兴斋@，下面我們一起來看看吧。

情況是這樣子的，當(dāng)時和面試官聊的感覺還可以，就在他覺得好像差不多快結(jié)束的時候，面試官給他扔了個題：“我這剛好有紙和筆，你來寫個冒泡排序吧?！?/p>

這位讀者心里一慌，為什么慌，倒并不是因為不會寫，因為作為一個程序員，冒泡排序基本上沒有不會寫的，而是事發(fā)突然，感覺不太妙。當(dāng)時他是這么寫的：

public void bubbleSort(int[] source) {
    for(int i = source.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1])
                 //交換，具體實現(xiàn)略
                 swap(source, j, j+1); 
        }
    }
}

    

果不其然，他寫了之后，面試官就問他，這種寫法有沒有什么問題？能否繼續(xù)優(yōu)化？結(jié)果還真沒答上來。（看到這里，讀者們不妨也先思考下如何優(yōu)化。）

今天就這個冒泡排序，我們再多聊幾句，回歸一下經(jīng)典。也希望以后有朋友實習(xí)也好，校招也罷，不要再栽在同樣的問題上了。

冒泡排序算法的時間復(fù)雜度高，如果不清楚算法復(fù)雜度如何計算，可以參考下這篇文章：循序漸進(jìn)帶你學(xué)習(xí)時間復(fù)雜度和空間復(fù)雜度。但是冒泡排序簡單，基本流程是：每一輪從頭開始兩兩比較，將較大的項放在較小項的右邊，這樣每輪下來保證該輪最大的數(shù)在最右邊。如何實現(xiàn)？就如上面這位朋友所寫的那樣，基本上大家都會寫。

但是今天主要討論的是如何優(yōu)化，有人可能會說，這是再簡單不過的算法了，還有什么好優(yōu)化的？確實，上面這段代碼沒有毛病，但的確是有可優(yōu)化之處的。

我們可以假設(shè)一種場景，比如 8 1 2 3 5 7，進(jìn)行一次排序之后，結(jié)果就變成了 1 2 3 5 7 8，那我們還有必要再像上面代碼里那樣繼續(xù)循環(huán)下去嗎？肯定沒有必要了，因為這已經(jīng)是最終結(jié)果了。

針對上面的代碼，我們優(yōu)化的點主要在于：假如某一趟排序之后已經(jīng)有序，我們需要減少排序的趟數(shù)。否則就做了很多無用功。

針對這個問題，我們可以考慮在算法中加入一個布爾變量，來標(biāo)識該輪有沒有進(jìn)行數(shù)據(jù)的交換，若在某一趟排序中未發(fā)現(xiàn)數(shù)據(jù)位置的交換，則說明待排序的無序區(qū)中所有的項均已滿足排序后的結(jié)果。那么就沒有必要再次排序下去了?？梢匀缦赂脑欤?br/>

public void bubbleSort(int[] source) {
    boolean exchange;
    for(int i = source.length - 1; i > 0; i--) {
        exchange = false;
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1]) {
                swap(source, j, j+1);
               exchange = true;
            }
        }
        if(!exchange) return;
    }
}

這樣就優(yōu)化完了，其實代碼邏輯很簡單，通過一個布爾變量即可監(jiān)控一趟過程有沒有進(jìn)行數(shù)據(jù)交換。

冒泡排序最好的情況是初始狀態(tài)是正序的，一次掃描即可完成排序，所以最好的時間復(fù)雜度為O(N)；最壞的情況是反序的，此時最壞的時間復(fù)雜度為O(N^2)。平均情況，每輪N/2次循環(huán)，N輪時間復(fù)雜度為O(N^2)。所以它并不是個好的排序算法。這個問題的討論就到此結(jié)束，如果有更好的優(yōu)化算法也歡迎留言討論。

冒泡排序并不好，但為什么面試官還會去問？針對這件事情，我們需要注意什么呢？

1. 經(jīng)典的東西，可能已經(jīng)不用了，但是從經(jīng)典的東西身上，我們能學(xué)到的還有很多，否則也不會成為經(jīng)典。特別是那些面試經(jīng)常被問到的，總有它存在的合理性。

2. 教科書上的東西不代表實戰(zhàn)，所以很多時候考慮到非理想情況下，就可能不那么適用了。面試官往往更加注重的是在不適用的情況下，面試者是如何應(yīng)對的。面試官更加看重的是面試者的思路。

3. 應(yīng)屆生不能浮躁，特別是在準(zhǔn)備面試的時候，一定要步步為營，切忌好高騖遠(yuǎn)，淺嘗輒止，多學(xué)習(xí)學(xué)習(xí)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法（最常用的經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法匯總），多做做算法題還是很有必要的。

關(guān)于“Java冒泡排序?qū)嵗治觥边@篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“Java冒泡排序?qū)嵗治觥敝R都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道。