C語言經典排序算法：冒泡、選擇、插入法詳解與代碼實現

引言

排序算法是計算機科學基石。本文詳細分析冒泡排序、選擇排序、插入排序三種基礎算法的原理、特點及C語言實現，幫助初學者建立扎實的算法思維。

一、冒泡排序

算法思想

對 n 個數進行 n-1 趟比較。第 j 趟比較 n-j 次相鄰元素，將最大值「沉底」移至末尾（升序），最小值沉底則為降序。

代碼實現

#include <stdio.h>

int main() {
    int a[10], i, j, t;
    printf("Please input 10 numbers: ");
    for (i = 0; i < 10; i++) scanf("%d", &a[i]);

    for (j = 0; j < 9; j++)          // 控制趟數
        for (i = 0; i < 9 - j; i++)  // 每趟比較次數
            if (a[i] > a[i+1]) {
                t = a[i];
                a[i] = a[i+1];
                a[i+1] = t;
            }

    printf("The sorted numbers: ");
    for (i = 0; i < 10; i++) printf("%d  ", a[i]);
    printf("\n");
    return 0;
}

特點

• 相鄰元素兩兩比較，每趟確定一個元素最終位置
• 位置確定順序從後向前
• 可實現升序/降序

二、選擇排序

算法思想

每趟從無序區選出最值與無序區首元素交換。n 個數需 n-1 趟。第 i 趟假設 i 為最值下標，向後掃描更新最值下標，最後交換。

代碼實現

#include <stdio.h>

int main() {
    int a[10], i, j, k, t, n = 10;
    printf("Please input 10 numbers: ");
    for (i = 0; i < 10; i++) scanf("%d", &a[i]);

    for (i = 0; i < n-1; i++) {
        k = i;                          // 假設當前為最值
        for (j = i+1; j < n; j++)     // 尋找真正最值
            if (a[k] < a[j]) k = j;   // 降序：找最大值
        if (k != i) {                   // 交換
            t = a[k]; a[k] = a[i]; a[i] = t;
        }
    }

    printf("The sorted numbers: ");
    for (i = 0; i < 10; i++) printf("%d  ", a[i]);
    printf("\n");
    return 0;
}

特點

• 每趟確定一個元素最終位置，順序從前向後
• 每趟最多一次交換，非最值元素相對位置不變

三、插入排序

算法思想

將序列分為有序區與無序區。初始有序區含首元素，每次從無序區取首元素插入有序區合適位置。查找插入位置時從有序區末尾向前掃描，同時後移元素騰出空位，合併查找與移動提高效率。

代碼實現

#include <stdio.h>

int main() {
    int a[10], i, j, t;
    printf("Please input 10 numbers: ");
    for (i = 0; i < 10; i++) scanf("%d", &a[i]);

    for (i = 1; i < 10; i++) {           // n-1 次插入
        t = a[i];                         // 暫存待插入值
        for (j = i-1; j >= 0 && t > a[j]; j--) // 從後向前找位置並後移
            a[j+1] = a[j];
        a[j+1] = t;                       // 插入
    }

    printf("The sorted numbers: ");
    for (i = 0; i < 10; i++) printf("%d  ", a[i]);
    printf("\n");
    return 0;
}

特點

• 元素最終位置在最後一趟才確定
• 查找與移動合併執行，效率較高
• 對近乎有序數據性能優異

總結對比

三種算法雖時間複雜度均為 O(n²)，但常數因子與適應性不同。實際工程中，小數組常用插入排序作為快速排序、歸併排序的基準情況優化。