冒泡排序 vs 選擇排序：交換次數差異與性能分析

代碼對比

// 冒泡排序：相鄰比較，大數逐步「冒泡」到末尾
for (int i = n-1; i > 0; i--)
    for (int j = 0; j < i; j++)
        if (a[j+1] < a[j]) swap(a[j], a[j+1]);

// 你的寫法（實為選擇排序）：每輪選出最大值放到末尾
for (int i = n-1; i > 0; i--)
    for (int j = i-1; j >= 0; j--)
        if (a[i] < a[j]) swap(a[i], a[j]);

核心區別

你的觀測解釋

數組 {2,6,4,7,0,1,3,4,5,8,9,0} 中冒泡交換 26 次，選擇交換 21 次。選擇排序**交換次數顯著少於冒泡**，因每輪僅將最終確定的最大值與當前位置交換一次。

性能結論

• CPU 中交換（內存讀寫）比比較（寄存器運算）慢得多，故選擇排序在小規模數據上通常更快。
• 但兩者均為 O(N²)，實際工程中**極少直接使用**，優先選 std::sort（Introsort，O(N log N)）、qsort 或語言內置排序。
• 冒泡排序唯一優勢：代碼極簡、原地排序、穩定，適合教學或極小數據量（<50）且近乎有序場景。

你寫的其實是**選擇排序**變體，而非冒泡排序，理解兩者差異有助於選擇合適算法。