摘要：二冒泡排序算法作為這一系列的第一部分，主要講解排序算法。直到隊(duì)列全部排好為止。到這里，我想你應(yīng)該明白了冒泡排序的思想了。

一直想寫一些簡單易懂的文章，因?yàn)槠綍r(shí)看的很多的書籍或者文章都是看著很難受的感覺，當(dāng)然，這并不是說書籍寫的不好，只是說對于一些沒有太多基礎(chǔ)或者基礎(chǔ)不是很好的來說，相對來說還是比較難以理解的。

這個(gè)系列主要是寫一些簡單易懂的數(shù)據(jù)結(jié)構(gòu)與算法的文章，同時(shí)也是幫助自己再理解理解這方面的知識。

作為數(shù)據(jù)結(jié)構(gòu)與算法的開篇，還是以排序算法作為第一部分的內(nèi)容，需要注意的是，這一系列的文章并不是涉及到很多理論性質(zhì)的知識，因?yàn)榍懊嬲f了，主要還是希望文章是簡單易懂的，希望能達(dá)到讀故事的感覺。如果需要去學(xué)習(xí)理論性質(zhì)的知識，可以去查看相關(guān)的數(shù)據(jù)結(jié)構(gòu)與算法的書籍。

作為這一系列的第一部分，主要講解排序算法。從小到大，我們至少前20年的時(shí)間都是在學(xué)校度過了，校園生活在我看來是十分的美好的，以至于現(xiàn)在我都還在校園里面生活。在我們讀書的階段，是不是經(jīng)常會碰到排隊(duì)的時(shí)候，因?yàn)榇蠹叶际煜み@一場景，所以，我們就一排隊(duì)來講解排序算法。

冒泡算法應(yīng)該是我們最熟悉不過的算法了，也是我們最熟悉不過的排隊(duì)了，既然熟悉不過，那么我們今天就來排個(gè)冒泡排序的隊(duì)列吧。

今天早上，老師叫我們?nèi)ゲ賵錾献鲈绮?，做早操之前呢，需要排?duì)，排隊(duì)都有一個(gè)排法，不是嗎？那么，老師今天就要求我們按照身高由低到高依次排好。

于是，我們早上很快就一起到了操場上，總共有5個(gè)人到了操場，剛剛?cè)サ臅r(shí)候，隊(duì)列肯定是散的對吧，這時(shí)候的隊(duì)列是下面這樣子的：第0個(gè)位置站的小明，第1個(gè)位置站的小海，第2個(gè)位置站的小劉，第3個(gè)位置站的小李，第5個(gè)位置站的小愛。

于是老師（假設(shè)老師是一個(gè)程序員哈，皮一下）要求我們按照冒泡排序的方法排好隊(duì)：挨個(gè)的比較身高，如果比下一個(gè)位置上的同學(xué)高，就換一下位置。

好了，同學(xué)們聽到老師的指示之后呢，同學(xué)們就開始動(dòng)身了。

第0個(gè)位置上的小明同學(xué)和第1個(gè)位置上的小海同學(xué)相互比了一下身高，發(fā)現(xiàn)第1個(gè)位置上的小海同學(xué)（1.80m）比第0個(gè)位置上的小海同學(xué)（1.60m）高，于是就保持不動(dòng)，所以第一次排隊(duì)后，隊(duì)列還是保持不變的。

接下來，第1個(gè)位置上的小海同學(xué)還想和第2個(gè)位置上的小劉同學(xué)比一下身高，發(fā)現(xiàn)第1個(gè)位置上的小海同學(xué)比第2個(gè)位置上的小劉同學(xué)高，所以，他們互換一下位置。

于是，隊(duì)列成了下面的樣子，小海和小劉換了一下位置。

之后，第2個(gè)位置上的小海同學(xué)，又和第3個(gè)位置上的小李同學(xué)比了一下身高，發(fā)現(xiàn)，第2個(gè)位置上的小海同學(xué)還是比第3個(gè)位置上的小李同學(xué)高，所以他們還是需要交換一下位置的。

這時(shí)候，隊(duì)列變成了下面的樣子，小海和小李互換。

接下來第3個(gè)位置上的小海同學(xué)和第4個(gè)位置上的小愛同學(xué)進(jìn)行了身高的比較，發(fā)現(xiàn)第3個(gè)位置上的小海同學(xué)還是比第4個(gè)位置上的小愛同學(xué)高，所以又需要換一下。

交換后，變成了這樣子：

結(jié)果我們發(fā)現(xiàn)，通過這種排序方法，最高的小海從第2個(gè)位置上跑到了最后一個(gè)位置

好了，現(xiàn)在最高的小海的位置已經(jīng)確定了，我們就不管他了，我們又從第0個(gè)位置上的同學(xué)開始，第0個(gè)位置的小明同學(xué)和第1個(gè)位置的小劉同學(xué)比較身高，發(fā)現(xiàn)小明的身高比小劉的矮，所以隊(duì)列維持不變。

接下來，第1個(gè)位置上的小劉和第2個(gè)位置上的小李比較，發(fā)現(xiàn)，小劉比小李高，所以需要交換位置

交換后，變成了下面的隊(duì)列

然后，第2個(gè)位置上的小劉和相鄰的第3個(gè)位置上的小愛比較身高，發(fā)現(xiàn)小愛比小劉高，所以不交換位置

最后一個(gè)位置的小海因?yàn)榈谝惠喴呀?jīng)知道他最高了，所以不與他比較了，因此，這輪排完之后，我們發(fā)現(xiàn)，整個(gè)序列已經(jīng)是有序的了，我們看一下隊(duì)列的變化。

從這排隊(duì)的過程中，我們是不是發(fā)現(xiàn)了冒泡排序的思想：

第一遍，第一個(gè)位置上的同學(xué)開始，挨個(gè)的比較身高，如果第0個(gè)位置的同學(xué)比第1個(gè)位置的同學(xué)高，就交換位置，否則，不換位置，然后，第1個(gè)位置與第2個(gè)位置的同學(xué)比一下身高，如果第1個(gè)位置的同學(xué)高比第2個(gè)位置的同學(xué)高，交換位置，否則不換，以此類推，最高的同學(xué)將會到最后一個(gè)位置上。

第二遍，還是從第一個(gè)位置上的同學(xué)開始，第1個(gè)同學(xué)和第2個(gè)同學(xué)比較，如果第一個(gè)同學(xué)比第二個(gè)同學(xué)高，交換位置，否則不變，然后，第2個(gè)位置上的同學(xué)和第3個(gè)位置的同學(xué)比較，如果第2個(gè)位置的同學(xué)高，則交換位置，否則不換。這一遍，因?yàn)榈谝槐橐呀?jīng)找出來最高的同學(xué)在最后一個(gè)位置，所以最后一個(gè)位置不用比較了。

直到隊(duì)列全部排好為止。

到這里，我想你應(yīng)該明白了冒泡排序的思想了。

接下來，我們看一下代碼的實(shí)現(xiàn)（這里我們使用Java代碼實(shí)現(xiàn)）。

public static void bubbleSort(int[] arr) {
        //如果數(shù)組為空，或者元素為1，直接返回。
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int e = 0; e < arr.length - 1; e++) {//每次最大元素就像氣泡一樣"浮"到數(shù)組的最后
            for (int i = 0; i < n-1-e; i++) {//n-1-e:-1是因?yàn)樵貜?下表開始，-e是因?yàn)榭梢詼p去已排到最后的幾個(gè)元素，可以減少比較次數(shù)。
                if (arr[i] > arr[i + 1]) {//如果大于下一個(gè)位置
                    swap(arr, i, i + 1);//交換位置
                }
            }
        }
    }

    /**
     * 交換元素位置
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

性能分析

最差時(shí)間復(fù)雜度：O(n^2)
最優(yōu)時(shí)間復(fù)雜度：如果已經(jīng)是有序的,可以把最優(yōu)時(shí)間復(fù)雜度降低到O(n)
平均時(shí)間復(fù)雜度：O(n^2)
所需輔助空間：O(1)
穩(wěn)定性：穩(wěn)定
穩(wěn)定性說明：排序穩(wěn)定不穩(wěn)定，就是看每次排序的過程中，是否會改變整個(gè)序列的位置。

文章有不當(dāng)之處，歡迎指正，如果喜歡微信閱讀，你也可以關(guān)注我的微信公眾號：好好學(xué)java，獲取優(yōu)質(zhì)學(xué)習(xí)資源。