我们直接对代码进行分析：
void MERGE_SORT(int A[], int p, int r){ //分离数据树
int q;
q = (p + r) / 2;
if (r - p > 3){
MERGE_SORT(A, p, q);
MERGE_SORT(A, q + 1, r);
}
MERGE(A, p, q, r); //排序
}
划分区间，注意数组下标从0开始！p,r为划分数组的起始下标和最后一个元素的下标，，q为中间下标,q大于5时进行归并排序，小于5时进行插入排序（当个数较少时，用插入排序可以减少递归调用的空间使用，且其效率较高）
具体排序过程：
void MERGE(int A[], int p, int q, int r){ //排序
if (r - p > 3){
int n1, n2, i = 0, j = 0, k; //当p=0,q=4,r=9时
int *L, *R;
L = new int[NUM];
R = new int[NUM];
n1 = q - p + 1; //n1=5
n2 = r - q; //n2=5
for (i = 0; i < n1; i++){
L[i] = A[p + i]; //A[0]开始到A[4]赋给左边数组L[0]到L[4]
}
for (j = 0; j < n2; j++){
R[j] = A[q + j + 1]; //A[5]开始到A[9]赋给右边数组R[0]到L[4]
}
L[n1] = MAX; //设置哨兵
R[n2] = MAX; //设置哨兵
i = j = 0;
for (k = p; k <= r; k++){ //k=p=0,r=9,使十个数都排列到A[]中
if (L[i] <= R[j]){ //当L[i]比R[j]小时，把L[i]放到A[K]中，反之亦然
if (j != n2){ //R[j]不等于标志位
A[k] = L[i];
i++;
}
else{
for (; k <= r; k++){ //R[j]等于标志位时，把剩余的L[i]放到A中
A[k] = L[i];
i++;
}
}
}
else{
if (i != n1){
A[k] = R[j];
j++;
}
else{
for (; k <= r; k++){
A[k] = R[j];
j++;
}
}
}
}
delete[]L; //释放空间
delete[]R;
}
else{ //插入排序
int temp, i;
for (int j=p+1; j <= r; j++){
temp = A[j];
i = j - 1;
while (i >= p && A[i] > temp){
A[i + 1] = A[i];
i--;
A[i + 1] = temp;
}
}
}
}
这种排序方法就像把一副扑克牌分成两份（牌面向下放置），然后每次从两叠牌上方各抽一张比较，按顺序叠放合并。就是一个完全二叉树向上合并过程。
具体排序过程（已加入测试方法，具体见源代码）：
--------分治法：归并排序加插入排序---------
请输入排序数值：
18 12 26 7 28 2 24 23 22 1 20 16 19 3·
本次测试数组大小：
0 13 //p=0,r=13
--------------------------------------------
左区间: 0 6 //第一次划分区间（大于5，继续划分）
左区间: 0 3
//第二次划分区间（小于5，进入插入排序）
测试插入排序情况：
7 12 18 26
右区间: 4 6 //完成左区间，进入右区间划分，同理进行排序，注意，这里是对区间【4,6】进行操作
测试插入排序情况： //对区间【4,6】进行操作,3个数据，插排
7 12 18 26 2
24 28 //插排完成，返回数据后长度为7（>5），接着进行并归排序
测试并归排序情况：
2 7 12 18 24
26 28
右区间: 7 13 //对后7个元素进行同样处理
左区间: 7 10
测试插入排序情况： //这里排的是23 22 20 1
2 7 12 18 24
26 28 1 20 22 23
右区间: 11 13
测试插入排序情况：
2 7 12 18 24
26 28 1 20 22
23 3 16 19
测试并归排序情况：
2 7 12 18 24
26 28 1 3 16
19 20 22 23 //前7个数据与后7个再次归并排序
测试并归排序情况：
1 2 3 7 12
16 18 19 20 22
23 24 26 28 //已经完成排序
结果：1 2 3 7 12 16 18 19
20 22 23 24 26 28
请按任意键继续. . .
利用分治法，可以大大减少重复比较，但相对地带来了较大的空间开销，利用插入排序等其他原址排序能够很好地减少空间开销。其运行时间主要有：
分解：计算中间值，需要常量时间：
。
解决：分解为规模为n/2的问题需要2T(n/2)运行时间。
合并：在n个元素需要的时间
需要时间的递归式：T(n)=2T(n/2)+cn;
其时间复杂度为：
最后附上源代码：https://github.com/LRC-cheng/Algorithms_Practise.git
网友评论