文 | 莫若吻

一、簡介

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。
這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

二、原理

（升序排列為例）
1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)。
3.針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

三、原理過程圖

相鄰兩個(gè)元素進(jìn)行比較，如果符合條件換位。
第一圈：最值出現(xiàn)在了最后位。后面以此類推。（如下圖）

冒泡排序.png

四、時(shí)間復(fù)雜度

若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù) C和記錄移動(dòng)次數(shù)M均達(dá)到最小值：

Paste_Image.png

。所以，冒泡排序最好的時(shí)間復(fù)雜度為: O(n)。
　　若初始文件是反序的，需要進(jìn)行 n-1趟排序。每趟排序要進(jìn)行 n-i次關(guān)鍵字的比較(1≤i≤n-1)，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：

Paste_Image.png

綜上，因此冒泡排序總的平均時(shí)間復(fù)雜度為 ** O(n2)** 。

五、性能分析（穩(wěn)定性）

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，不會交換；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來，這時(shí)候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

六、示例代碼（Java）：

1.核心代碼

/*
    冒泡排序：相鄰兩個(gè)元素進(jìn)行比較，如果符合條件換位。
    第一圈：最值出現(xiàn)在了最后位。
    */

    public static void bubbleSort(int[] arr)
    {
        for(int x=0; x<arr.length-1; x++)
        {                   
            for(int y=0; y<arr.length-x-1; y++)
            {   //y代表數(shù)組角標(biāo)。-x:讓每一次比較的元素減少，-1：避免角標(biāo)越界。     
                if(arr[y]<arr[y+1])
                {
                    int temp = arr[y];
                    arr[y] = arr[y+1];
                    arr[y+1] = temp;
                }
            }
        }
    }

2.選擇排序與冒泡排序相關(guān)示例

選擇排序.png

冒泡排序.png

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請必須注明出處，謝謝！