C++ 排序算法大全：從插入到基數，原理、實現與實測性能對比

系統實現並測試主流內部排序算法，統一測試框架記錄關鍵碼比較次數 (KCN) 與記錄移動次數 (RMN)，在 10,000/100,000 整數隨機/有序/逆序數據下量化性能，揭示理論復雜度與實際運行的差異。

統一測試框架

template <class T>
void test(T a[], int N, void(*sort)(T[], int, int&, int&)) {
    int KCN=0, RMN=0; clock_t t = clock();
    sort(a, N, KCN, RMN);
    cout << "Time: " << clock()-t << "ms\n"
         << "KCN=" << KCN << " KCN/N=" << (double)KCN/N
         << " KCN/N²=" << (double)KCN/N/N
         << " KCN/NlogN=" << (double)KCN/N/log2(N) << "\n"
         << "RMN=" << RMN << " RMN/N=" << (double)RMN/N
         << " RMN/N²=" << (double)RMN/N/N
         << " RMN/NlogN=" << (double)RMN/N/log2(N) << endl;
}

測試數據：升序、降序、隨機排列（固定種子保證可比性）。

1. 插入排序類

直接插入排序 O(N²)

void InsertSort(T a[], int N, int& KCN, int& RMN) {
    for (int i=1; i<N; i++) {
        T tmp = a[i]; RMN++;
        int j; for (j=i; j>0 && ++KCN && tmp < a[j-1]; j--) { a[j]=a[j-1]; RMN++; }
        a[j] = tmp; RMN++;
    }
}

測試：升序 0ms (KCN≈N)，隨機 330ms (KCN≈N²/4)，降序 711ms (KCN≈N²/2)。最好/最壞/平均符合理論。

表插入排序（靜態鏈表）

移動指針而非記錄，RMN 極低（理論最大 3(N-1)），但平均耗時反超直接插入（整數移動開銷極小，指針操作額外負擔）。適合大記錄、鏈表結構。

希爾排序（縮小增量）

void ShellSort(T a[], int N, int& KCN, int& RMN) {
    for (int gap=N/2; gap; gap/=2)
        for (int i=gap; i<N; i++) {
            T tmp=a[i]; RMN++;
            for (int j=i; j>=gap && ++KCN && tmp<a[j-gap]; j-=gap)
                { a[j]=a[j-gap]; RMN++; }
            a[j]=tmp; RMN++;
        }
}

測試 (10萬)：升序 140ms，隨機 230ms，降序 151ms。無明顯最壞情況，附加空間 O(1)，在不明數據分布時是優於快排的穩健選擇。

2. 交換排序類

起泡排序 O(N²)

優化：設置 exchange 標誌，無交換提前結束。測試：升序 0ms (KCN=N)，隨機 1161ms，降序 1022ms。效率低於直接插入，教學價值大於實用。

快速排序 O(N log N) 平均，O(N²) 最壞

核心 Partition：單趟掃描確定樞軸最終位置。

int Partition(T a[], int L, int R, int& KCN, int& RMN) {
    int pos = L; T piv = a[L];
    for (int i=L+1; i<=R; i++)
        if (++KCN && a[i] < piv && ++pos != i)
            { swap(a[i], a[pos]); RMN+=3; }
    swap(a[L], a[pos]); RMN+=3;
    return pos;
}
void QSort(T a[], int L, int R, int& KCN, int& RMN) {
    if (L < R) {
        int p = Partition(a, L, R, KCN, RMN);
        QSort(a, L, p-1, KCN, RMN);
        QSort(a, p+1, R, KCN, RMN);
    }
}

測試：隨機 10萬僅 110ms (KCN≈21N)，但升序/降序 10萬耗時 42秒！最壞情況極其危險。

優化：三數取中

取首、中、末中位數作樞軸。升序/降序改善明顯，但代碼複雜，隨機選樞軸效果更好且簡單：

swap(a[L], a[rand(R-L)+L]); // 隨機樞軸

隨機快排測試 (10萬)：升序 90ms，隨機 120ms，降序 110ms。質的飛躍，消除最壞情況，工程首選。

3. 選擇排序類

直接選擇排序 O(N²)

KCN 固定 N(N-1)/2，RMN 極小 (0~3N)。測試三種數據耗時接近 (711ms)，CPU 流水線優化使比較密集型代碼表現優於移動密集型。

堆排序 O(N log N) 穩定

void FilterDown(T a[], int i, int N, int& KCN, int& RMN) {
    int c = 2*i+1; T tmp = a[i];
    while (c < N) {
        if (c+1= a[c]) break;
        a[i] = a[c]; RMN++; i = c; c = 2*i+1;
    }
    a[i] = tmp; RMN++;
}
void HeapSort(T a[], int N, int& KCN, int& RMN) {
    for (int i=(N-2)/2; i>=0; i--) FilterDown(a, i, N, KCN, RMN); // 建堆
    for (int i=N-1; i>0; i--) { swap(a[0], a[i]); RMN+=3; FilterDown(a, 0, i, KCN, RMN); }
}

測試 (10萬)：升序 110ms，隨機 160ms，降序 90ms。無最壞情況，附加空間 O(1)，不信任快排時的最佳替代。

4. 歸併排序與基數排序（補充）

• 歸併排序：O(N log N) 穩定，需 O(N) 輔助空間，適合鏈表/外部排序。
• 基數排序：O(d(N+r))，非比較排序，整數/字符串固定長度鍵值極快，但通用性受限。

性能總結與選擇指南

關鍵洞察

1. 隨機快排是工程通用首選：簡單、快、平均性能極佳，隨機樞軸消除最壞情況風險。
2. 希爾排序是小規模/嵌入式最優：無遞歸、O(1) 空間、代碼極短、無最壞情況。
3. 堆排序是硬實時系統保底：嚴格 O(N log N) 保證，無遞歸棧溢出風險。
4. CPU 流水線影響實測：比較密集（選擇排序）常快於移動密集（插入排序），理論 RMN 不等於實際耗時。
5. 穩定性需業務決定：多關鍵字排序、保持相對順序時必須用穩定排序（歸併、基數、插入）。

排序無銀彈，理解數據特徵（規模、分布、鍵類型、穩定性要求、內存限制）才能做最優選擇。