归并排序算法的理解

浏览数：25 / 时间：2015年06月08日

归并排序：先对两个有序的系列进行合并，合并的时候不断的对两个系列的第一个元素进行比较，把较小的那个移动到最前面成为了第一个元素，那么移动的元素后面的元素就是成为了下次比较的序列的第一个元素，如此不断的取两个系列的第一个元素进行比较。

1 4 5 6 2 7 8 9 第一轮1与2比较 1比2小，那么1被移动了 4成为了下次要比较的元素了

那么下一轮就是比较4和2 2小就被移动了那么再次比较的就是4和7了如此一轮一轮的比较。

//merge two array：对两个有序列进行合并
void merge(int a[], int temp[], int first, int mid, int end)
{
	int i = first, j = mid + 1;
	int m = mid, n = end;
	int k = 0;

	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}

	while (i <= m)
		temp[k++] = a[i++];
	while (j <= n)
		temp[k++] = a[j++];

	for (int i = 0; i < k; i++)/*把存储在临时对象temp中排好序列copy到a中对应的下标上*/
		a[first + i] = temp[i];
}

上面只是对两个有序的系列进行合并，还没有对序列进行排序，那么如何排序了，这里我们要用到递归的思想，就是把序列分成若干个系列再合并，分裂到最后必然小的系列，包含一个元素，一个元素的系列必然是有序的，然后逆向合并，合并起来的必然是有序的。

void merge_sort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		merge_sort(a, first, mid, temp);    //it's let letf have a regular
		merge_sort(a, mid + 1, last, temp); //it's let right have a regular
		merge(a, temp, first, mid, last); //merge two  in  one  
	}
}

写个测试代码：

int main()
{
	int a[] = { 1, 8, 6, 7, 9, 45, 68, 100, 5 };

	int k = (sizeof(a) / sizeof(int));

	int *p = new int[k];

	merge_sort(a,0,k-1,p);

	for (int i = 0; i < k; i++)
		cout << a[i] << " ";

	return 0;
}