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

算法设计-归并排序（C++）

article 2025/2/12 22:40:17

一、简述

归并排序是一种基于分治法的高效排序算法，其核心思想是将数组分成两个子数组，分别排序后再合并。

二、详细代码

#include <iostream>
using namespace std;

void Merge(int arr[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[p + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[q + 1 + j];
    }

    int i = 0, j = 0, k = p;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) { // 保持稳定性
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

void MergeSort(int arr[], int p, int r) {
    if (p < r) { // 递归基 case
        int q = (p + r) / 2;
        MergeSort(arr, p, q);
        MergeSort(arr, q + 1, r);
        Merge(arr, p, q, r);
    }
}

int main() {
    int size;
    cout << "Enter size: ";
    cin >> size;
    int* arr = new int[size];

    for (int i = 0; i < size; i++) {
        cout << "arr element: ";
        cin >> arr[i];
    }

    int p = 0; // 从 0 开始
    int r = size - 1; // 结束为 size - 1
    MergeSort(arr, p, r);

    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

三、详细说明

Merge功能

Merge 函数用于合并两个已排序的子数组 arr[p..q] 和 arr[q+1..r]。

参数

arr[]：待排序的数组。
p：子数组的起始索引。
q：子数组的中间索引。
r：子数组的结束索引。

变量

n1：左子数组的长度，n1 = q - p + 1。
n2：右子数组的长度，n2 = r - q。
L 和 R：临时数组，分别存储左子数组和右子数组。
i, j, k：循环变量，分别用于遍历左子数组、右子数组和原数组。

算法步骤

将左子数组 arr[p..q] 复制到临时数组 L。
将右子数组 arr[q+1..r] 复制到临时数组 R。
合并 L 和 R 到原数组 arr：
- 比较 L[i] 和 R[j]，将较小的元素放入 arr[k]。
- 如果 L[i] <= R[j]，则放入 L[i]（保持稳定性）。
- 否则，放入 R[j]。
将剩余的元素（如果有）从 L 或 R 复制到 arr。
释放临时数组 L 和 R 的内存。