數據結構實驗：六大排序算法 C++ 實現與性能實測對比

數據結構實驗：六大排序算法 C++ 實現與性能實測對比

本實驗實現並測試六種經典排序算法：選擇、插入、冒泡、快速、改進快速、兩路歸併。使用 clock() 計時，對 100 個隨機整數排序，記錄耗時對比優劣。代碼採用模板泛型，可直接復用於任意可比較類型。

算法實現精華

選擇排序 O(n²)

template 
void SelectSort(T A[], int n) {
    for (int i = 0; i < n; ++i) {
        int small = i;
        for (int j = i + 1; j < n; ++j)
            if (A[j] < A[small]) small = j;
        swap(A[i], A[small]);
    }
}

直接插入排序 O(n²)、近乎有序時 O(n)

template 
void InsertSort(T A[], int n) {
    for (int i = 1; i < n; ++i) {
        T tmp = A[i];
        int j = i;
        while (j > 0 && tmp < A[j-1]) {
            A[j] = A[j-1];
            --j;
        }
        A[j] = tmp;
    }
}

改進冒泡排序：記錄最後交換位置縮小範圍

template 
void BubbleSort(T A[], int n) {
    int i = n - 1, last;
    while (i > 0) {
        last = 0;
        for (int j = 0; j < i; ++j)
            if (A[j+1] < A[j]) {
                swap(A[j], A[j+1]);
                last = j;
            }
        i = last; // 之後區間已有序
    }
}

標準快速排序（霍爾分區）

template 
void QSort(T A[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right + 1;
    do {
        do ++i; while (A[i] < A[left]);
        do --j; while (A[j] > A[left]);
        if (i < j) swap(A[i], A[j]);
    } while (i < j);
    swap(A[left], A[j]);
    QSort(A, left, j-1);
    QSort(A, j+1, right);
}

改進快速排序：小區間改用插入排序（閾值 9）

template 
void MagicQSort(T A[], int left, int right) {
    if (right - left + 1 < 9) { // 閾值經驗值
        InsertSort(A + left, right - left + 1);
        return;
    }
    // 同標準快排分區邏輯...
}

兩路歸併排序（迭代版，自底向上）

template 
void Merge(T A[], int i1, int j1, int i2, int j2) {
    T *tmp = new T[j2 - i1 + 1];
    int i = i1, j = i2, k = 0;
    while (i <= j1 && j <= j2)
        tmp[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];
    while (i <= j1) tmp[k++] = A[i++];
    while (j <= j2) tmp[k++] = A[j++];
    for (int t = 0; t < k; ++t) A[i1++] = tmp[t];
    delete[] tmp;
}

template 
void MergeSort(T A[], int n) {
    for (int size = 1; size < n; size <<= 1) {
        for (int i1 = 0; i1 < n; ) {
            int i2 = i1 + size;
            if (i2 >= n) break;
            int j1 = i2 - 1;
            int j2 = min(i2 + size - 1, n - 1);
            Merge(A, i1, j1, i2, j2);
            i1 = j2 + 1;
        }
    }
}

主程式：隨機生成、計時、輸出

int main() {
    srand(time(NULL));
    const int n = 100;
    int *a = new int[n], *b = new int[n], *c = new int[n];
    int *d = new int[n], *e = new int[n], *f = new int[n];
    
    for (int i = 0; i < n; ++i) {
        a[i] = rand() % 91;
        b[i] = c[i] = d[i] = e[i] = f[i] = a[i];
    }
    
    auto test = [&](const char* name, int* arr, void(*sort)(int*, int)) {
        clock_t st = clock();
        sort(arr, n);
        clock_t ed = clock();
        printf("%s: %.6fs\n", name, (double)(ed - st) / CLOCKS_PER_SEC);
    };
    
    test("SelectSort", a, SelectSort);
    test("InsertSort", b, InsertSort);
    test("BubbleSort", c, BubbleSort);
    test("QuickSort", d, QuickSort);
    test("MergeSort", e, MergeSort);
    test("MagicQuickSort", f, MagicQuickSort);
    
    // 釋放記憶體...
    return 0;
}

典型輸出與分析（100 元素，隨機分佈）

結論：小規模（<50）插入排序極具競爭力；通用場景改進快排綜合最優；需穩定排序選歸併。實驗代碼模板化，可直接擴展至大規模測試或自定義類型。