排序算法7 - 归并排序

归并排序（Merge Sort）就是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，......，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为二路归并排序。

可以看到这种结构很像一棵完全二叉树，归并排序可以采用递归实现也可采用迭代的方式实现。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4, 5, 7, 8]和[1, 2, 3, 6]两个已经有序的子序列，合并为最终序列[1, 2, 3, 4, 5, 6, 7, 8]，来看下实现步骤。

动图演示：

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

// 递归实现
void Merging(int *left, int left_size, int *right, int right_size)
{
	int i, j, k;
	int temp[MAXSIZE];

	i=j=k=0;

	while(i<left_size && j<right_size)
	{
		if(left[i]<right[j])
		{
			temp[k++]=left[i++];
		}
		else
		{
			temp[k++]=right[j++];
		}
	}

	while(i<left_size)
	{
		temp[k++]=left[i++];
	}
	while(j<right_size)
	{
		temp[k++]=right[j++];
	}

	for(i=0; i<(left_size+right_size); i++)
	{
		left[i]=temp[i];
	}
}

void MergeSortRecursive(int k[], int n)
{
	if(n>1)
	{
		int *left = k;
		int left_size = n/2;
		int *right = k+left_size;
		int right_size = n-left_size;

		MergeSortRecursive(left, left_size);
		MergeSortRecursive(right, right_size);

		Merging(left, left_size, right, right_size);
	}
}

// 迭代实现
void MergeSort(int k[], int n)
{
	int i, left_min, left_max, right_min, right_max, next;
	int *temp = (int *)malloc(n*sizeof(int)); // 临时数组

	for(i=1; i<n; i*=2) // 从两个元素相互合并到4,8,16个 
	{
		for(left_min=0; left_min<n-i; left_min=right_max)
		{
			right_min = left_max = left_min+i;
			right_max = left_max+i;

			if(right_max>n) // 超出数组长度则强制等于数组长度
			{
				right_max = n;
			}

			next = 0;

			while(left_min<left_max && right_min<right_max)
			{
				if(k[left_min]<k[right_min])
				{
					temp[next++] = k[left_min++];
				}
				else
				{
					temp[next++] = k[right_min++];
				}
			}

			while(left_min<left_max)
			{
				k[--right_min] = k[--left_max];
			}

			while(next>0) // 临时存储的数有序放回到原来的数组
			{
				k[--right_min] = temp[--next];
			}
		}
	}
}


int main(void)
{

	int i;
	int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	//MergeSortRecursive(a, 10);
	MergeSort(a, 10);

	printf("排序后的结果是：");
	for(i=0; i<10; i++)
	{
		printf("%d", a[i]);
		if(i!=9)
		{
			printf(",");
		}
	}
	printf("\n");
	return 0;
}