排序算法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)。