數據結構 6 基礎排序演算法詳解冒泡排序、三層冒泡排序逐步優化方案詳解

2020 年 4 月 23 日
筆記
數據結構

前言

說到前面，我們已經詳解了幾種數據結構、包括數組、鏈表、二叉樹、B樹、B+樹等基本數據結構、當然，我們這節課也叫做數據結構與演算法、肯定會包含演算法的相關知識、因為在之前已經了解和學習過有關時間複雜度的相關內容。當然也是和演算法密切相關的。時間複雜度和空間複雜度共同決定一個演算法的好壞、本節，我們將學習有關數組元素排序的幾種常用演算法。以及使用圖畫的方式展示出來。為了我們更好的理解與使用。

冒泡排序

聽這個名字可以大概猜到。就像湖底水草上面的水泡一樣，從水底到水面的一個過程。就是排序的其中一輪。我們來畫圖理解一下：

假設我們有這樣一個長度的數組：需要將元素 順序排列（從小到大）

指定一個本輪循環的元素j 與 j+1 元素 進行比較。若大於則換位。

這裡明顯 49>38 調換位置。

指針位移，再次開始與 i+1 個元素比較；

65>49 很顯然，不進行換位。下移一位。

97>65 則不進行換位。位移下一位。

發現這裡需要進行換位操作。因為97>76

位移下一位。

比較後，進行換位操作。

位移下一位。。。。這裡省略步驟到最後一步我們會發現

當指針到達(len-1)位置的時候，其實已經比較完了。所以我們通過這一輪的冒泡排序。一個最大的元素已經被確認出來了。

重複以上的過程，從第二個元素繼續開始。再次重複這樣的過程。實現排序。

下次的終止位置。則只需要比較到上一次位置-1處即可。

JAVA 程式碼示例。

第一版

int[] arrays = {49, 38, 65, 97, 76, 13, 27, 49};

public static void sort1(int[] arrays) {

    int allChange = 0;
    for (int i = 0;i<arrays.length;i++) {

        for (int j = 0 ;j<arrays.length-i-1;j++) {

            if (arrays[j] > arrays[j+1]) {

                int temp = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1] = temp;

            }
            allChange++;
        }
        System.out.println(Arrays.toString(arrays));
    }

    System.out.println("總比較次數："+allChange);
}

第一版的冒泡排序通過兩個FOR 循環的形式實現

外層 for循環用於控制整體程式的運行次數。也就是數組的長度。
內層 for用於與後面一位數比較大小。從而實現交換的邏輯。

如此一來，第一版冒泡排序的時間複雜度為 O(N的平方)

[38, 49, 65, 76, 13, 27, 49, 97]
[38, 49, 65, 13, 27, 49, 76, 97]
[38, 49, 13, 27, 49, 65, 76, 97]
[38, 13, 27, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
----------------------------------注意這段分隔符的意義
[13, 27, 38, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
總比較次數：28

第二版

通過觀察控制台的輸出，我們發現，其實在循環進行到第5次的時候，其實數組已經變得井然有序了。但是我們的演算法仍然兢兢業業的做4次無用功。所以這裡就是一個需要優化的地方。

通過加入一個isChange的變數。用來記錄本次循環是否發生了變化。若沒有發生元素的交換。則後面的循環直接跳出即可。

int[] arrays = {49, 38, 65, 97, 76, 13, 27, 49};

public static void sort2(int[] arrays) {

    int allChange = 0;

    for (int i = 0; i < arrays.length; i++) {

        boolean isChange = true;

        for (int j = 0; j < arrays.length - i - 1; j++) {

            if (arrays[j] > arrays[j + 1]) {

                int temp = arrays[j];
                arrays[j] = arrays[j + 1];
                arrays[j + 1] = temp;

                isChange = false;
            }
            allChange++;
        }
        System.out.println(Arrays.toString(arrays));
        if (isChange) {
            break;
        }
    }
    System.out.println("總比較次數："+allChange);
}

通過控制台輸出的內容我們不難發現。其實循環在第五次的時候，已經完成了元素的交換，但是為何又輸出了一遍？

[38, 49, 65, 76, 13, 27, 49, 97]
[38, 49, 65, 13, 27, 49, 76, 97]
[38, 49, 13, 27, 49, 65, 76, 97]
[38, 13, 27, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
--------------------------------
[13, 27, 38, 49, 49, 65, 76, 97]

其實在第四遍走完後，排序已經是完成了的。但是因為不知道下次時候會有元素的交換，所以在此走了一遍，因為沒有交換元素，則在第五遍執行完畢後，跳出循環。

再次優化，有序長度的界定

何謂有序長度的界定呢？我們重新選擇一個數組來列印一次，發現這裡面需要優化的位置點。

選定一個特殊數組：[3,4,2,1,5,6,7,8]

通過短暫的觀察，我們可以發現，5,6,7,8 這幾位元素已經是處於一個有序的狀態的。那麼我們現有的演算法，怎麼去對於這些有序序列的比較。從而優化性能呢？我們先用這個數組來跑一遍

[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
------------------------
[1, 2, 3, 4, 5, 6, 7, 8]

通過測試後發現，現有的演算法對於數據的比較只需要三次即可排列好這個數組，但是我們會發現。在執行第一遍的時候，若遇到一些有序的元素。

例如：第一遍已經產生的 [4, 5, 6, 7, 8] 演算法還是在第二遍執行的時候，重複進行了比較。我們能不能想個辦法。跳過這些重複的內容呢？

我們可以控制內層比較的長度啊！！！

想要跳過一些元素的比較，那麼就需要得到這個有序內容的長度。從而控制第二層循環，不要比較這些有序長度即可。

如何確定有序長度。

當然是若發生比較的時候，

    public static void sort3(int[] array) {

        //用來記錄最後一次發生變化的位置
        int lastChangeIndex = 0;
        //用來表示需要比較的長度。只需要比較到之前即可
        int sortLength = array.length - 1;

        int allChange = 0;

        for (int i = 0; i < array.length; i++) {

            boolean isChange = true;

            for (int j = 0;j< sortLength;j++) {

                if (array[j] > array[j + 1]) {

                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = false;
                    //記錄發生變化的位置
                    lastChangeIndex = j;
                }
                //用於記錄比較次數
                allChange++;
            }
            sortLength = lastChangeIndex;
            System.out.println(Arrays.toString(array));
            //若無改變則跳出循環
            if (isChange) {
                break;
            }
        }
        System.out.println("總比較次數："+allChange);
    }

最終我們得出，我們的演算法只需要運行10次比較。即可排序完成。再來看看我們第二版本的演算法次數

--------------------- 第三版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總比較次數：10

----------------------第二版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總比較次數：22
----------------------第一版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總比較次數：28

小結

通過一次一次的優化，使得我們的冒泡排序從最初的比較次數28，通過加入有無調換順序的判斷後優化為22 再到記錄有序序列的下標。變為更優化的10次。是演算法優化的結果，也是我們在慢慢進步的效果。

下節課我們將學習到一個更加優化的排序演算法。雞尾酒排序

Tags: 數據結構