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