選擇排序法

更新於 2025/03/06發佈於 2025/03/06閱讀時間約 5 分鐘

前導

選擇排序（Selection Sort），是在每輪遍歷中找到最小（或最大）值，並將其放到正確位置。

演算法流程

首先從待排序部分中選擇最小值（或最大值），將其與目前排序範圍的第一個元素交換，也可以說將經過比較後選出的最小值放入a[0]中，再從未排序的範圍找出最小值，然後放入a[1]中。而a[1]中的數字理所當然小於a[0]，依此類推，即實現了選擇排序。

實際範例

假設一原始陣列如下:

[64, 25, 12, 22, 11]

排序步驟：

第一次迭代循環（i = 0）：
- 未排序區域：[64, 25, 12, 22, 11]
- 找出最小值：11（在索引 4）
- 交換：將 11 與索引 0 的 64 互換
- 結果：[11, 25, 12, 22, 64]
第二次迭代循環（i = 1）：
- 未排序區域：[25, 12, 22, 64]（索引 1 到 4）
- 找出最小值：12（在索引 2）
- 交換：將 12 與索引 1 的 25 互換
- 結果：[11, 12, 25, 22, 64]
第三次迭代循環（i = 2）：
- 未排序區域：[25, 22, 64]（索引 2 到 4）
- 找出最小值：22（在索引 3）
- 交換：將 22 與索引 2 的 25 互換
- 結果：[11, 12, 22, 25, 64]
第四次迭代循環（i = 3）：
- 未排序區域：[25, 64]（索引 3 到 4）
- 找出最小值：25（已在正確位置）
- 無需交換
- 結果：[11, 12, 22, 25, 64]
第五次迭代循環（i = 4）：
- 剩下一個元素：[64]，已排序完成

最終排序結果:

[11, 12, 22, 25, 64]

程式碼

#include <stdio.h>

// 選擇排序函式
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { 
        int minIndex = i; // 記錄最小值的索引

        // 在未排序部分尋找最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值索引
            }
        }

        // 交換最小值到正確位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 輔助函式：列印陣列
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主程式
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("排序後: ");
    printArray(arr, n);
    return 0;
}