博客

归并排序是建立在归并操作山的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

基本思想：

将待排序的元素序列分成两个长度相等的子序列，对每一个子序列排序，然后将他们合并成一个序列。合并两个子序列的过程称为二路合并。

归并排序的核心步骤：

• 
  分组
  
• 
  合并
  

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//归并排序合并过程
void Merge(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	assert(a&&tmp);
	int begin = begin1;
	int index = begin1;//从begin1的地方合并
	//和两条有序单链表的合并的过程类似
	while ((begin1 <= end1) && (begin2 <= end2))
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	//把剩余的合并到tmp上
	while (begin1 <= end1)
		tmp[index++] = a[begin1++];
	while (begin2 <= end2)
		tmp[index++] = a[begin2++];
	//tmp是个临时空间，最后到把合并的内容拷贝到a上
	memcpy(a + begin, tmp + begin, sizeof(int)*(end2 - begin + 1));
}

//归并排序分开过程
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	assert(a&&tmp);
	int mid = begin + (end - begin) / 2;
	//只有一个元素，说明这个序列已经有序
	if (begin == end)
		return;
	//子问题划分左子序列
	_MergeSort(a, begin, mid, tmp);
	//子问题划分右子序列
	_MergeSort(a, mid + 1, end, tmp);
	//合并两个有序数组
	Merge(a, begin, mid, mid + 1, end, tmp);
}
//归并排序
void MergeSort(int* a, int n)
{
	if (a == NULL || n <= 0)
		return;
	//开辟临时空间，用来存放每次合并后的子序列
	int* tmp = (int*)malloc(sizeof(int)*n);
	_MergeSort(a, 0, n - 1, tmp);
	//释放空间
	free(tmp);
	tmp = NULL;
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = { 14, 12, 15, 13, 11, 16 };
	MergeSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

运行结果如下：

归并排序的特性总结：

1. 
   归并的缺点在于需要O(N)的空间复杂度
   
2. 
   时间复杂度：O(N*logN)
   
3. 
   空间复杂度：O(N)
   
4. 
   稳定性：稳定
   

各排序算法比较

插入排序和希尔排序的实现：

https://blog.csdn.net/Damn_Yang/article/details/86524253

选择排序和堆排序的实现：

https://blog.csdn.net/Damn_Yang/article/details/86530835

冒泡排序和快读排序的实现：

https://blog.csdn.net/Damn_Yang/article/details/86541054