C++中的合并排序与实例

合并排序遵循分而治之的方法。

分意味着将一个问题分解为许多小的子问题。

治意味着递归地解决这些小的子问题，然后重新组合它们以创建原始问题的解决方案。

该方法MergeSort()将数组分成相等的部分，直到每个元素分离为止，然后该方法Merge()将它们重新组合，同时每次将它们连接到两个数组时对它们进行排序，就以排序的方式将它们连接起来，以便得到最终的排序数组。

C ++合并排序程序

#include <iostream>

using namespace std;

//合并两个数组
void Merge(int A[], int p, int q, int r)
{
    //的大小
    int n1 = q - p + 1, i, j, k;

    //n2是R []
    int n2 = r - q;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)

    {
        L[i] = A[p + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = A[q + j + 1];
    }

    i = 0, j = 0;

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

    /*
        如果l[]比r[]有更多的元素，那么它就会变成。
        将l[]的所有元素都放到a[]
    */
    while (i < n1) {
        A[k++] = L[i++];
    }

    //如果R []的元素多于L []，则它将全部
    //R []的重定义元素到A []
    while (j < n2) {
        A[k++] = R[j++];
    }
}

//它将划分数组并排序
//他们合并时
void MergeSort(int A[], int p, int r)
{
    int q;

    if (p < r) {
        //q是划分数组的中间元素
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

int main(){
    //A_Size为A []的大小
    int A_Size;

    cout << "//输入元素数量： ";

    cin >> A_Size;

    int A[A_Size];

    cout << "//输入数组元素： ";

    for (int i = 0; i < A_Size; i++) {
        cin >> A[i];
    }

    MergeSort(A, 0, A_Size - 1);

    for (int i = 0; i < A_Size; i++) {
        cout << A[i] << " ";
    }

    cout << endl;

    return 0;
}

输出结果

First Run:
//输入元素数量： 5
//输入数组元素： 10 30 12 56 60
10 12 30 56 60

Second Run:
//输入元素数量： 10
//输入数组元素： 10 20 50 60 77 88 34 43 1 45
1 10 20 34 43 45 50 60 77 88