演算法-常見的排序演算法與其平均時間複雜度

氣泡排序法(Bubble Sort)

氣泡排序法的一個常見口訣是「相鄰比較，交換位置」。每個詞都代表了氣泡排序的一個關鍵步驟：

1. 相鄰比較（Compare Adjacent）：比較相鄰的兩個元素，並根據排序規則確定它們的順序。
2. 交換位置（Swap）：如果相鄰的兩個元素的順序不符合排序規則，則交換它們的位置。
3. 重複上述步驟，對數列中的所有元素進行相鄰比較和位置交換，直到整個數列排序完成。

平均時間複雜度為: O(n²)

選擇排序法(Selection Sort)

常見口訣是「尋找最小，交換位置」。每個詞都代表了選擇排序的一個關鍵步驟

1. 尋找最小（Find Minimum）：從未排序部分的數列中尋找最小的元素。
2. 交換位置（Swap）：將找到的最小元素與未排序部分的第一個元素交換位置。
3. 重複上述步驟，繼續尋找最小元素並進行交換，直到整個數列排序完成。

平均時間複雜度為: O(n²)

插入排序法(Insertion Sort)

插入排序法的一個常見口訣是「一一插入，保有順序」。每個詞都代表了插入排序的一個關鍵步驟：

1. 一一插入（Insert One by One）：從未排序部分的數列中逐一選取元素，並將其插入到已排序部分的正確位置。
2. 保有順序（Maintain Order）：在插入元素時，確保已排序部分的元素仍保持升序或降序的順序。
3. 重複上述步驟，繼續逐一插入元素，直到整個數列排序完成。

    public static void InsertionSortAlgorithm(int[] arr)
    {
        int n = arr.Length;

        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

平均時間複雜度為: O(n²)

合併排序法(Merge Sort)

合併排序法的一個常見口訣是「分而治之」。

合併排序的主要思想是通過分治的策略，將數列不斷分割成更小的部分，然後將這些部分按照順序合併起來，形成一個有序序列。合併排序具有穩定性和較好的時間複雜度，特別適用於處理較大規模的數列排序。

    public static void MergeSortAlgorithm(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;

            MergeSortAlgorithm(arr, left, middle);
            MergeSortAlgorithm(arr, middle + 1, right);

            Merge(arr, left, middle, right);
        }
    }

    private static void Merge(int[] arr, int left, int middle, int right)
    {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
        {
            leftArr[i] = arr[left + i];
        }

        for (int j = 0; j < n2; j++)
        {
            rightArr[j] = arr[middle + 1 + j];
        }

        int k = left;
        int p = 0;
        int q = 0;

        while (p < n1 && q < n2)
        {
            if (leftArr[p] <= rightArr[q])
            {
                arr[k] = leftArr[p];
                p++;
            }
            else
            {
                arr[k] = rightArr[q];
                q++;
            }

            k++;
        }

        while (p < n1)
        {
            arr[k] = leftArr[p];
            p++;
            k++;
        }

        while (q < n2)
        {
            arr[k] = rightArr[q];
            q++;
            k++;
        }
    }

平均時間複雜度為: O(n log n)

快速排序法(Quick Sort)

常見口訣是「選基、劃分、遞迴」。每個詞都代表了快速排序的一個關鍵步驟

1. 選基（Choose Pivot）：從數列中選擇一個基準點（pivot）。
2. 劃分（Partition）：將數列劃分為兩個部分，一部分是小於等於基準點的元素，另一部分是大於基準點的元素。
3. 遞迴（Recursion）：對劃分後的兩個部分進行遞迴排序，重複上述步驟，直到排序完成。

    public static void QuickSortAlgorithm(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int partitionIndex = Partition(arr, left, right);

            QuickSortAlgorithm(arr, left, partitionIndex - 1);
            QuickSortAlgorithm(arr, partitionIndex + 1, right);
        }
    }

    private static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }

        Swap(arr, i + 1, right);
        return i + 1;
    }

    private static void Swap(int[] arr, int i, int j)
    {
        (arr[i], arr[j]) = (arr[j], arr[i]);
    }

平均時間複雜度為: O(n log n)

---

其他少聽/用過的排序

希爾排序法(Shell Sort)

插入排序法的改良，幾乎所有狀況都能比O(n²)來得快

堆積排序法(Heap Sort)

平均時間複雜度為: O(n log n)

桶排序法(Bucket Sort)

非比較排序，平均時間複雜度為: O(n+k)

基數排序法(Radix Sort)

同屬非比較排序