看完了這篇，面試的時候人人都能單手擼冒泡排序！

2020 年 11 月 11 日
筆記

雞湯給大家備好了：

歲月流逝是多麼殘酷啊，對我們也是如此，不要把時間浪費在不重要的人和事情上！

在電腦科學中，排序是一個經典的主題。學習排序演算法的好處有三：

1.創造性解決問題

2.練習和鞏固程式設計技能

3.演示演算法性能的極好例子

冒泡排序屬於比較簡單的一種排序方法。但是，很多同學到現在也不能手寫一個冒泡排序。甚至經過和一些剛畢業甚至工作一兩年的朋友交流後，發現他們內心對演算法，抱著深深的恐懼和盲目崇拜，覺得演算法好像高不可攀，只適合那些高學歷、高智商的人來學習和研究！今天，我想把這篇獻給他們，希望他們能樹立起學習的勇氣和信心！

1.什麼是冒泡排序

冒泡排序演算法需要遍歷幾次數組，在每次遍歷中，比較連續相鄰的元素。如果一對元素是降序排列，則互換他們的位置，否則保持不變。這樣一來，使得較小的值像「氣泡」一樣，逐漸浮向頂部，而較大的值沉入底部，因此稱這種排序方法為冒泡排序（bubble sort ）或下沉排序（sinking sort）。

第一次遍歷之後，最後一個元素將成為最大的元素。第二次遍歷之後，倒數第二個元素，將成為倒數第二大的元素。整個過程持續到所有的元素全部都已排好序。

2.圖解冒泡排序

經過第一次遍歷後，最大的數已經在數組末尾。因為最後一個數已經是最大數，因此不需要再考慮最後一對元素。

經過第二次遍歷，後兩個數已經排好序，所以只需要對除它們之外的元素進行排序。

因此，在進行第n次遍歷時，不需要考慮倒數第n-1個元素，因為它們已經排好序了！

冒泡排序偽程式碼：

for(int k = 1; k < list.length; k++){
    for(int j = 0; j < list.length-k; j++) {
        if(list[j] > list[j + 1]) {
            swap(list[i], list[i + 1]);
        }
    }
}

3.改進後的冒泡排序

注意到，上面的排序實際上有很多次沒有發生交換，因此，我們可以對冒泡排序稍微改進下：

boolean nextPass = true;
for(int k = 1; k < list.length && nextPass; k++){
    nextPass = false;
    for(int j = 0; j < list.length-k; j++) {
        if(list[j] > list[j + 1]) {
            swap(list[i], list[i + 1]);
            nextPass = true;
        }
    }
}

4. 冒泡排序時間複雜度

最佳情況下，冒泡排序只需要一次遍歷就能確定數組已排好序，不需要再進行下一次遍歷。因此，最佳情況下，冒泡排序時間複雜度為O(n)。

最壞情況下，冒泡排序需要次。因此比較總次數為:
$$
(n-1) + (n-2) + (n-3) + …+ 3 + 2 + 1 = ({\frac n2^2} – {\frac n2}) = O(n^2)
$$
所以，最壞情況下，冒泡排序的時間複雜度為:O(n^2)。

5. 附上函數

public static void bubbleSort(int[] list) {
    boolean nextPass = true;
    for(int k = 1; k < list.length && nextPass; k++){
        nextPass = false;
        for(int j = 0; j < list.length-k; j++) {
            if(list[j] > list[j + 1]) {
                int tmp = list[j];
                list[j] = list[j+1];
                list[j+1] = tmp;
                nextPass = true;
            }
        }
    }
}

如果你覺得文章還不錯，記得關注公眾號：鍋外的大佬
劉一手的部落格