[Algorithm] 排序演算法

排序演算法在電腦科學中相當常用，畢竟無論是誰都需要整理資料，因為有序的資料通常能更有效率地查詢、分析與處理。
而排序演算法一般有幾項重要的評估指標：

執行效率：一般期望排序演算法的時間複雜度能低，且操作總體次數能少，這點尤其體現在資料量大的時候。
就地性：是否需要額外的儲存空間來進行排序，若需要額外空間，則會增加記憶體的使用量，所以一般希望排序時事不要再額外使用太多空間。舉例來說，array 排序可以就該 array 本身進行排序，而不是再開一個新的 array 來存放排序後的結果 (除非實務上要做資料備份)。
穩定性：當兩個元素的排序鍵相同時，排序後它們的相對順序會不會被改變。這有點抽象，所以看一下範例：
- 假設有三個學生資料，要使用分數來排序，但 Alice 和 Charlie 的分數都是 90 分，所以符合排序鍵相同的條件。
- 原始資料中，Alice 在 Charlie 之前，所以在穩定排序的結果中，Alice 仍然會在 Charlie 之前。

// 原始資料
(Alice, 90)
(Bob, 80)
(Charlie, 90)

// 穩定排序結果
(Bob, 80)
(Alice, 90)
(Charlie, 90)

適應性：指的是當輸入資料已經部分排序時，排序演算法是否能夠利用這個特性，減少不必要的比較或交換，從而提高整體執行效率。
多使用「比較」：在排序演算法中，通常會進行元素之間的比較來決定它們的順序。「比較」排序通常較為通用且比「不比較」的排序更有時間效率。

泡泡排序 (Bubble Sort)

泡泡排序是一種簡單且直觀的排序演算法，其基本原理是通過多次比較相鄰元素，將較大的元素逐漸「冒泡」到序列的末端 (或較小的元素冒泡到序列的前端，這也是泡泡排序)。
取名「泡泡排序」就是因為這種把較大元素逐漸移動到序列末端的過程，類似於水中的氣泡上升的過程，呃，就一種程式開發者的浪漫。

以 array 舉例，泡泡排序會從陣列的第一個元素開始，依次比較相鄰的兩個元素，如果前一個元素大於後一個元素，則交換它們的位置。這樣一來，經過一輪比較後，最大的元素就會被移動到陣列的最後一個位置。接著，對剩下的元素重複這個過程，直到整個陣列排序完成。

以陣列 [4, 1, 3, 1, 5, 2] 為例，使用泡泡排序的過程如下 (僅記錄交換位置的步驟)：

第一輪比較：
- 比較 4 和 1，交換位置 → [1, 4, 3, 1, 5, 2]
- 比較 4 和 3，交換位置 → [1, 3, 4, 1, 5, 2]
- 比較 4 和 1，交換位置 → [1, 3, 1, 4, 5, 2]
- 比較 5 和 2，交換位置 → [1, 3, 1, 4, 2, 5]
第二輪比較：
- 比較 3 和 1，交換位置 → [1, 1, 3, 4, 2, 5]
- 比較 4 和 2，交換位置 → [1, 1, 3, 2, 4, 5]
第三輪比較：
- 比較 3 和 2，交換位置 → [1, 1, 2, 3, 4, 5]

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = {4, 1, 3, 1, 5, 2};

        // check elements of array before sort
        System.out.println("Array before sort: ");
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");

        // Array after sort
        bubbleSorting(arr);
        System.out.println("Array after sort: ");
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
     }

    static void bubbleSorting(int[] array) {
        int arrayLength = array.length;

        // 外迴圈每執行一次都把最大數值放到右邊
        for (int i = 0; i < arrayLength; i++) {
            // 設定一個 flag，用來判斷當兩兩比較都已經排序完成，就終止後續的迴圈 (無用迴圈)
            boolean isSwap = false;


            // 內迴圈檢查相鄰兩數做交換
            // `- 1 - i` 是因為最右邊 i 個順序已經固定，不需要加入排序
            // 有沒有再 `- i` 其實也能得到正確結果，但就是多跑一些無用迴圈步驟，理論效率變低，但時間複雜度是一樣的
            for (int j = 0; j < arrayLength - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j]; // 暫存一下較大的數值
                    array[j] = array[j + 1]; // 把較小的數值前挪
                    array[j + 1] = temp; // 把剛剛存的較大數值丟給右邊

                    // 表示這一次迴圈內依然有需要排序的情況
                    isSwap = true;
                }
            }

            // 某次迴圈兩兩比較完，發現都沒排序，即可終止後續迴圈
            if (!isSwap) {
                break;
            }
        }
    }
}

泡泡排序 (Bubble Sort)​

泡泡排序 (Bubble Sort)