為什么要學(xué)排序

我覺得可以提升自己的編程能力猿推，學(xué)習(xí)更多的算法思想片习，數(shù)據(jù)結(jié)構(gòu)。是的蹬叭，學(xué)習(xí)算法的確可以給你帶來這些方面的提升藕咏，但我相信經(jīng)歷過互聯(lián)網(wǎng)校招、計算機(jī)考研的人都知道秽五，算法和數(shù)據(jù)結(jié)構(gòu)都是不可避免的孽查。尤其在現(xiàn)在的互聯(lián)網(wǎng)大環(huán)境下，提升自己的算法和數(shù)據(jù)結(jié)構(gòu)水平是有必要的筝蚕。

談到排序算法卦碾，一般是以下八個铺坞。冒泡排序起宽，插入排序洲胖，選擇排序，歸并排序坯沪，快速排序绿映，堆排序，希爾排序腐晾，基數(shù)排序叉弦。今天我們就來聊聊冒泡排序，這是個非常入門的排序算法藻糖，我將盡量以通俗的語言向讀者介紹冒泡排序淹冰，相信你看完這篇文章，就能完全掌握它啦巨柒。

冒泡排序的過程

冒泡排序是一種比較排序樱拴，也就是說兩個元素來比較大小，然后交換他們彼此的位置洋满，最后達(dá)到排序的目的晶乔。注意這里強(qiáng)調(diào)“元素”這個概念，而不是讀者通常意義上理解的數(shù)字牺勾，是因為如大小寫字母正罢、ASSIC表中的字符都是可以用來排序的，如 Java 中的比較器可以自己制定排序規(guī)則驻民。

以下圖中的待排序元素為例翻具，我們來分析一下整個冒泡排序的過程。
4 6 2 5 1 是待排序元素序列回还，首先分析下第一輪排序（Step 1）的過程裆泳。

1. 首先 4 和 6 比較，4 比 6 小懦趋，所以 4 和 6 不需要交換位置晾虑。
2. 然后 6 和 2 比較，6 比 2 大仅叫，交換位置帜篇。
3. 然后 6 和 5 比較，6 比 5 大诫咱，交換位置笙隙。
4. 然后 6 和 1 比較，6 比 1 大坎缭，交換位置竟痰。

這樣第一輪（Step 1）將整個序列中最大的元素（6）交換到末尾签钩。剩下的幾輪過程（Step 2-Step 4）都是一樣的，讀者可以類比上述過程自行理解坏快。

排序過程

可以發(fā)現(xiàn)铅檩，每一輪排序結(jié)束后，待排序序列（綠色數(shù)字部分）中的最大一個值會加入到已排序序列（黃色數(shù)字部分）中莽鸿，注意已排序序列（紅色線條右側(cè)部分）在下一輪排序中不會被加入比較昧旨。在第 4 輪的時候，我們發(fā)現(xiàn)整個序列已經(jīng)排好序祥得。

整個過程就是這么簡單清爽兔沃。有了上面的排序思想，那么就要將思想轉(zhuǎn)化為代碼级及，實現(xiàn)如下乒疏。

public static int[] bubbleSort(int[] arr) {
    for(int i=0;i<arr.length;i++) {  // 控制排序輪次
        for(int j=1;j<arr.length-i;j++) {  // 進(jìn)行一輪排序過程
            if(arr[j]<arr[j-1])  // 后面比前面小，交換位置
                swap(arr,j,j-1);  
        }
    }
    return arr;
} 

// 交換函數(shù)
private static void swap(int[] arr, int j, int i) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
} 

冒泡排序的時間復(fù)雜度

對于時間復(fù)雜度饮焦，我希望讀者牢記一句話：將算法中基本操作的執(zhí)行次數(shù)作為算法時間復(fù)雜度的度量怕吴。時間復(fù)雜度不是執(zhí)行完一段程序的總時間，而是其中基本操作的總次數(shù)追驴。計算一個算法時間復(fù)雜度的具體步驟如下械哟。

1. 確定算法中基本操作以及問題的規(guī)模。
2. 根據(jù)基本操作執(zhí)行情況計算出規(guī)模 n 的函數(shù) 殿雪，并確定時間復(fù)雜度為暇咆。

是不是有點難懂？沒關(guān)系丙曙，我們以求冒泡排序的時間復(fù)雜度來還原上述步驟爸业。

1. 首先確定冒泡排序的基本操作是 swap 函數(shù) ，即元素交換的操作亏镰。
2. 冒泡排序內(nèi)層循環(huán)的執(zhí)行條件決定了基本操作的執(zhí)行次數(shù)扯旷。

那么內(nèi)層循環(huán)到底執(zhí)行了多少次呢？根據(jù)上圖索抓，如果序列有 5 個元素钧忽，那么需要比較的次數(shù)是 4 + 3 + 2 + 1。現(xiàn)在我們用 n 來表示序列的元素個數(shù)逼肯，那么 n 個元素經(jīng)過冒泡排序有序后的基本操作執(zhí)行次數(shù)就是 n-1 項耸黑，公差為 1 的等差數(shù)列求和，如下圖所示篮幢。

時間復(fù)雜度

根據(jù)公式大刊，所以時間復(fù)雜度就是 。

冒泡排序如何優(yōu)化

冒泡排序還能優(yōu)化嗎三椿？讀者可能覺得到這里全文就結(jié)束了缺菌，但冒泡排序是可以優(yōu)化的葫辐。如上分析，冒泡排序無論原序列是否有序伴郁，都會就行比較耿战。我們要做的優(yōu)化就是，如果未排序的序列已經(jīng)有序蛾绎，那就不需要就行比較了昆箕，直接退出循環(huán)鸦列。

那么如何確定未排序序列已經(jīng)有序了呢租冠？一個簡單的方法是：在上一輪排序過程中記錄下是否有元素交換，如果有交換則說明未排序序列不是有序的薯嗤，如果沒有交換顽爹，則說明整個序列已經(jīng)有序，不需要進(jìn)行下一輪的比較骆姐，直接退出循環(huán)即可镜粤，代碼優(yōu)化如下。

public static int[] bubbleSort(int[] arr) {
    for(int i=0;i<arr.length;i++) {
        boolean switched = false;
        for(int j=1;j<arr.length-i;j++) {
            if(arr[j]<arr[j-1]) {
                switched = true;  // 有元素交換玻褪，所以不是有序
                swap(arr,j,j-1);
            }
        }
        if(!switched) {  // 沒有元素交換肉渴，有序。直接退出循環(huán)
            break;
        }
    }
    return arr;
}  

寫在最后

讀者第一次接觸排序概念的時候带射，基本是大學(xué)學(xué)數(shù)據(jù)結(jié)構(gòu)那會同规，教材會有這些內(nèi)容的講解，不過據(jù)我觀察窟社，初學(xué)者對這些內(nèi)容經(jīng)常會感到迷糊券勺。其實本質(zhì)上還是沒有完全掌握排序算法的思想，導(dǎo)致寫代碼的時候會卡殼灿里，無從下手。畢竟沒有一個程序員會去背算法代碼，這樣的學(xué)習(xí)方式就大錯特錯了锰瘸。學(xué)習(xí)編程最有效的方法桌肴，其實是去實踐。將算法思想用代碼一遍又一遍的實踐色鸳，如果你看到本文并對冒泡排序還有疑惑社痛，那就趕緊行動起來吧！

如果你對我感興趣缕碎，請移步到 http://blogss.cn 褥影，
或關(guān)注公眾號：程序員小北，進(jìn)一步了解咏雌。

• 如果本文幫助到了你凡怎，歡迎點贊和關(guān)注 ??
• 由于作者水平有限校焦，文中如果有錯誤，歡迎在評論區(qū)指正 ??
• 本文首發(fā)于簡書统倒，未經(jīng)許可禁止轉(zhuǎn)載 ??