文章目录
前言一、归并排序介绍（代码在大标题二）1.1 思路1.2 基本流程
二、代码总结
前言
本文继续排序算法的回顾。本文主要是针对归并排序进行分析，分别从递归的角度和分治的角度对归并进行认识，并附上c++的实现
一、归并排序介绍（代码在大标题二）
同样，这里我们以一个乱序数组为例。有数组 a[5]
a[0]a[1]a[2]a[3]a[4]
32710
len = 5 startIndex = 0 endIndex = n - 1 = 5 - 1 = 4
1.1 思路
归并排序的中心思路可以概括为从局部有序到整体有序。具体来说，就是可以将原数组进行分割（分治），分别进行运算（递归），实现局部有序，然后通过一个外排进而实现整体有序。
1.2 基本流程
结合a[5]，就是先将数组切成两半 然后进行局部的排序，并借助两个指针实现外排（借助辅助数组，a和b中的较小值填入辅助数组，并且右移，直到其中一个指针遍历了其所在的子数组的全部元素，结束并将另外的数组的剩余元素全部拷贝到辅助数组），进而实现整体有序。（图片这里仅展示了第一次分治的过程，实际上伴随着递归，子数组也会被再一次分治，外排，直到无法进行分割，直观来说，就是辅助数组被构建了logN次） 最后将辅助数组数据拷贝到原数组即可。
时间复杂度分析：
子数组元素的数量是原数组元素的数量的一半 T(N) = 2T(N/2)此外，外派的复杂度为O(N)，故有 T(N) = 2T(N/2) + O(N)根据Master公式有 log(b, a) > d 复杂度为O(N^log(b, a) ) log(b, a) = d 复杂度为O((N^d) * logN) log(b, a) < d 复杂度为O(N^d ) 所以有归并的时间复杂度为：O(N*logN)
二、代码
#include <iostream>
#include <vector>
using namespace std
;
void Merge(vector
<int> &v
, int start
, int mid
, int end
)
{
vector
<int> temp(end
- start
+ 1, 0);
int i
= 0;
int p1
= start
;
int p2
= mid
+ 1;
while (p1
<= mid
&& p2
<= end
)
{
temp
[i
++] = v
[p1
] < v
[p2
] ? v
[p1
++] : v
[p2
++];
}
while (p1
<= mid
)
{
temp
[i
++] = v
[p1
++];
}
while (p2
<= end
)
{
temp
[i
++] = v
[p2
++];
}
for (i
= 0; i
< temp
.size(); i
++)
{
v
[start
+ i
] = temp
[i
];
}
}
void SortProcess(vector
<int> &v
, int start
, int end
)
{
if (start
== end
)
{
return;
}
int mid
= start
+ ((end
- start
) >> 1);
SortProcess(v
, start
, mid
);
SortProcess(v
, mid
+ 1, end
);
Merge(v
, start
, mid
, end
);
}
void MergeSort(vector
<int> &v
)
{
if (v
.size() < 2)
{
return;
}
SortProcess(v
, 0, v
.size()-1);
}
int main()
{
vector
<int> v
= { 3,2,7,1,0 };
for (int i
= 0; i
< v
.size(); i
++)
{
cout
<< v
[i
] << "\t";
}
cout
<< endl
;
MergeSort(v
);
for (int i
= 0; i
< v
.size(); i
++)
{
cout
<< v
[i
] << "\t";
}
cout
<< endl
;
system("pause");
return 0;
}
总结
笔者在回顾的时候，这段编码还是错误挺多次的，主要问题出现在Merge函数部分，即辅助数组构建时候出了问题，究其原因，主要是对递归的理解不到位。总结来讲，归并排序的各个阶段不难理解，但是当这些内容串联起来是容易犯一些错误。
