【数据结构】排序：归并排序（2路归并排序算法）详解，递归实现与迭代实现（C++）

野性酷女 2021-12-05 03:49 352阅读 0赞

\#笔记整理

***内部排序分类目录：***  
*- [插入排序][Link 1]  
\- [交换排序][Link 2]  
\- [选择排序][Link 3]  
**-[\->归并排序][-]**  
\- 计数排序*

# 归并 #

基本思路：是将两个或两个以上的有序表合并成一个新的有序表。

#### 2-路归并排序 ####

算法思路：  
假设初始序列有 n 个记录，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。  
整体思路如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
代码中注释更详细，建议结合代码理解。

**算法实现：**

// --------- 递归实现部分 start
        // 2路归并排序法的包装函数，对容器 nums 进行排序，递归法
        void mergeSort(vector<int> &nums){
        
            int len = nums.size();
            mSort(nums, 0, len - 1);   // 将无序的nums[0 ~ len-1] 归并排序为有序
        }
    
        // 2路归并排序法，对 nums[low ~ high] 进行归并排序，递归实现
        void mSort(vector<int> &nums, int low, int high){
        
            if(low < high){
                             // 有不只一个元素待归并
                int m = (low + high) / 2;
                mSort(nums, low, m);            // 递归将nums[low ~ m]归并为有序的 nums[low ~ m]
                mSort(nums, m + 1, high);       // 递归将nums[m+1 ~ high]归并为有序的 nums[m+1 ~ high]
                Merge(nums, low, m, high);      // 将有序的 nums[low ~ m] 和 nums[m+1 ~ high] 归并到 nums[low ~ high]
            }
        }
        // --------- 递归实现部分 end
    
    
        // --------- 迭代实现部分 start
        // 2路归并排序法的包装函数，对容器 nums 进行排序，迭代法
        void mergeSort2(vector<int> &nums){
        
            int len = nums.size();
            int currLen = 1;                    // 归并长度从 1 开始，迭代增加
            while( currLen < len){
        
                mSort2(nums, currLen, len);     // 分别对数组 nums 中长度为 1、2、4、8……的子序列进行归并排序
                currLen *= 2;
            }
        }
    
        // 2路归并排序法，依次将 nums 中长度为 subseqLen 的子序列进行归并排序。迭代实现
        // subseqLen：子序列长度， numsLen：数组长度
        void mSort2(vector<int> &nums, int subseqLen, int numsLen){
        
            int currLow = 0;
            int currHigh = currLow + 2 * subseqLen - 1;
            while( currHigh < numsLen){
        
                int m = (currLow + currHigh) / 2;
                Merge(nums, currLow, m, currHigh);
                currLow  = currLow + 2 * subseqLen;
                currHigh = currLow + 2 * subseqLen - 1;
            }
            if(currLow < numsLen - subseqLen + 1){
            // 若有剩下的单独子序列在最后，将最后两个子序列进行归并排序，防止漏掉
                Merge(nums, currLow, currLow + subseqLen - 1, numsLen - 1);
            }
        }
        // --------- 迭代实现部分 end
    
    
        // --------- 归并排序递归法和迭代法共有的合并函数
        // 2路归并排序法的合并函数，将有序的 nums[low ~ m] 与 nums[m+1 ~ high] 合并为有序的 nums[low ~ high]
        void Merge(vector<int> &nums, int low, int m, int high){
        
            int len = nums.size();
            vector<int> temp;             // 临时容器，用于暂存排好序的记录
            temp.resize(len);             // 设置临时容器大小
            int i = low;                  // nums[low ~ m] 范围内的下标
            int j = m + 1;                // nums[m+1 ~ high] 范围内的下标
            int k = low;                  // temp[low ~ high]的下标
            while(i <= m && j <= high){
        
                if(nums[i] < nums[j]){
        
                    temp[k] = nums[i++];
                }else{
        
                    temp[k] = nums[j++];
                }
                k++;
            }
    
            while(i <= m){
                         // 若temp[low ~ m] 还剩下数据，直接放到temp之后
                temp[k++] = nums[i++];
            }
    
            while(j <= high){
                      // 若temp[m+1 ~ high] 还剩下数据，直接放到temp之后
                temp[k++] = nums[j++];
            }
    
            for(i = low; i <= high; i++){
          // 将归并好的记录放回 nums
                nums[i] = temp[i];
            }
        }

[github源码][github]

**算法分析：**

*  在迭代的归并排序算法中，总的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
 *  在递归的归并排序算法中，总的时间复杂度为 O(nlogn)，空间复杂度为 O(n+logn)。
 *  递归的归并排序算法的递归深度为 logn。
 *  归并排序占用附加存储较多，需要另外一个与原待排序记录数组同样大小的辅助数组。O(n) 这是这个算法的缺点。

**归并排序算法是一个稳定的排序算法。**

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[Link 1]: https://steve.blog.csdn.net/article/details/95931848
[Link 2]: https://steve.blog.csdn.net/article/details/95934166
[Link 3]: https://steve.blog.csdn.net/article/details/95935599
[-]: https://steve.blog.csdn.net/article/details/96337444
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211205/40d3191bb5584e44a1797909e7a6bea3.png
[github]: https://github.com/yohstone/data-structure/blob/master/sort.cpp