归并排序主要运用了"分治算法"，就是将一个大的问题划分为n个规模较小而结构相似的子问题，子问题的解决办法都是相似的，分别解决这些子问题，然后归并子问题的结果，得到大问题的解。

归并排序的主旨就是分解 ，归并：
分解：将数组分为单个元素，默认单个就是排好序的。
归并：从最小的只包含一个元素的数组开始两两合并，合并后的数组也是有序的，最后得到原数组也是有序的。
如图：

如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；

算法描述：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾。

比较快排：
归并排序是稳定的排序，即相等的元素的顺序不会改变。如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。
速度仅次于快速排序，一般用于对总体无序，但各子项相对有序的数组排序。
应用：求逆序对数。在合并的时候，记录逆序对。

复杂度：

• 归并排序比较占用内存，需要额外的空间来存放合并后的数组，是典型的用空间换时间的例子。
• 改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)。
• TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。
  
  相比快排：最好O(N),最坏O(N*N),空间复杂度O(1)。

package sort;
/*
 * 归并排序：利用递归来分解数组，利用分治来合并数组。
 * 核心思想：将一个无序的n长数组切成n个有序子序列（只有一个数据默认为有序），
 * 			然后两两合并，再将合并后的n/2个子序列继续进行两两合并，循环。。
 * 因为将两个有序的数组归并到另一个数组中，所以需要开辟额外的空间。workspace
 * 
 * 算法：元素总数为n，需要分log2n层，每一层归并复制后，再与上一层继续归并，复制总数n*log2n
 * 		所以算法复杂度为O(n*log2n),比较次数远小于复制次数，可忽略。
 */
public class Merge {
	
	public static int[] mergeSort(int[] nums,int l,int h) {
		if(l==h) {
			return new int[] {nums[l]}; //分解到一个元素默认有序。
		}
		
		//先递归分解
		int mid = l + (h-l)/2;
		int[] leftArr = mergeSort(nums, l, mid); //对左分组排序
		int[] rightArr = mergeSort(nums, mid+1, h); //对右分组排序
		int[] newNum = new int[leftArr.length + rightArr.length]; //存放归并排好序的数组
		
		//后归并排序
		int m=0,i=0,j=0;
		while(i<leftArr.length && j<rightArr.length) {
			newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
		}
		while(i<leftArr.length) {
			newNum[m++] = leftArr[i++];
		}
		while(j<rightArr.length) {
			newNum[m++] = rightArr[j++];
		}
		
		return newNum; //返回归并后的数组
	}
	
	public static void main(String[] args) {
		int[] nums = new int[] {9,3,6,2,0,7,4,1};
		int[] newNums = mergeSort(nums, 0, nums.length-1);
		for(int x : newNums) {
			System.out.print(x+" ");
		}
	}
}

基础数据结构之八大排序算法（五）

⑤二路归并排序：

时间复杂度：O(nlogn) 外层函数需要遍历的次数与2的指数次有关（外层的时将复杂度为O(logn)），内层函数需要完全遍历所有数据（内层的时间复杂度为O(n)）,两个相乘整体的时间复杂度为O(nlogn)
空间复杂度：O(nlogn) 额外的辅助变量会影响的问题的规模（内层额外辅助空间brr,外层函数所需额外辅助变量i），整体空间复杂度为O(nlogn)
稳定性：不稳定 存在跳跃交换

（以顺序表作为待排序对象）

1.基本思想：
（1）.一开始将所有数据看作单独的个体（队列），这个时候他们都独自有序。
（2）.两个对列两个队列融合（保证融合后有序且稳定（不存在跳跃交换））
（3）.重复第二步直到所有数据都到一个队列中。

以数组arr[]={21,12,7,9,11,98,56,88,66,68}为例：

（这里初始数据一共是10个，第一次是1个队列和1个队列融合，第二次是2个数据的队列和2个数据的队列融合，第三次是4个数据的队列和4个数据的队列融合，第四次是8个数据的队列和8个数据（实际上其中只有2个数据）的队列融合），从而看出融合次数的规律：

【设 i 为运行次数，当( i * 2 ) < 总数据个数时继续排序】

2.具体合并方法：

（1）.需要设置一个临时辅助空间 brr 来存放两两队列对比排序完数据。
（2）.左右手对比时，先从左右手中各从左到右对比，两手中较小的那个放到辅助空间 brr 中，循环这样比较直到一只手空了，则剩下的那个手里的数据依次放到辅助空间 brr 中。
（3）.两手放完后，再去抓另外两组

*设置临时辅助空间 brr 的原因：
例如数组arr[]={7,9,11,12,12,11,88,98,66,68}时：

当只用arr时会导致无序，不稳定，所以需要设立临时辅助空间brr。

3.代码实现：

<1>.所需头文件和宏替换：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>

#define ar arr[]={21,12,7,9,11,98,56,88,66,68}
#define ELEM_TYPE int

int ar;

<2>.顺序表的建立：

typedef struct Sqlist
{
	ELEM_TYPE* data;
	int length;
	int SIZE;
}Sqlist,*PSqlist;

<3>.顺序表的初始化：

void Init_Sqlist(PSqlist L)
{
	L->data = arr;
	L->length = 0;
	L->SIZE = sizeof(arr) / sizeof(arr[0]);
}

<4>.打印

void Show(PSqlist L)
{
	for (int i = L->length; i < L->SIZE; i++)
	{
		printf("%d ", L->data[i]);
	}
	printf("\n\n");
}

<5>.每一次的归并排序：

void Merge(PSqlist L,int gap)          //控制一次融合,gap是每次融合组中数据的个数
{
	ELEM_TYPE* brr = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * L->SIZE);   //申请额外辅助空间brr
	int i = 0;          //辅助空间的下标

	//左右手的边界
	int low1 = 0;                           
	int high1 = low1 + gap - 1;      //有边界=左边界+偏移量
	int low2 = high1 + 1;
	int high2 = low2 + gap - 1 < L->SIZE ? low2 + gap - 1 : L->SIZE - 1;

	while (low2 <= high2)              //最外层保证可以抓取值
	{
		while (low1 <= high1 && low2 <= high2)        //内层保证两只手都有值可以比较大小
		{
			if (arr[low1] <= arr[low2])
			{
				brr[i++] = arr[low1++];
			}
			else
			{
				brr[i++] = arr[low2++];
			}
		}
		//内层循环退出的时候代表有一只手为空，这时直接将不为空的手里的数据依次放到brr中

		while (low1<=high1)         //左手不空时
		{
			brr[i++] = arr[low1++];
		}

		while (low2<=high2)         //右手不空时
		{
			brr[i++] = arr[low2++];
		}

		//已经将这次的左右手都放到brr中了，就让左右手再去抓另外的组
		low1 = high2 + 1;
		high1 = low1 + gap - 1;
		low2 = high1 + 1;
		high2 = low2 + gap - 1 < L->SIZE ? low2 + gap - 1:L->SIZE - 1;    //这里是决定外层循环退出的关键

	}
	//外层循环退出代表两种情况：1.此时全部数据都已经排完，目前左右手都是空的，这种情况不用管
	                          //2.此时左手有值右手没有值，这时只需要将左手的值依次放进brr就可以

	while (low1 < L->SIZE)
	{
		brr[i++] = arr[low1++];
	}

	//此时brr已经满了，只需将brr都覆盖arr即可
	for (int k = 0; k < L->SIZE; k++)
	{
		arr[k] = brr[k];
	}

	//最后将临时辅助空间释放防止内存泄露
	free(brr);
}

<6>.二路归并排序：

void MergeSort(PSqlist L)          //控制总的融合次数
{
	for (int i = L->length + 1; i < L->SIZE; i = i * 2)
	{
		Merge(L, i);
	}
}

<7>.主函数：

int main()
{
	Sqlist head;
	Init_Sqlist(&head);
	printf("初始数据为:");
	Show(&head);

	MergeSort(&head);
	printf("二路归并排序后数据为:");
	Show(&head);
	return 0;
}

<8>.运行结果：

希望这篇博客能帮助大家更好的学习和理解二路归并排序
感谢阅读！

目录

前言

一、排序规则

两两融合规则

二、代码实现

1.非递归实现

2.递归实现

总结

前言

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

这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。

时间复杂度：平均情况O(nlogn)；最好情况(nlogn)；最坏情况O(nlogn)
空间复杂度：O(n)
稳定性：       稳定
基本思想：首先将所有数据看做一个个单独的个体（单独的个体有序），然后两两融合，直到所有的数据都在同一个组内。

一、排序规则

1.一开始就将所有值都看作单独的个体，这个时候，从另一个角度来讲，他们独自有序。

2.两个部分两个部分融合(保证融合后有序且稳定)。

3.重复第二步，直到所有的数据都在同一个队列中。

两两融合规则

左手右手各拿起左右两部分中第一个值(也即是最小值)，进行比较，谁小，谁先放置(递增序列)，如果相等则先放置左边，这是为了保证原有的顺序性。

此处的"放置"，我们需要借助辅助空间，也就是另一个数组来帮助实现。

我们依旧设立一组数来帮助理解：{21  12  7  9  11  98  56  88  66  68};

下面图示中数字下的“横线”,表示分组；

上图只为表现归并思想，省去了辅助空间。

即不断进行两两融合，直到最后(第四次)，数据全部存在于一个队列中，则排序结束。

上述为非递归式二路归并排序，而递归式仅是将整个队列规模层层降低，变成一个个单独的元素后再进行上述操作。

因非递归式较易理解，我们在此仅进行非递归分析。

二、代码实现

1.非递归实现

因为代码较长，且难以理解，在此简单分析一下：
首先，MergeSort函数中，给出了数据每次进行归并时的规模，并调用Merge。

Merge函数中，首先构造了辅助空间，其大小与原数据队列相同。

而后我们确定了，左右数据队列的范围。

左手的左边界：low1 = 0;   //即为数组最左边元素的位置

左手的右边界：high1 = low1 + gap - 1;  //右边界的确定与问题规模有关，若规模为1，则high = 0 + 1 - 1 = 0;即左手抓住一个值，以此类推。

右手的左边界：low2 = high + 1;   //因为左右两个数据队列相邻

右手的右边界：low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;  //此处与左边空间规则相同，但需要考虑合法性问题，即右边界不可能超过数组。

在while中我们完成了将归并融合的值放入辅助空间的过程。

其余问题皆在注释中进行分析，逐句理解即可。

void Merge(int arr[], int len, int gap)//gap：代表合并的两个组中单独的组个数是多少(几几合并的几)
{
	//第一步，先整出来辅助空间brr
	int* brr = (int*)malloc(len * sizeof(int));
	assert(brr != NULL);
	int i = 0; //i是辅助空间brr的下标   代表下一个值插入位置

	int low1 = 0;//左手的左边界
	int high1 = low1 + gap - 1;//左手的右边界
	int low2 = high1 + 1;//右手的左边界
	int high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;//右手的右边界

	while (low2 <= high2)//确保左手和右手都抓到值（左右手都不空），只要右手还有值，左手肯定抓满值了
	{
        //代表着，融合比较过程中，左右手还不空
        //有一个空了，就不用比较了，直接向brr挪动另一个手中的数据即可
		while (low1 <= high1 && low2 <= high2)
		{
			if (arr[low1] <= arr[low2])//如果左手的第一个值 <= 右手的第一个值
			{
				brr[i++] = arr[low1++];//将左手的第一个值放到brr中
			}
			else//如果左手的第一个值 > 右手的第一个值
			{
				brr[i++] = arr[low2++];//将右手的第一个值放到brr中
			}
		}

		//当内层while循环退出，代表着肯定有一个手空了
		//这里可以不用判断到底哪个手空了，简单粗暴一点（两个数组都调用一下，将其剩余数据向brr挪动）
		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;
	}

	//此时，代表着处理到最后一组了：这时候退出有两种情况：1.左右手都没有抓到值 2.左手不空，右手空 
	//会不会存在第三种情况：左手空，右手不空？  这种情况不存在
	//那么怎么处理上面两种可以出现的情况：第一种皆大欢喜，不用管了
	//                                    第二种，需要处理一下

	//处理2：左手的值放到brr里，右手肯定为空 不用管
	while (low1 < len)//将左手剩余数据向brr中挪动  //这里是low1<len
	{
		brr[i++] = arr[low1++];
	}

	//最后一步，brr里放满了值， 这时只需要将brr的值同步到arr里即可
	for (int k = 0; k < len; k++)
	{
		arr[k] = brr[k];
	}

	free(brr);//释放辅助空间brr
	brr = NULL;

}
void MergeSort(int* arr, int len)
{
    assert(arr != NULL);
	//i代表几几合并的几   当i小于len时，才有必要进行一次融合
	//当i大于等于len时，没有必要进行一次融合，因为这时所有的值都在同一个组内
	for (int i = 1; i < len; i *= 2) //logn
	{
		Merge(arr, len, i);
	}
}

2.递归实现

递归实现中，Merge函数的实现与非递归基本相同，代码量还有些许减少。

主要问题在于理解MergePass中递归思想，其将整个规模层层剥离减少，到达非递归中的初始，即一个元素为一个队列时开始回归，而后进行与非递归相同操作。

需要注意的是，递归式中的辅助空间则是在外部申请，因为需要防止在递归中同时申请大量空间的情况。

void Copy(int* src, int* dest, int left, int right)
{
	while (left <= right)
	{
		src[left] = dest[left];
		left++;
	}
}
void Merge(int* src, int* dest, int left, int m, int right)
{
	int i = left; //i是辅助空间brr的下标   代表下一个值插入位置
	int j = m + 1;
	int k = left;
	while (i <= m && j <= right)//代表着，融合比较过程中，左右手还不空（有一个空了，就不用比较了，直接向brr挪动另一个手中的数据即可）
	{
		if (src[i] <= src[j])//如果左手的第一个值 <= 右手的第一个值
		{
			dest[k++] = src[i++];//将左手的第一个值放到brr中
		}
		else//如果左手的第一个值 > 右手的第一个值
		{
			dest[k++] = src[j++];//将右手的第一个值放到brr中
		}
	}

	//当内层while循环退出，代表着肯定有一个手空了
	//这里可以不用判断到底哪个手空了，简单粗暴一点（两个数组都调用一下，将其剩余数据向brr挪动）
	while (i <= m)//将左手剩余数据向brr中挪动
	{
		dest[k++] = src[i++];
	}
	while (j <= right)//将右手剩余数据向brr中挪动
	{
		dest[k++] = src[j++];
	}
}
void MergePass(int* src, int* dest, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		MergePass(src, dest, left, mid);
		MergePass(src, dest, mid + 1, right);

		Merge(src, dest, left, mid, right);
		Copy(src, dest, left, right);
	}
}
void MergeSort(int* arr, int len)
{
	if (len < 2 || arr == NULL)
	{
		return;
	}
	int* tmp = (int*)malloc(sizeof(int) * len);
	MergePass(arr, tmp, 0, len - 1);
	free(tmp);
}

总结

以上就是今天学习的内容，本文介绍了归并排序的排序规则和代码实现，归并排序速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。