合并排序
1、基本思路
1）分解：将n个元素的数组分成含n/2 个元素的子序列；
2）求解：用合并排序法对每个子序列递归地进行排序；
3）合并：合并已经完成排序子序列。
伪代码如下：
mergesort(A,p,r)
if p<r
q = floor((p+r)/2)
mergesort(A,p,q)
mergesort(A,q+1,r)
merge(A,p,q,r)
merge(A,p,q,r)
n1=q-p+1
n2=r-q
create array L[1,2,...,n1+1] and R[1,2,...,n2+1]
for i=1 to n1
L[i] = A[p+i-1]
for i = 1 to n2
R[i] = A[q+i]
L[n1+1] = +inf
R[n2+1] = +inf
i = 1
j = 1
for k=p to r
if L[i]<=R[j]
A[k] = L[i]
i = i+1
else
A[K] = R[j]
j = j+1
2、C++代码
#include<limits.h>
#include<algorithm>
//using namespace std;
void merge(int* A, const int p, int q, int r)
{
//确定两个子数组的长度
int n1 = q - p + 1;
int n2 = r - q;
//开辟临时内存空间
int* L = new int[n1 + 1];
int* R = new int[n2 + 1];
//将子数组复制到开辟的空间中
for (int i = 0; i < n1; ++i)
L[i] = A[p + i ];
for (int i = 0; i < n2; ++i)
R[i] = A[q + i + 1];
L[n1 ] = INT_MAX;
R[n2 ] = INT_MAX;
int i = 0;
int j = 0;
//合并，类似于两堆牌，比较牌堆顶部的两张牌，小的先放入结果中。
for (int k = p; k <= r; ++k)
if (L[i] <= R[j])
A[k] = L[i++];
else
A[k] = R[j++];
}
void mergesort(int* A, int p, int r)
{
if (p < r)
{
int q = floor((p + r) / 2);
mergesort(A, p, q);
mergesort(A, q + 1, r);
merge(A, p, q, r);
}
}
int main()
{
int A[6] = { 5,3,2,4,1,0};
int p = 0;
int r = 5;
mergesort(A, p, r);
return 0;
}
