【数据结构】——排序篇(下)

【数据结构】——排序篇(下)

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

归并排序:

归并排序(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中递归完成排序之后就返回,再将开辟的空间销毁。

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

转载请说明出处内容投诉
CSS教程_站长资源网 » 【数据结构】——排序篇(下)

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买