归并排序算法详解及C++代码实现

归并排序算法详解及C++代码实现

引用

CSDN

1.

https://blog.csdn.net/Chenqin1879/article/details/140875935

归并排序是一种采用分治策略进行排序的算法，其核心思想是将一个大规模的问题分解为若干规模较小的相同子问题，然后逐个解决这些子问题，最后将结果合并。对于排序问题而言，这意味着将待排序的无序序列分解为两个规模大致相等的子序列，如果子序列仍然较大，则继续分解，直到每个子序列只包含一个元素（因为单个元素的序列本身就是有序的）。此时，就可以开始合并这些有序子序列，逐步构建出完整的有序序列。

以序列（42，15，20，6，8，38，50，12）为例，归并排序的过程如下图所示：

从上图可以看出，归并排序首先将待排序元素分成大小大致相同的两个子序列，然后将子序列继续分成更小的子序列，直到每个子序列只包含一个元素。接着，算法开始执行合并操作，将两个有序的子序列合并成一个有序序列，如此反复，直到所有元素都合并为一个完整的有序序列。

下面是归并排序的完整C++代码实现：

#include<bits/stdc++.h>
using namespace std; 

// 合并两个有序子序列的函数
void merge(int A[], int low, int mid, int high) {
    int *B = new int[high - low + 1]; // 申请一个动态数组进行辅助
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) { // 按从小到大的顺序放入辅助数组中
        if (A[i] <= A[j])
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }
    while (i <= mid) B[k++] = A[i++]; // 将数组中剩下的元素放入辅助数组中
    while (j <= high) B[k++] = A[j++];
    for (i = low, k = 0; i <= high; i++, k++) { // 将排序好的辅助数组复制到原数组中
        A[i] = B[k];
    }
    delete[] B; // 释放内存空间
}

// 分解序列并递归排序的函数
void mergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2; // 取中点
        mergeSort(A, low, mid); // 对A[low：mid]中的元素合并排序
        mergeSort(A, mid + 1, high); // 对A[mid+1:high]中的元素合并排序
        merge(A, low, mid, high); // 合并
    }
}

int main() {
    int a[1005];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    mergeSort(a, 0, n - 1); // 调用归并排序函数
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}

这段代码首先定义了一个merge函数，用于合并两个有序子序列。然后定义了mergeSort函数，用于递归地将序列分解为更小的子序列，并最终调用merge函数进行合并。最后，在main函数中读取用户输入的序列，调用mergeSort函数进行排序，并输出排序后的结果。