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

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

归并排序：

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

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