排序算法7——归并排序

【归并排序】

归并排序的算法思想：将两个或两个以上的元素有序序列合并为一个有序序列。其中，二路归并排序是最常见的归并排序。

【算法思想】

二路归并排序的主要算法思想是：假设元素个数是n，将每个元素作为一个有序的子序列。继续将相邻的两个有序子序列两两合并得到

个长度为2的有序子序列。继续将相邻的两个有序子序列两两合并，得到

个长度为4的有序的子序列。以此类推，直到有序序列合并为1个为止。这样，待待续元素序列就整体有序了。

【示例】

假设待排序元素序列为49，23，66，52，34，75，99，18。使用归并排序对该序列的排序过程如图所示。

初始时，可以将单个元素看作是一个有序的子序列，通过将两个相邻的子序列合并，子序列中元素个数就变成了两个，如此不断反复，直到子序列的个数只有一个，这样，待排序元素就构成了一个有序的序列。

code:

#include<stdio.h>
#include<malloc.h>
void CopyArray(int source[], int dest[], int len, int first);
void MergeSort(int a[], int left, int right);
void Merge(int a[], int left, int right);
void DispArray(int a[], int n);
void main()
{
	int a[] = { 49,23,66,52,34,75,99,18 };
	int len = sizeof(a) / sizeof(int);
	printf("排序前数组中的元素:\n");
	DispArray(a, len);
	MergeSort(a, 0, len - 1);
	printf("排序后数组中的元素:\n");
	DispArray(a, len);
	getchar();
}
void MergeSort(int a[], int left, int right)
/*归并排序*/
{
	int i;
	if (left < right)
	{
		i = (left + right) / 2;
		MergeSort(a, left, i);
		MergeSort(a, i + 1, right);
		Merge(a, left, right);
	}
}
void Merge(int a[], int left, int right)
/*合并两个子序列中的元素*/
{
	int begin1, begin2, mid, k = 0, len, *b;
	begin1 = left;
	mid = (left + right) / 2;
	begin2 = mid + 1;
	len = right - left + 1;
	b = (int*)malloc(len*sizeof(int));
	while (begin1 <= mid && begin2 <= right)
	{
		if (a[begin1] <= a[begin2])
			b[k++] = a[begin1++];
		else
			b[k++] = a[begin2++];
	}
	while (begin1 <= mid)
		b[k++] = a[begin1++];
	while (begin2 <= right)
		b[k++] = a[begin2++];
	CopyArray(b, a, len, left);
	free(b);
}
void CopyArray(int source[], int dest[], int len, int start)
/*将source数组中的元素复制到dest数组中.
其中,len是源数组长度,start是目标数组起始位置*/
{
	int i, j = start;
	for (i = 0; i<len; i++)
	{
		dest[j] = source[i];
		j++;
	}
}
void DispArray(int a[], int n)
/*输出数组中的元素*/
{
	int i;
	for (i = 0; i<n; i++)
		printf("%4d", a[i]);
	printf("\n");
}

           

结果：

【主要用途】

归并排序算法实现复杂，因为二路归并排序算法需要临时空间较大，所以常常用在外部排序中。

【稳定性和复杂度】

归并排序是一种稳定的排序算法。

二路归并排序的过程需要进行$\lceil log_2n \rfceil$趟。二路归并排序算法需要多次递归调用自己，其递归调用的过程可以构建一个二叉树的结构，它的时间复杂度为T(n)≤n+2T(n/2)≤n+2*(n/2+2*T(n/4))=2n+4T(n/4)≤3n+8T(n/8)≤...≤nlog_2n+nT(1)，即O(nlog_2n)。

二路归并排序的空间复杂度为O(n)。