归并排序（二路、递归）

深碍√TFBOYSˉ_ 2023-05-22 06:37 5阅读 0赞

## 归并排序 ##

##### 排序策略 #####

**将两个有序表归并为一个新的有序表**

##### 排序过程 #####

**`i`与`j`分别是两个有序表的所索引**

①当`i`和`j` 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的对象排放到新表 `k` 所指位置中

②当 `i`与 `j`中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中

如图：  
需要进行归并的两个表：  
![在这里插入图片描述][20200416145045379.png]  
归并的新表：  
![在这里插入图片描述][20200416145131799.png]

##### 实现代码 #####

origen[]和result[]作为私有属性存储数据
    /**
      * 一次归并
      * @param i 归并的起始位置
      * @param mid 归并的中间值
      * @param j 归并的结束位置
      */
     private static void merge(int i, int mid, int j) {
      	//将数据分为两个集合：i~mid、mid+1~i
      	int temp = mid + 1;
      	int begin = i;
      	//新序列索引
      	int index = i;
      	//当两者均为出界
      	while(begin <= mid &&  temp <= j) {
       		if(orign[begin] < orign[temp]) {
        			result[index++] = orign[begin++];
       		}else {
        			result[index++] = orign[temp++];
       		}
      	}
      	//一方为空时，将剩余的进行归并到新集合中
      	while(begin <= mid) {
       		result[index++] = orign[begin++];
      	}
      	while(temp <= j) {
       		result[index++] = orign[temp++];
      	}
      
      	//将排序好的数据赋给要排序的表
      	for(; i <= j; i++) {
       		orign[i] = result[i];
      	}
     }

## 二路归并排序 ##

##### 排序策略 #####

**假设初始对象序列有 n 个对象  
首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)  
再做两两归并，即每次将上次由两个子序列归并得到的对象之间再次进行归并  
如此重复，最后得到一个长度为 n 的有序序列**

##### 排序过程 #####

**设置一个步长step，每次排序完整个序列后都调整步长  
在每次排序过程中，按照步长给整个序列分组，按组进行归并排序**

**若n不是2step的整数倍, 则一趟归并到最后,可能遇到两种情形:  
①剩下一个长度为step的归并项和另一个长度不足step的归并项, 可用merge算法将它们归并成一个长度小于 2step 的归并项  
②只剩下一个归并项，其长度小于或等于 step, 不必进行排序，在下一次排序过程中再次进行排序**

例，排序以集合\{21,25,49,25,93,62,72,8,37,16,54\}中数据为例，执行迭代归并排序  
①步长step =1 时，两两归并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]  
②步长step =2 时，两两归并![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]  
③步长step =4 时，两两归并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]  
④步长step =8 时，两两归并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]

##### 实现代码 #####

二路归并排序：

/**
      * 二路归并排序
      * @param length 序列长度
      * @param step 步长
      */
     private static void doubMerge(int length, int step) {
      	int i = 0;
      	//当两个步长小于总长度时，进行排序
      	while((i+2*step) < length) {
       		merge(i, i+step-1, i+2*step-1);
       		i += 2*step;
      	}
      	//当一个步长小于总长度时，进行排序
      	if((i+step) < length) {
       		merge(i, i+step, length-1);
      	}
      	System.out.println(Arrays.toString(orign));
      	//由于每次归并后，步长乘于2，即剩余部分一定是上一次归并排序的结果，即是有序的
      	//则可将剩余部分先不做排序，下一次再进行排序
     }

初始化及调整步长：

/**
      * 二路归并排序
      * @param list  需要进行排序的数据
      * @return 排序的结果
      */
     public static int[] doubMerSort(int[] list) {
      	//初始化
      	this.orign = list;
      	this.result = new int[list.length];
      	//步长
      	int step = 1;
      	System.out.println("每次步长调整后排序结果：");
      	while(step < list.length-1) {
       		doubMerge(list.length, step);
       		step = step*2;
      	}
      	return this.result;
     }

**测试结果**

##### 时间及空间复杂度 #####

①时间  
在整个排序过程中：  
doubMerSort()需要调用doubMerge() log2n 次  
doubMerge()需要调用merge() n/(2\*step)次  
merge()函数每次需要比较 step+i次，赋值2\*step次

即，时间复杂度为T(n) = n\*log2n

②空间  
使用了辅助数组，即S(n)=O(n)

③稳定性  
该算法是稳定的

##### 适用范围 #####

n较大时

## 递归归并排序 ##

##### 排序策略 #####

**首先把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并**

##### 排序过程 #####

例，排序以集合\{27,8,59,9,23,41,65,19\}中数据为例，执行递归归并排序

①使用递归完成发表中数据的分割  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]  
②再将相邻数据进行归并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]

##### 实现代码 #####

递归归并排序

/**
      * 递归进行归并排序
      * @param i 排序的起点
      * @param j 排序的终点
      */
     private static void resSort(int i, int j) { 
      	if(i < j) {
       		//先对当前集合两边进行排序
       		resSort(i, (i+j)/2);
       		resSort((i+j)/2+1, j);
       		//进行归并
       		merge(i, (i+j)/2, j);
       		System.out.println(Arrays.toString(orign));
      	}
     }

初始化：

/**
      * 递归归并排序
      * @param list  需要进行排序的数据
      * @return 排序的结果
      */
     public static int[] merSort(int[] list) {
      	this.orign = list;
      	this.result = new int[list.length];
      	System.out.println("每次排序后的原序列：");
      	resSort(0, list.length-1);
      	return this.result;
     }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]

##### 时间及空间复杂度 #####

①时间  
类似于一棵完全二叉树：  
则共递归执行log2n层  
而每一层都相当于将整个序列进行了一次排序，即O(n)

递归方程：  
T(n)=1 当n=1  
T(n)=2T(n/2)+O(n) 当n>1

即，时间复杂度为T(n) = n\*log2n

②空间  
使用了辅助数组，并且使用了递归占用了栈的空间，即S(n)=O(n)

③稳定性  
该算法是稳定的

#### 适用范围 ####

n较大时

[20200416145045379.png]: /images/20230521/f753e83bf3254b5ba0df2b1890c4eeaf.png
[20200416145131799.png]: /images/20230521/fd318643b8ac404db66ce4bc38dce7c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230521/f6e5d05df3cb49ce81fe985144239b58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: /images/20230521/49e1d40a11df4cbba53a0b9813ddd0cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: /images/20230521/e93160434fe5477cb93ff02447a46ae6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: /images/20230521/cbf56743bdcd4efda0c99c3a2101eb72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]: /images/20230521/bbe8e7e6c46547e88353ad326bebac36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]: /images/20230521/81568968fe624122ba4206ae7e465536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]: /images/20230521/602fbf76f73d4d1bafa809a15abc97e2.png