C 語言排序演算法實作：插入排序與選擇排序完整範例

程式碼完整實作

#include <stdio.h>

// 插入排序
void sortArray(int p[], int n);
void insert(int p[], int a, int b);

// 選擇排序
void selectedSort(int p[], int n);
void swap(int *p1, int *p2);

// 陣列大小常數
#define ARRAY_COUNTS 9

int main() {
    int a[] = {1, 3, 8, 2, 6, 5, 7, 4, 9};
    sortArray(a, ARRAY_COUNTS);
    printf("插入排序結果：");
    for (int i = 0; i < ARRAY_COUNTS; i++) {
        printf("%3d", a[i]);
    }
    printf("\n");

    int b[] = {1, 3, 8, 2, 6, 5, 7, 4, 9};
    selectedSort(b, ARRAY_COUNTS);
    printf("選擇排序結果：");
    for (int i = 0; i < ARRAY_COUNTS; i++) {
        printf("%3d", b[i]);
    }
    printf("\n");
    return 0;
}

// 插入排序主邏輯
void sortArray(int p[], int n) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // 找到插入位置
            if (p[i] < p[j]) {
                insert(p, j, i);
            }
        }
    }
}

// 插入操作：將 p[b] 插入到 p[a] 位置，後續元素後移
void insert(int p[], int a, int b) {
    int temp = p[b];
    while (a < b) {
        p[b] = p[b - 1];
        b--;
    }
    p[a] = temp;
}

// 選擇排序主邏輯
void selectedSort(int p[], int n) {
    int index;
    for (int i = 0; i < n; i++) {
        index = i;
        // 尋找最小值索引
        for (int j = i + 1; j < n; j++) {
            if (p[index] > p[j]) {
                index = j;
            }
        }
        // 交換到正確位置
        swap(&p[i], &p[index]);
    }
}

// 交換兩個整數值
void swap(int *p1, int *p2) {
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

演算法解析

插入排序

• 核心思想：將陣列分為「已排序」與「未排序」兩部分，每次從未排序取出一個元素，插入已排序區的適當位置。
• 時間複雜度：平均/最差 O(n²)，最佳 O(n)（近乎有序時）。
• 空間複雜度：O(1)，原地排序。
• 穩定性：穩定排序。

選擇排序

• 核心思想：每輪在未排序區找出最小值，與未排序區首位元素交換。
• 時間複雜度：固定 O(n²)，與資料分布無關。
• 空間複雜度：O(1)。
• 穩定性：不穩定（交換操作可能改變相等元素相對順序）。

關鍵點提醒

1. C 語言無參考傳遞，swap 必須傳指標 int *。
2. 插入排序的 insert 函式以「後移元素」實現空出插入位置。
3. 選擇排序每輪只交換一次，寫入次數少於插入排序。

本文轉載自 “小宇2013” 博客，原文出處：請與作者聯系