【算法】归并排序

【算法】归并排序

Richard

2019 年 05 月 10 日

833 次浏览

暂无评论

1618字数

数据结构与算法

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；
- 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

##算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

来源：https://github.com/hustcc/JS-Sorting-Algorithm

##代码实现
```cpp
/*****************************************************************
Function:Merge Sort
Time complexities: O(n*logn)

P.S: 这里的参数都是左闭右开的;
*****************************************************************/

inline void MyMerge(int a[], int left, int mid, int right)
{
	int *tmp = new int[right - left]; //定义一个 tmp 辅助数组
	int lp = left, rp = mid; //lp 遍历左边的数，rp遍历右边的数
	int tp = 0;	//tp指向 tmp 中应写入的位置

while (lp < mid && rp < right)	//开始归并
	{
		if (a[lp] < a[rp])
			tmp[tp++] = a[lp++];
		else
			tmp[tp++] = a[rp++];
	}

while (lp < mid) //将剩余未归并的数归并进来
		tmp[tp++] = a[lp++];

while (rp < right) //同上
		tmp[tp++] = a[rp++];

for (int i = 0; i < right - left; i++)
		a[left + i] = tmp[i]; //复制回原数组

delete[] tmp; //new 完 delete 是个好习惯 :D

return;
}

void MergeSort(int a[], int begin, int end)
{
	if (begin >= end - 1)
		return; //递归出口

int mid = (begin + end - 1) / 2 + 1;

MergeSort(a, begin, mid);
	MergeSort(a, mid, end);

MyMerge(a, begin, mid, end);

return;
}
```

> 代码是我自己写的，前面的解释都是搬运[小吴师兄的文章](https://mp.weixin.qq.com/s/-SNtdnw6vPSq2Qs0S7y-eQ)的。里面有动图演示，看不懂可以去这里看。