【归并排序】

归并排序

• 前言
• 一、归并排序
• 二、归并实现
• • 1. 实现细节
  • 2. 具体代码实现
• 总结

---

前言

归并排序的定义

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

---

一、归并排序

归并排序也称为“二路归并”排序

1. 思想：首先将所有的数据默认每个数字单独一个组，接下来两两合并（两个组），当所有的数据在同一个组内的时候，数据完全有序，则可以结束
2. 步骤：对于原始数据，可以看作是两只手，两只手依次抓取数据
   第一次两两合并：从左向右，左右两只手依次抓取两个数据，并将抓取的两个元素进行排序
   第二次两两合并：还是从左向右，左右两只手依次抓取两个数据，将抓取的数据进行排序
   …
   第n次两两合并：直到所有的数据均在同一个组内，此时就可以停止抓取，这时也就说明数据已经排序完成
   具体步骤如下图例子所示
   
   废话不多说，直接上动图：
   

二、归并实现 1. 实现细节

1. 对于二路归并排序来说，其最重要的就是数组的划分，每次要“抓取”的数据，需要先将数据分组，然后两两抓取
2. 需要知道总共合并几次，对于一组数据，合并的次数怎样计算？
   需要清楚的是，当所有的数据全部在同一个组内的时候，就停止抓取数据
   例如：
   
   其中，1 1 代表第一次抓取的值的个数，假设10个数据分为10个组，第一次“左手”抓取1个值，“右手”抓取一个值；
   2 2 代表第二次抓取的值得个数，第二次“左手”抓取两个值，“右手”抓取两个值，此时也是合法得
   …
   8 8 代表本次抓取得数据，“左手”有8个，右手可以抓取8个，此时要注意，这样抓取也是合法的，因为总共有10个数据，左手抓取8个数据之后还剩2个数据，此时右手就只需要抓取2个数据即可，并不需要完全抓取8个数据，只要将数据中得值抓取完成即可
   16 16 代表本次“左、右手”均可以抓取16个数据，但是数组总共有10个数据，所以本次“左手”抓不满，也就是说明：此时数据已经存在于同一个组内，也就是已经排好序
   【说明】在第n次抓取数据之后，每个“小组”的数据元素个数为2^n

2. 具体代码实现

对于二路归并排序来说，最重要的就是：每次分组抓取数据，如何实现分组抓取，也就是上面所说的“两两合并”，只要可以清楚的知道怎样两两合并，那么只需要用for循环控制两两合并的次数即可，因为每次两两合并均是相同的理论

代码如下：

//一次融合函数  时间复杂度O（n）  空间复杂度O（n）
void Merge(int arr[], int len, int gap)
{
	int low1 = 0;
	int high1 = low1+gap-1;
	int low2 = high1+1;
	int high2 = low2+gap-1<len ? low2+gap-1 : len-1;

	int *brr = (int*)malloc(len * sizeof(int));
	assert(brr != NULL);
	int i=0;//i指向辅助空间brr的下标

	while(low2 < len)//写法不唯一：目的就一个，证明两个手抓到的两个组都有数据
	{
		while(low1<=high1 && low2<=high2)//保证两个组内还有数据去拿来比较
		{
			if(arr[low1] <= arr[low2])
			{
				brr[i++] = arr[low1++];
			}
			else
			{
				brr[i++] = arr[low2++];
			}
		}
		//此时，肯定有一个手抓的组为空了，需要判断一下哪个手，做对应的出来

		while(low1 <= high1)//左手没空，此时将左手数据向brr中挪动
		{
			brr[i++] = arr[low1++];
		}
		while(low2 <= high2)//右手没空，此时将右手数据向brr中挪动
		{
			brr[i++] = arr[low2++];
		}
		//此时应该，继续向后抓两个组
		low1 = high2+1;
		high1 = low1+gap-1;
		low2 = high1+1;
		high2 = low2+gap-1<len ? low2+gap-1: len-1;
	}
	//此时，最外层while退出，有两种可能性：1.左手有数据，右手空了  2.左右手都空了

	while(low1 < len)//左手没空，此时将左手数据向brr中挪动 //不要写成low1<=high1  因为这里没有办法保证high1的合法性
	{
		brr[i++] = arr[low1++];
	}

	//最后将brr中的数据全部重新覆盖到arr里，即可
	for(int i=0; i<len; i++)
	{
		arr[i] = brr[i];
	}
	free(brr);
}

清楚了怎样“两两合并”，只需要对其使用for循环控制两两合并的次数即可

//归并排序
void MergeSort(int *arr, int len)
{
	for(int i=1; i<len; i*=2)// O（logn）
	{
		Merge(arr, len, i);
	}
}

---

总结

1. 归并排序是稳定的，因为其不涉及跳跃交换数据
   【注】稳定性：如果排序之前 3在3‘ 的前面，但是在排序之后，3跑到了3’ 的后面，则认为它不稳定
2. 时间复杂度：O(nlogn)
3. 空间复杂度：O（n）