【数据结构】——排序篇（下）

前言：前面我们的排序已经详细的讲解了一系列的方法，那么我们现在久之后一个归并排序了，所以我们现在就来讲解一下归并排序。

归并排序：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid][mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	// [begin, mid][mid+1, end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

a是我们待排序的数组，里面存放了要排序的数据，tmp是我们额外开辟的数组用来存放我们排好序的数据，而我们排好序的数据则是像链表一样尾插入数组的。我们先找出中间值，给这个区间分成两个小区间，两个小区间各自在分成小区间。从左到右逐一比较两个小区间中的元素，把较小的元素优先放入额外开辟的数组tmp，如果一个小区间的全部尾插到tmp中就结束了循环，而另外一个数组则按顺序的尾插到tmp中。最后我们的tmp中的数据拷贝到数组a中就完成了。

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

这里就是用来开辟额外数组tmp的，我们传参到函数_MergeSort，在_MergeSort中递归完成排序之后就返回，再将开辟的空间销毁。

如果最大家有所帮助的话就支持一下吧！感谢大家！