萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C++ 合併排序實作(左閉右開區間,符合 STL 風格)

設計考量

《演算法導論》使用 1-based 索引與哨兵,但為配合 C++ STL 慣例,本實作採用 左閉右開區間 [p, r),統一長度計算、避免 +1/-1 易錯的邊界調整。

合併函數 merge

void merge(int* A, int p, int q, int r) { // 合併 [p, q) 和 [q, r)
    int n1 = q - p, n2 = r - q;
    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; ++i) L[i] = A[p + i];
    for (int i = 0; i < n2; ++i) R[i] = A[q + i]; // 注意:非 q+i+1

    int i = 0, j = 0, k = p;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else              A[k++] = R[j++];
    }
    while (i < n1) A[k++] = L[i++];
    while (j < n2) A[k++] = R[j++];

    delete[] L;
    delete[] R;
}

遞迴排序 merge_sort

void merge_sort(int* a, int p, int r) { // 呼叫介面:merge_sort(a, 0, len)
    if (p < r - 1) { // 區間長度 > 1
        int q = p + (r - p) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q, r); // 同樣用 [q, r)
        merge(a, p, q, r);
    }
}

測試主程式

int main() {
    srand(time(nullptr));
    int n;
    while (cin >> n) {
        int* a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = rand() % n;
        for (int i = 0; i < n; ++i) printf("%d ", a[i]);
        puts("");

        merge_sort(a, 0, n);

        for (int i = 0; i < n; ++i) printf("%d ", a[i]);
        puts("");

        delete[] a;
    }
    return 0;
}

驗證

經數萬組隨機測試,輸出結果與 std::sort 完全一致,確認正確性。

copyright © 萬盛學電腦網 all rights reserved