2021-01-29

C/C++ selection sort 選擇排序法

本篇 ShengYu 介紹 C/C++ 中的選擇排序法 selection sort，並且由 C/C++ 來實作選擇排序法 selection sort。

如果不想自己刻一個排序法可以使用現成 C 提供的 qsort 或 C++ STL 標準函式庫提供的 std::sort。
以下開始介紹選擇排序的原理，

選擇排序法 selection sort 基本原理

選擇排序法 selection sort 的原理是先在所有資料中挑選出一個最小的數值放在放在第一個，再從第二個到尾端的資料中挑選出一個最小的數值放在第二個，這樣一直迭代下去，最終將能獲得排序好的升序串列(由小到大)，
讓我來舉個簡單的例子吧！假如今天有一串數字串列 10 8 6 2 4 要使用選擇排序 selection sort，

第一次迴圈排序結果如下，所以第一次迴圈就從全部資料挑選出最小的數值 1 給交換放到第一個了，剩餘要排序的數值還有 4 個，

1	2 8 6 10 4

第二次迴圈排序結果如下，第二次迴圈就從第二個到尾端挑選出最小的數值 2 給交換放到第二個了，剩餘要排序的數值還有 3 個，

1	2 4 6 10 8

第三次迴圈排序結果如下，第三次迴圈就從第三個到尾端挑選出最小的數值 3 給交換放到第三個了，剩餘要排序的數值還有 2 個，

1	2 4 6 10 8

第四次迴圈排序結果如下，第四次迴圈就從第四個到尾端挑選出最小的數值 4 給交換放到第四個了，剩餘要排序的數值還有 1 個，

1	2 4 6 8 10

迴圈結束，排序完成，

C/C++ 實作選擇排序法 selection sort

由上述的簡單例子推演可以了解了選擇排序 selection sort 基本原理後，接著就開始練習用 C/C++ 來寫程式，那我們來看看 C/C++ 選擇排序怎麼寫吧！

cpp-selection-sort.cpp

// g++ cpp-selection-sort.cpp -o a.out
#include <stdio.h> 

void selection_sort(int array[], int n) {
    for (int i=0; i<n-1; i++) {
        int min_idx = i;
        for (int j=i+1; j<n; j++) {
            if (array[j] < array[min_idx]) {
                min_idx = j;
            }
        }
        // swap
        int temp = array[min_idx];
        array[min_idx] = array[i];
        array[i] = temp;
    }
}

int main() {
    int array[] = {10,8,6,2,4};
    printf("排序前 = ");
    for (int i=0; i<5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    selection_sort(array, 5);

    printf("排序後 = ");
    for (int i=0; i<5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

C/C++ 程式跑出來的結果如下，經過選擇排序法 selection sort 排序後的結果的確是由小排到大。

1 2	排序前 = 10 8 6 2 4 排序後 = 2 4 6 8 10