昨天我們講了排序的簡介和一些基本的排序法，今天我們要繼續來看其他的排序演算法 !
插入排序(Insertion Sort)
合併排序(Merge Sort)
快速排序(Quick Sort)

一、插入排序(Insertion Sort)

把陣列想像成分成「已排序」跟「未排序」兩部分，每次都從未排序部分拿一個元素，插入到已排序部分正確的位置。

程式碼

void insertionSort(int arr[], int n) {
    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]; // 比key大的往後移一格
            j--;
        }
        arr[j + 1] = key;// 找到正確位置插入
    }
}

根據上面例子想一遍

當 i = 1，key = 2，j = i-1 = 0
進 while迴圈 j >= 0且9 > 2，
所以把 9 往後搬：[9, 9, 14, 0]，然後再插入變成 [2, 9, 14, 0]

這段程式碼是不是有點眼熟?
回想 Day6 陣列 的 insert 函式 把後面的元素往後搬，騰出空位插入 的邏輯是一樣的，插入排序就是反覆執行陣列插入操作，只是每次插入的位置是「已排序部分裡正確的位置」，而不是任意指定的位置

二、合併排序(Merge Sort)

其實這段在Day 3 時間複雜度 也有簡單看過去喔，只是那時候只有看他的時間複雜度和他的程式碼而已，並沒有介紹完整概念

所以這邊要來繼續把它的概念寫清楚~

合併排序法是將陣列一直對半切拆成小元素後，再依序將已排序的子陣列合併
合併排序會用到 分治法(Divide and Conquer) 的概念

分治法(Divide and Conquer)

1. 分割(Divide) : 把陣列不斷對半切，直到每份只剩 1 個元素(1 個元素就是「已排序」的)
2. 合併(Merge) : 把切開的小陣列兩兩合併，合併的同時順便排好序，一路往回合併回完整的陣列

以 [17, 2, 28, 61, 35, 11, 73, 86]為例

先 Divide

再 Merge

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArr[n1], rightArr[n2];
    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

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

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;      

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);         
    mergeSort(arr, mid + 1, right);     
    merge(arr, left, mid, right);       
}

時間複雜度推導

• 分割層數 : 每次都對半分，切到剩 1 個元素，需要 層
• 每層合併 : 每一層加起來都要處理過全部 n 個元素一次
  

三、快速排序(Quick Sort)

概念和合併排序很像都是用 分治 的概念

每次選一個基準值(pivot)，把陣列分成「比pivot小」跟「比pivot大」兩部分(這個過程叫partition)，然後對這兩部分分別遞迴排序

可以寫成以下步驟

1. 選擇 Pivot
2. 將小於 Pivot 的元素放左邊
3. 將大於 Pivot 的元素放右邊
4. 對左右兩部分遞迴排序

平均情況: O(n log n)

如果每次選到的 pivot 都能把陣列 大致平均 地切成兩半 :

• 切的層數:每次都對半分，層
• 每層的工作量:每一層做partition，加起來都要處理過全部n個元素一次

(綠色為pivot)

最壞情況:O(n²)

如果每次選到的 pivot 都剛好是當時範圍裡最小值或最大值(例如陣列本身已經完全排序好，又每次都選第一個元素當pivot)，partition出來的結果會變成「一邊0個元素，一邊n-1個元素」，完全沒有把問題縮小規模 :

程式碼

void quickSort(int arr[], int left, int right) {
    if (left >= right)
        return;

    int pivot = arr[right];
    int i = left - 1;

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

    int pivotIndex = i + 1;
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

各排序比較

• 氣泡排序 (Bubble Sort)

  • 優點 : 邏輯直覺、實作簡單，資料已排序時可優化到接近 O(n)。
  • 缺點 : 平均與最壞情況效率都不好，實務上很少拿來用。

• 選擇排序 (Selection Sort)

  • 優點 : 每輪只需要交換一次，資料搬移成本低。
  • 缺點 : 不管資料多整齊，都得完整跑過找最小值的過程，且是不穩定排序。

• 插入排序 (Insertion Sort)

  • 優點：實作簡單，資料量小或幾乎已排序時效率極高（接近 O(n)，且無需額外記憶體空間。
  • 缺點：處理大規模未排序資料時效率不好。

• 合併排序 (Merge Sort)

  • 優點：效能穩定，無論輸入資料的分佈如何，時間複雜度恆定為 O(n log n)
  • 缺點：合併階段需要額外的 O(n) 輔助空間。

• 快速排序 (Quick Sort)

  • 優點：平均效能極佳，實際執行速度通常最快。
  • 缺點：若 Pivot 選擇不佳且資料已排序，會導致時間複雜度退化至 O(n²)。

那接下來，我們會進入搜尋演算法，看二分搜尋法跟插補搜尋法怎麼在已排序的資料裡快速找到目標值