归并排序【C语言版-笔记】

一、概念

归并是一种算法思想，是将两个或两个一上的有序表合并成一个长度较大的有序表。若一开始无序表中有n个元素，可以把n个元素看作n个有序表，把它们两两合并得到$\lceil n/2\rceil 个$长度为2或1(n为奇数时)的有序表，继续重复两两合并的操作，直到剩下一个有序表，即得到最终排序的结构，这是“二路归并排序”，还有多路的归并。

二、排序流程理解

给定一个序列如下：

1）不断地将当前序列平均分割成2个子序列，直到不能再分割（序列中只剩1个元素）
2）不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列

要点分析：
① 处理好边界和有序表分割位置选择问题
② 合并两个子序列的过程中，如何排序使合并后的序列是一个有序序列，称之为：merge

1、有序表分割的位置（排序使用到的参数：begin，mid，end）
初始时：
begin=0，mid=(begin+end)/2，end=length
规定：
左边表范围：[begin，mid）
右边表范围：[mid，end）
当无序表元素个数为偶数时，划分的左右子表元素个数相同，
当无序表元素个数为奇数时，划分的左右子表元素个数相差1，右子表多个一
不管奇偶情况如何，左子表元素个数为：mid-begin，右子表元素个数为：end-mid

2、merge过程中我们使用一个辅助数组leftArray，把位于[begin，end）
  范围的表中左边部分[begin，mid)之间的元素拷贝到leftArray中，用
  leftArray表中元素和右边部分元素依次比较，小的放入原表(即：[begin，end) ）中的左边部分，
  直到leftArray或右边部分的元素比较完，然后把剩余的没比较的直接拷贝到原表中即可，一次merge完成。

◼ li == 0，le == mid – begin
◼ ri == mid，re == end

三、代码实现

3.1主调函数

void sort(int *nums,int begin,int end){
	if(end-begin<=1) return;//只有一个元素不用排序
	int mid=(begin+end)/2;//或(begin+end)>>1
	sort(nums,begin,mid);
	sort(nums,mid.begin);
	merge(nums,begin,mid,end);
}

3.2 merge函数

void merge(int *nums,int begin,int mid,int end){
	int li=0;
	int le=mid-begin;
	int ri=mid;
	int re=end;
	int ai=begin;
	int leftArray=(int*)malloc(le*sizeof(int));//辅助数组
	//初始化辅助数组
	for(int i=li;i<le;i++){
		leftArray[i]=nums[begin+i];//begin~end之间左边部分拷贝到夫leftArray
	}
	//在原存储空间上给两个有序子表重新排序（逻辑上是合并为一个有序表），两种可能：左边指针先走完(ri>=re)或右边指针先走完。
	//若左边先走完则直接把leftArray中li指针指向的及之后的元素复制到原存储空间（nums）；若右边先走完，则结束
	while(li<le){
		if(ri<re&&nums[ri]<leftArray[li]){
			nums[ai++]=nums[ri++];//拷贝左边部分的元素到nums[ai]
		}else{
			nums[ai++]=leftArray[li++];//拷贝右边部分的元素到nums[ai]
		}
	}
}

四、性能分析

空间效率： merge函数中使用的辅助空间是n/2个单元，即算法的空间复杂度：O(n)
时间效率： 每趟归并的时间复杂度是O(n)，总共需要进行$\lceil lo{g}_{2}n\rceil$趟归并，总的时间复杂度：O(nlog₂n）
稳定性： 不会改变相同关键字记录的相对次序（看merge函数中while循环的处理部分可知），因此二路归并排序是稳定的排序算法