2021-01-08

算法之冒泡排序

冒泡排序是面試經常問到的，之前在網上看到的冒泡排序都是雙層for循環來實作的，最近在看書，《資料結構與算法圖解》中，關于冒泡排序的寫法是while循環嵌套for循環的，我覺得這種寫法更加好了解，下面記錄下來，以供學習：

public static void main(String[] args) {
        //冒泡排序寫法
        int[] arr = {12,3,45,33,4,25};
        //index：表示：該索引之前的資料都沒排過序”。一開始整個數組都是沒排過序的，是以此變量指派為數組的最後一個索引
        int index = arr.length-1;
        //flag：被用來記錄數組是否已完全排好序。當然一開始它應該是False。
        boolean flag = false;

        /**
         * 接着是一個while循環，除非數組排好了序，不然它不會停下來。
         * 然後，我們先将flag初步設定為True。當發生任何交換時，我們會将其改為False。
         * 如果在一次輪回裡沒有做過交換，那麼flag就确定為True，我們知道數組已排好序了。
         */
        while (!flag) {
            flag = true;

            /**
             * 在while循環裡，還有一個for循環會疊代未排序元素的索引值。
             * 此循環中，我們會比較相鄰的元素，如果有順序錯誤，就會進行交換，并将flag改為False。
             */
            for (int i = 0; i < index; i++) {
                if(arr[i] > arr[i+1]) {
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    flag = false;
                }
            }
            /**
             * 到了這一行，就意味着一次輪回結束了，同時該次輪回中冒泡到右側的值處于正确位置。
             * 因為index所指的位置已放上了正确的元素，是以減1，以便下一次輪回能略過該位置
             */
            index = index-1;
        }
        //一次while循環就是一次輪回，循環會持續直至flag确定為True。

        //debug調試可以檢視arr已經是排序好（升序）
        System.out.println(arr);
    }