C 語言指針數組冒泡排序優化：字符串排序實戰

C 語言指針數組冒泡排序優化：字符串排序實戰

對字符串陣列排序，若直接交換字符串內容（strcpy），開銷極大。標準做法：指針數組存儲字符串地址，排序時僅交換指針，避免內存搬移。本文演示優化版冒泡排序（提前結束標誌位）對 char* 陣列排序。

一、 核心代碼

#include <stdio.h>
#include <string.h>

int main() {
    char *str[] = {"hello", "change", "world", "come", "on"};
    int size = sizeof(str) / sizeof(str[0]);

    for (int i = 0; i < size - 1; i++) {
        int swapped = 0; // 優化標誌位
        for (int j = 0; j < size - 1 - i; j++) {
            if (strcmp(str[j], str[j+1]) > 0) { // 字典序比較
                char *tmp = str[j];
                str[j] = str[j+1];
                str[j+1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 本輪無交換，已有序，提前結束
    }

    for (int i = 0; i < size; i++) printf("%s ", str[i]);
    // 輸出: change come hello on world
    return 0;
}

二、 關鍵優化點

1. 指針交換：char *tmp = str[j]; str[j] = str[j+1]; ... 僅 3 次指針賦值，O(1)，不涉及字符拷貝。
2. 提前結束：swapped 標誌位，最好情況（已有序）僅 1 趟掃描 O(N)。
3. 縮小內層範圍：j < size - 1 - i，每輪最大元素「冒泡」到末尾，無需重複比較。

三、 複雜度分析

四、 實務建議

• 小規模（N < 50）冒泡排序可接受，代碼簡單。
• 大規模必須用 qsort（快速排序）、std::sort（C++）、TimSort 等 O(N log N) 演算法。
• 字符串排序永遠交換指針，切勿交換內容。