当前位置：首页 > article >正文

分治算法归并排序

article 2024/11/15 22:58:16

分治算法

基本概念

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的基本步骤

分治法在每一层递归上都有三个步骤：

step1分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3合并：将各个子问题的解合并为原问题的解。

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治)策略(分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
在这里插入图片描述

代码如下：

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int is1[N], is2[N]; // `is1` 为主数组，`is2` 为辅助数组

// 合并两个有序子数组的函数
void merge(int low, int mid, int high) {
    int i = low, j = mid + 1, k = low; // 初始化 i, j, k 指针

    // 合并两个有序子数组
    while (i <= mid && j <= high) {
        if (is1[i] < is1[j]) {
            is2[k++] = is1[i++]; // 左子数组元素更小，拷贝到辅助数组
        }
        else {
            is2[k++] = is1[j++]; // 右子数组元素更小，拷贝到辅助数组
        }
    }

    // 处理左子数组剩余元素
    while (i <= mid) {
        is2[k++] = is1[i++];
    }

    // 处理右子数组剩余元素
    while (j <= high) {
        is2[k++] = is1[j++];
    }

    // 将辅助数组中的合并结果拷贝回主数组
    for (int i = low; i <= high; i++) {
        is1[i] = is2[i];
    }
}

// 归并排序递归函数
void mergesort(int l, int r) {
    if (l >= r) {
        return; // 如果子数组长度为1或无效，直接返回
    }

    int mid = (l + r) >> 1; // 计算中间索引
    mergesort(l, mid);      // 递归排序左半部分
    mergesort(mid + 1, r);  // 递归排序右半部分
    merge(l, mid, r);       // 合并两个有序子数组
}

int main() {
    int n;
    cin >> n; // 输入数组长度

    // 输入数组元素
    for (int i = 1; i <= n; i++) {
        cin >> is1[i];
    }

    // 归并排序
    mergesort(1, n);

    // 输出排序后的数组
    for (int i = 1; i <= n; i++) {
        cout << is1[i] << ' ';
    }
    cout << endl;

    return 0;
}

代码模板

// 合并排序函数
void merge_sort(int q[], int l, int r)
{
    // 如果子数组只有一个元素或为空，则无需排序
    if (l >= r) return;
    // 计算中间点
    int mid = l + r >> 1;
    // 递归地排序左半部分
    merge_sort(q, l, mid);
    // 递归地排序右半部分
    merge_sort(q, mid + 1, r);
    // 定义临时数组用于合并
    int k = 0, i = l, j = mid + 1;
    int tmp[r - l + 1]; // 临时数组大小为当前处理的子数组大小
    // 合并两个已排序的子数组
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; // 将较小的元素放入临时数组
        else tmp[k ++ ] = q[j ++ ]; // 将较小的元素放入临时数组
    // 将左半部分剩余的元素添加到临时数组
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    // 将右半部分剩余的元素添加到临时数组
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    // 将临时数组中的元素复制回原数组
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}