C語言三大經典排序算法：冒泡、選擇、插入排序深度解析

概述

本文詳細分析 C 語言中三種基礎排序算法——冒泡排序、選擇排序、插入排序的原理、代碼實現、特點與適用場景，所有範例均以 10 個整數為對象演示。

一、冒泡排序

算法思想

• 進行 n-1 趟比較，第 j 趟比較 n-j 次相鄰元素。
• 每趟將最大值（升序）或最小值（降序）「沉底」到無序區末尾。
• 確定元素位置的順序是**從後往前**。

代碼實現（升序）

#include 

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++)           // n-1 趟
        for (i = 0; i < 9 - j; i++)   // 第 j 趟比較 n-j 次
            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;
}

特點

• 相鄰兩兩比較，交換次數多，效率較低（O(n²)）。
• 可優化：若某趟無交換則提前結束。
• 穩定排序（相等元素相對位置不變）。

二、選擇排序

算法思想

• 每趟從無序區選出最大值（降序）或最小值（升序），與無序區第一個元素交換。
• 共 n-1 趟，第 i 趟假設 a[i] 為最值，向後掃描找出真正最值下標 k，若 k != i 則交換。
• 確定元素位置的順序是**從前往後**。

代碼實現（降序）

#include 

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;
}

特點

• 每趟**最多一次交換**，移動次數少於冒泡排序。
• 不穩定排序（交換可能改變相等元素相對順序）。
• 時間複雜度同為 O(n²)，但實際運行通常快於冒泡。

三、插入排序

算法思想

• 將序列分為「有序區」（初始只有第一個元素）與「無序區」。
• 依次從無序區取出第一個元素，插入有序區適當位置。
• 尋找插入位置時從有序區末尾向前掃描，**邊找邊後移元素**，找到位置後一次性插入。
• 共 n-1 次插入，元素最終位置在**最後一趟**才確定。

代碼實現（降序）

#include 

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++) {           // 從第 2 個元素開始插入
        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)**（已有序時僅比較不移動），適合近乎有序的小規模數據。
• 穩定排序。
• 就地排序，空間複雜度 O(1)。

三算法對比總結

實務建議

• 實際工程中對中大規模數據應優先考慮 qsort（快速排序）、歸併排序、堆排序等 O(n log n) 算法。
• 理解這三種基礎算法有助於掌握分治、遞歸、原地排序等核心思想。