归并排序

CSP-J · 编程模板 · 代码 · cpp · 难度 4/5 · 共 675 字

分治到单元素，再两两合并成有序段

排序
分治

前置内容

正文

// ── 归并排序：分治 + 合并 ──
// 稳定排序，O(n log n)
// 需要 O(n) 辅助空间
int tmp[100005];
void merge_sort(int a[], int l, int r) {
    // 单个元素不用排
    if (l >= r) return;
    int mid = (l + r) / 2;
    // 先排好左半
    merge_sort(a, l, mid);
    // 再排好右半
    merge_sort(a, mid + 1, r);
    // 左指针、右指针、写入位置
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        // 两头取小的写入；
        // 相等取左边 → 稳定性的来源
        tmp[k++] = a[i] <= a[j]
            ? a[i++] : a[j++];
    }
    // 左边剩下的直接搬
    while (i <= mid) tmp[k++] = a[i++];
    // 右边剩下的直接搬
    while (j <= r) tmp[k++] = a[j++];
    // 写回原数组
    for (int p = l; p <= r; p++)
        a[p] = tmp[p];
}
// 归并排序还能顺便数逆序对
// CSP 常考

归并排序

前置内容

正文

CSP-J · 编程模板的其它内容