《恋上数据结构与算法》排序（五）：归并排序

「爱情、让人受尽委屈。」 2023-01-01 14:58 132阅读 0赞

> 转载自 : [https://blog.csdn.net/weixin\_43734095/article/details/105127138][https_blog.csdn.net_weixin_43734095_article_details_105127138]
> 
>  *  相关 : [https://juejin.cn/post/6844904094235426830][https_juejin.cn_post_6844904094235426830]

# 一、经典十大排序算法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

# 归并排序 #

*  归并排序（MERGE-SORT）是利用`归并`的思想实现的排序方法，该算法采用经典的`分治（divide-and-conquer）策略`（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

执行流程

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]

## 序列分割-divide ##

/** * 对[begin, end)范围的数据进行归并排序; 左闭右开 * * @param begin * @param end */
    private void divide(int begin, int end) { 
        // 表示只有一个元素了, 就不需要归并排序
        if (end - begin < 2) return;
    
        int mid = (begin + end) >> 1;
        // 归并排序左半子序列
        divide(begin, mid);
        // 归并排序右半子序列
        divide(mid, end);
        // 合并整个序列
        merge(begin, mid, end);
    }

## 序列合并-merge ##

#### 合并到新序列 ####

*  将两个序列合并的思路为：**`左序列`和`右序列`的中元素挨个比较，`将较小的放入新序列中`，最后新序列中的元素必然升序。**

下图中 li，ri 分别代表指向左、右序列的元素**索引**，ai 为新序列（合并后的序列）的元素**索引**；  
【li】代表左序列 li 位置的**元素**，【ri】代表右序列 ri 位置的**元素**，【ai】为新序列 ai 位置的**元素**；

*  第一轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++;
 *  第二轮：【li】 > 【ri】，【ri】放入新数组，【ai】=【ri】，ri++; ai++;
 *  第三轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++；
 *  第四轮：**左序列已经遍历完毕**，直接将右序列剩余元素放入新序列，得到新序列（升序）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]

### 原地合并-merge ###

*  将两个序列合并时，不一定要合并到新空间，可以合理的利用原空间实现 **`原地合并`**。

例如：

*  将 **array的左半部分\[begin, mid)**，备份到 leftArray 中；
 *  然后将 **leftArray** 视为左子序列，**arrary的右半部分\[mid, end\]** 视为右子序列；
 *  将左子序列和右子序列合并到 array 中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 2]

**merge 过程：**

*  li < ri  
    array\[ai\] = leftArray\[li\]；  
    li++，ai++;
 *  li >= ri  
    array\[ai\] = array\[ri\];  
    ri++，ai++;

对序列 \{ 3, 8, 6, 10 \} 进行归并排序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 3]

对序列 \{ 3, 6, 8, 10 \} 进行归并排序：**左子序列先遍历结束**，那就归并结束。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 4]  
对序列 \{ 8, 10, 3, 6 \} 进行归并排序：**右子序列先结束**，则将左边剩余全部放入。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 5]

### 原地合并-merge-实现 ###

/** * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列 */
    private void merge(int begin, int mid, int end){ 
    	int li = 0, le = mid - begin; // 左边数组(基于leftArray)
    	int ri = mid, re = end;	// 右边数组(array)
    	int ai = begin; // array的索引
    	
    	// 备份左边数组到leftArray
    	for(int i = li; i < le; i++){ 
    		leftArray[i] = array[begin + i];
    	}
    	
    	// 如果左边还没有结束 
    	while(li < le){  // li == le 左边结束, 则直接结束归并
    		if(ri < re && cmp(array[ri], leftArray[li]) < 0){  // cmp改为<=0会失去稳定性
    			array[ai++] = array[ri++]; // 右边<左边, 拷贝右边数组到array
    		}else{ 
    			array[ai++] = leftArray[li++]; // 左边<=右边, 拷贝左边数组到array
    		}
    	}
    }

# 归并排序完整代码 #

/** * Description: 归并排序 * * @author guizy * @date 2021/1/3 15:15 */
    @SuppressWarnings("all")
    public class MergeSort<E extends Comparable<E>> extends Sort<E> { 
    
        private E[] leftArray;
    
        @Override
        protected void sort() { 
            leftArray = (E[]) new Comparable[array.length >> 1];
            divide(0, array.length);
        }
    
        /** * 对[begin, end)范围的数据进行归并排序; 左闭右开 * * @param begin * @param end */
        private void divide(int begin, int end) { 
            // 表示只有一个元素了, 就不需要归并排序
            if (end - begin < 2) return;
    
            int mid = (begin + end) >> 1;
            // 归并排序左半子序列
            divide(begin, mid);
            // 归并排序右半子序列
            divide(mid, end);
            // 合并整个序列
            merge(begin, mid, end);
        }
    
        /** * 将[begin, mid)和[mid, end)范围的序列合并成一个有序序列 * * @param begin * @param mid * @param end */
        private void merge(int begin, int mid, int end) { 
            int li = 0, le = mid - begin;   // 左边数组(基于leftArray)
            int ri = mid, re = end; // 右边数组(基于array)
            int ai = begin; // array的索引
    
            // 拷贝左边数组到leftArray
            for (int i = li; i < le; i++) { 
                leftArray[i] = array[begin + i];
            }
    
            // 如果左边还没有结束
            while (li < le) {   // li == le 左边结束, 则直接结束归并
                if (ri < re && cmp(array[ri], leftArray[li]) < 0) { 
                    // 拷贝右边数组到array
                    array[ai++] = array[ri++];
                } else { 
                    // 拷贝左边数组到array
                    array[ai++] = leftArray[li++];
                }
            }
        }
    }

/** * Description: 归并排序 * * @author guizy1 * @date 2021/2/2 9:40 */
    public class MergeSort { 
    
        private static int[] leftArray;
    
        public static void main(String[] args) { 
            int[] array = { 4, 3, 5, 1, 9, 8, 2, 0};
            leftArray = new int[array.length >> 1];
    
            // [begin, end) 左闭右开
            divide(0, array.length, array);
    
            for (int i : array) { 
                System.out.print(i + " ");
            }
        }
    
        // 分
        private static void divide(int begin, int end, int[] array) { 
            if (end - begin < 2) return; // 数组元素大于2, 才能进行归并排序
            int mid = (begin + end) >> 1;
            // 归并排序左半子序列
            divide(begin, mid, array);
            // 归并排序右半子序列
            divide(mid, end, array);
            // 合并整个序列
            merge(begin, mid, end, array);
        }
    
        // 合
        private static void merge(int begin, int mid, int end, int[] array) { 
            int li = 0, le = mid - begin;   // 左边数组(基于leftArray)
            int ri = mid, re = end; // 右边数组(基于array)
            int ai = begin; // array的索引
    
            // 拷贝左边数组到leftArray
            for (int i = li; i < le; i++) { 
                leftArray[i] = array[begin + i];
            }
    
            // 如果左边还没有结束
            while (li < le) {   // li == le 左边结束, 则直接结束归并
                if (ri < re && array[ri] < leftArray[li]) { 
                    // 拷贝右边数组到array
                    array[ai++] = array[ri++];
                } else { 
                    // 拷贝左边数组到array
                    array[ai++] = leftArray[li++];
                }
            }
        }
    }

生成 20000 个取值在\[1, 10000\] 的随机数进行排序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 6]

# 复杂度与稳定性 #

**归并排序花费的时间递推式**：

*  T(n) = 2 ∗ T(n/2) + O(n)
 *  T(1) = O(1)
 *  T(n) / n = T(n/2)/(n/2) + O(1)

**根据递推式计算复杂度**：  
令 Sn = T(n) / n

*  S(1) = O(1)
 *  Sn = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2k) + O(k) = S(1) + O(logn) = O(logn)
 *  Tn = n ∗ Sn = O(nlogn)

由于归并排序总是**平均分割子列**，所以

*  **`最好、最坏时间复杂度`** 都 `O(nlogn)`
 *  归并排序属于 **`稳定排序`**
 *  归并排序的**空间复杂度**是 O(n/2 + logn) = O(n)  
    n / 2 用于临时存放左侧数组， logn 是因为递归调用

## 常见的递推式与复杂度 ##

以后遇到复杂的时间复杂度计算，写出递归式直接看这张表即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 7]

# LeetCode真题 #

## 88. 合并两个有序数组 ##

题目地址：[88. 合并两个有序数组][88.]

题目：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。

说明:

*  初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
 *  你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6],       n = 3
    
    输出: [1,2,2,3,5,6]
    12345

## 思路一：从前往后合并 ##

原地合并，nums1 从头往后合并，将 nums2 元素插入到 nums1 时需要将挪动元素，**效率较低**。

class Solution { 
    
        public void merge(int[] nums1, int m, int[] nums2, int n) { 
        	int li = 0, ri = 0, ai = 0, m2 = m; // 备份一下m 
        	while(ri < n){  //nums2遍历完则直接结束
        		if(nums1[li] <= nums2[ri] && li < m2){ 
        			li++;
        			ai++;
        		}else{  // nums1[li] >= nums2[ri]
        			// 要令ri指向元素插入到ai, 首先将 ai到ai+li往后移1位
        			for(int i = m+n-1; i > ai; i--){ 
        				nums1[i] = nums1[i - 1];
        			}
        			nums1[ai++] = nums2[ri++];
                    li++;
                    m2++;
        		}
        	}
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 8]

## 思路二：从后往前合并 ##

在思路一的基础上，将**从前往后合并**变为**从后往前合并**。

原地合并，nums1 从后往前合并，将 nums2 元素放入 nums1 时无需移动元素，**效率较高**。

class Solution { 
    
    	public void merge(int[] nums1, int m, int[] nums2, int n) { 
    		 int len = m + n; //从后往前移, 需要合并后的总长度
    		 for(int i = len - 1; i >=0; i--){ 
    			 if(m>0 && n>0 && nums1[m-1] > nums2[n-1]  || n==0){ 
    				 nums1[i] = nums1[--m];
    			 }else{ 
    				 nums1[i] = nums2[--n];
    			 }
    		 }		 
    	 }
    	 
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 9]

[https_blog.csdn.net_weixin_43734095_article_details_105127138]: https://blog.csdn.net/weixin_43734095/article/details/105127138
[https_juejin.cn_post_6844904094235426830]: https://juejin.cn/post/6844904094235426830
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/2b6cd5ac713b454bb62778cdf8637ee3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]: /images/20221120/11bfee28546949b1b4d80ffb6ba67397.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/93152774b289490590c665233c0d587f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/7ef513a8f18b4348a3422318cc54bbed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 3]: /images/20221120/c68b8faa08c44c049ba2caaf2ea21abd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 4]: /images/20221120/ce4f564113bf42bea5bd919fc2c1703b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 5]: /images/20221120/5935de65ad8b44848091ac88f6164cf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 6]: /images/20221120/15fafce4884b4096a0529f2803f4788a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 7]: /images/20221120/1324a2ff2533427daab44db4d2e7dea8.png
[88.]: https://leetcode-cn.com/problems/merge-sorted-array/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 8]: /images/20221120/f0a661f633804a829114b222d6582c65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 9]: /images/20221120/5709b6a7d21b4ec89a9afd6b2b01eba3.png