算法设计 - 分治法

深碍√TFBOYSˉ_ 2023-09-28 18:08 42阅读 0赞

**目录**

分治法

什么是分治法

分治思想和递归

分治法的适用条件

分治法实例

快速排序

快速排序的原理

快速排序的最优和最差情况下的时间复杂度推导

快速排序的实现 - 双边循环

快速排序的实现 - 单边循环

快速排序的优化 - 打乱有序数组

归并排序

归并排序和中国好声音晋级机制

归并排序的原理

归并排序的实现

归并排序的时间复杂度

归并排序的非递归实现

--------------------

# 分治法 #

## 什么是分治法 ##

分治法，即运用分治思想来设计算法。

## 分治思想和递归 ##

分治思想，即将大的问题分解成多个小问题，然后通过解决小问题，再将小问题的解合并为大问题的解。即中国古代“分而治之”的策略。

分治思想的实现依赖于递归，递归思想的本质就是分治思想。也就是说分治思想和递归二者是相辅相成的。

想要学好分治法，最好先学习递归

[算法设计 - 递归\_伏城之外的博客-CSDN博客][- _-CSDN]

## 分治法的适用条件 ##

1.  该问题的规模小到一定的程度就可以轻松求解（存在base case，即递归出口）
2.  该问题可以分为若干个规模较小的相同问题，并分解出来的问题的解可以合并为原始问题的解（能够relate hard case to simple case，即存在递归公式）
3.  该问题所分解出的各个子问题是相互独立的，即子问题之间不好含公共的子问题（避免无意义的重复递归）

# 分治法实例 #

## 快速排序 ##

### 快速排序的原理 ###

快速排序是基于分治思想设计的排序算法。

快速排序分解逻辑如下：

1.  选取无序数组中任意一个元素作为基准值pivot，遍历其他数组元素：
2.  将比pivot值大的数组元素放到pivot元素的右边
3.  将比pivot值小的数组元素放到pivot元素的左边
4.  此时pivot元素处于有序位置，但是pivot左边所有数组元素、pivot右边所有数组元素任然处于无序状态。
5.  将pivot左边所有数组元素当成一个无序子数组、pivot右边所有数组元素当一个无序子数组，重复上述逻辑
6.  当子数组只有一个元素，就可以退出上述逻辑

如下图，所以每次都取无序数组的首元素为基准值，将比基准值小的元素放到其左边，将比基准值大的元素放到其右边。

![fd93328fa69847fca91fdd10e3572fc7.png][]

按此分解逻辑，一个无序数组，将会被拆分两个无序子数组和一个有序元素，而无序子数组又重复此分解逻辑，直到子数组本身只有一个元素无法拆分时。

而分解的最终结果就是所有的元素都处于有序位置。

此时也就达到了排序目的，而无需合并操作了。

### 快速排序的最优和最差情况下的时间复杂度推导 ###

快速排序最优的情况是，每次数组拆分出来的两个子数组元素数目都是相等的，此时快速排序时间复杂度为：

*  第1轮需要拆分1次，每次约遍历n个元素
 *  第2轮需要拆分2次，每次约遍历n/2个元素
 *  第3轮需要拆分4次，每次约遍历n/4个元素
 *  第4轮需要拆分8次，每次约遍历n/8个元素
 *  ......
 *  第x轮需要拆分2^(x-1)次，每次约遍历n/2^(x-1)个元素，假设此时每个子数组元素个数为1，即每次只需要遍历1个元素，即 n/2^(x-1) = 1，则 x = logn + 1 ≈ logn

当n接近无穷大时，则每轮近似要遍历n个元素，一共要遍历 logn轮，所以时间复杂度为O(nlogn)

![dbb499119ed94f3bb395e6540b664a89.png][]

快速排序最差的情况是，数组本身就是有序的，此时

*  第1轮需要拆分1次（得到一个子数组长度为0，一个子数组长度为n-1），一共约遍历n个元素
 *  第2轮需要拆分1次（同上），一共约遍历n-1个元素
 *  第3轮需要拆分1次（同上），一共约遍历n-2个元素
 *  ......
 *  第x轮需要拆分1次，一共约遍历1个元素

即：总共需要遍历 1 + 2 + 3 +...+ (n-2) + (n-1) + n = n \* (n+1) / 2

当n接近无穷大时，时间复杂度约为O（n^2）

### 快速排序的实现 - 双边循环 ###

快速排序的实现方式分为两种：双边循环、单边循环。

双边循环实现：

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    rl.on("line", (line) => {
      const arr = line.split(",");
      quickSort(arr); // 4,7,2,0,9,6,8,1,3,5
    });
    
    /* 快速排序算法 */
    function quickSort(arr, start = 0, end = arr.length - 1) {
      if (start >= end) {
        return;
      }
    
      let pivot = arr[start];
      let left = start;
      let right = end;
      console.log(`pivot=${pivot}, left=${left}, right=${right}`); // test
      visibleCursor(arr, left, right); // test
    
      while (left !== right) {
        while (right > left && arr[right] >= pivot) {
          right--;
          visibleCursor(arr, left, right); // test
        }
    
        while (left < right && arr[left] <= pivot) {
          left++;
          visibleCursor(arr, left, right); // test
        }
    
        if (right > left) {
          let tmp = arr[right];
          arr[right] = arr[left];
          arr[left] = tmp;
          visibleCursor(arr, left, right); // test
        }
      }
    
      arr[start] = arr[left];
      arr[left] = pivot;
      visibleCursor(arr, left, right); // test
    
      quickSort(arr, start, left - 1);
      quickSort(arr, left + 1, end);
    }
    
    /* left、right游标打印 */
    function visibleCursor(arr, left, right) {
      console.log(arr.join(" "));
      console.log(
        arr
          .slice()
          .map((_, index) => {
            if (index === left) {
              if (left === right) {
                return "↑";
              }
              return "L";
            } else if (index === right) {
              return "R";
            } else {
              return " ";
            }
          })
          .join(" ")
      );
    }

双边循环快速排序，指的是使用两个游标left、right来界定左子数组范围、右子数组范围，left游标左边的就是左子数组，right游标右边的就是右子数组。

left、right游标工作原理如下：

初始时，left游标指向数组头部位置，代表左子数组暂无元素，right游标指向数组尾部位置，代表右子数组暂无元素。

之后，right游标开始向左游动，当right游标指向的数组元素小于pivot基准值时（表示该元素应该被放到左子数组中），则暂停游动，否则保持游动，直到right和left相遇才停止游动。

当right游标暂停游动时，left游标开始向右移动，当left游标指向的数组元素大于pivot基准时（表示该元素应该被放到右子数组中），则暂停游动，否则保持游动，直到left和right相遇才停止游动。

当left、right都暂停游动时，判断

*  若left === right，则停止游动
 *  若left !== right，则直接交换arr\[left\]和arr\[right\]值，继续当前数组的下一轮游动

当left、right都停止游动时，则此时left必然等于right，我们需要将arr\[left/right\]的元素值和arr\[start\]元素值交换。

此时我们会得到两个子数组，分别是 \[0，left-1\]数组索引范围，和\[left+1，arr.length-1\]数组索引范围，然后对这两个子数组分别进行双边循环快排，直到子数组只有一个元素时，退出快排。

具体实例，请看下面的运行日志，L代表游标left，R代表游标right

PS D:\Desktop\DS> node .\haha.js
    4,7,2,0,9,6,8,1,3,5
    pivot=4, left=0, right=9
    4 7 2 0 9 6 8 1 3 5     //如果R指向值小于pivot，则暂停左移，否则保持左移
    L                 R     
    4 7 2 0 9 6 8 1 3 5     //arr[R] = 3 < 4，R暂停左移，若R暂停左移，则L开始右移
    L               R  
    4 7 2 0 9 6 8 1 3 5     //如果L指向值大于pivot，则暂停右移，否则保持左移，此时arr[L]= 7 > 4
      L             R       
    4 3 2 0 9 6 8 1 7 5     //R、L都暂停移动时，若 R > L，则交换对应元素的值
      L             R       
    4 3 2 0 9 6 8 1 7 5     
      L           R         
    4 3 2 0 9 6 8 1 7 5     
        L         R         
    4 3 2 0 9 6 8 1 7 5     
          L       R         
    4 3 2 0 9 6 8 1 7 5     
            L     R         
    4 3 2 0 1 6 8 9 7 5     
            L     R         
    4 3 2 0 1 6 8 9 7 5     
            L   R           
    4 3 2 0 1 6 8 9 7 5     
            L R             
    4 3 2 0 1 6 8 9 7 5     // 当R、L指向同一个位置时，则停止游动，交换arr[start]和arr[L]的值
            ↑               
    1 3 2 0 4 6 8 9 7 5     // 此时L游标往左就是左子数组（不含L），R游标往右就是右子数组（不含R）
            ↑               
    pivot=1, left=0, right=3
    1 3 2 0 4 6 8 9 7 5     
    L     R                 
    1 3 2 0 4 6 8 9 7 5     
      L   R                 
    1 0 2 3 4 6 8 9 7 5     
      L   R                 
    1 0 2 3 4 6 8 9 7 5     
      L R                   
    1 0 2 3 4 6 8 9 7 5     
      ↑                     
    0 1 2 3 4 6 8 9 7 5
      ↑
    pivot=2, left=2, right=3
    0 1 2 3 4 6 8 9 7 5
        L R
    0 1 2 3 4 6 8 9 7 5
        ↑
    0 1 2 3 4 6 8 9 7 5
        ↑
    pivot=6, left=5, right=9
    0 1 2 3 4 6 8 9 7 5
              L       R
    0 1 2 3 4 6 8 9 7 5
                L     R
    0 1 2 3 4 6 5 9 7 8
                L     R
    0 1 2 3 4 6 5 9 7 8
                L   R
    0 1 2 3 4 6 5 9 7 8
                L R
    0 1 2 3 4 6 5 9 7 8
                ↑
    0 1 2 3 4 5 6 9 7 8
                ↑
    pivot=9, left=7, right=9
    0 1 2 3 4 5 6 9 7 8
                  L   R
    0 1 2 3 4 5 6 9 7 8
                    L R
    0 1 2 3 4 5 6 9 7 8
                      ↑
    0 1 2 3 4 5 6 8 7 9
                      ↑
    pivot=8, left=7, right=8
    0 1 2 3 4 5 6 8 7 9
                  L R
    0 1 2 3 4 5 6 8 7 9
                    ↑
    0 1 2 3 4 5 6 7 8 9
                    ↑

### 快速排序的实现 - 单边循环 ###

单边循环实现：

单边循环快速排序，指的是只依赖于于一个游标mark来界定左右子数组的范围，mark游标左边的范围就是左子数组，mark游标右边的范围就是右子数组。

mark游标无法单独进行工作，需要搭配for循环遍历数组元素的i指针同时工作才可以。

下面是mark游标和for循环i指针的工作原理：

初始时，mark指针指向数组头部位置，for循环从数组第二个元素开始遍历

for循环每遍历一个数组元素，都要和pivot基准值进行比较，若比pivot小，则意味着左子数组长度+1，即mark游标此时需要向右移动一位

然后交换mark指向的元素 和 for循环此时遍历的元素，即i指针指向的元素

之后，继续下一次循环，直到for循环遍历结束

需要注意的是，mark指向的元素是比pivot小的元素，所以最后需要将mark指向的元素和arr\[start\]元素交换位置。

此时mark游标左边都是比pivot小的元素，即形成左子数组，右边都是比pivot大的元素，即形成右子数组。

分别将左子数组和右子数组投入单边循环快排。直到子数组只有一个元素时，退出快排。

具体实例，请看下面的运行日志，m代表游标mark，i代表for循环指针。

PS D:\Desktop\DS> node .\haha.js
    4,7,2,0,6,8,1,3,5
    pivot=4, start=0, end=8
    4 7 2 0 6 8 1 3 5      // 初始时，m指向数组第一个元素，for循环指针i从数组第二个元素开始
    m i                    
    4 7 2 0 6 8 1 3 5      // for循环开始遍历数组元素
    m   i                  
    4 7 2 0 6 8 1 3 5      // 若for循环指针i遍历到的值小于pivot，则m++，表示拓展左子数组长度
      m i                  
    4 2 7 0 6 8 1 3 5      // 然后交换arr[m]和arr[i]的位置，让小于pivot的值加入到左子数组中
      m i                  
    4 2 7 0 6 8 1 3 5      // 交换完成后，继续for循环
      m   i                
    4 2 7 0 6 8 1 3 5      
        m i                
    4 2 0 7 6 8 1 3 5      
        m i                
    4 2 0 7 6 8 1 3 5      
        m   i              
    4 2 0 7 6 8 1 3 5      
        m     i            
    4 2 0 7 6 8 1 3 5      
        m       i          
    4 2 0 7 6 8 1 3 5      
          m     i          
    4 2 0 1 6 8 7 3 5      
          m     i          
    4 2 0 1 6 8 7 3 5      
          m       i        
    4 2 0 1 6 8 7 3 5      
            m     i        
    4 2 0 1 3 8 7 6 5      
            m     i        
    4 2 0 1 3 8 7 6 5      // 当for循环结束时，m右边都是大于pivot的值，而m左边除了第一个元素外
            m       i      
    3 2 0 1 4 8 7 6 5      // 都是小于pivot的值，而m自身指向的元素是小于pivot的值，所以交换arr[m]和arr[start]的值
            m              
    pivot=3, start=0, end=3
    3 2 0 1 4 8 7 6 5      
    m i                    
    3 2 0 1 4 8 7 6 5
      m
    3 2 0 1 4 8 7 6 5
      m
    3 2 0 1 4 8 7 6 5
      m i
    3 2 0 1 4 8 7 6 5
        m
    3 2 0 1 4 8 7 6 5
        m
    3 2 0 1 4 8 7 6 5
        m i
    3 2 0 1 4 8 7 6 5
          m
    3 2 0 1 4 8 7 6 5
          m
    1 2 0 3 4 8 7 6 5
          m
    pivot=1, start=0, end=2
    1 2 0 3 4 8 7 6 5
    m i
    1 2 0 3 4 8 7 6 5
    m   i
    1 2 0 3 4 8 7 6 5
      m i
    1 0 2 3 4 8 7 6 5
      m i
    0 1 2 3 4 8 7 6 5
      m
    pivot=8, start=5, end=8
    0 1 2 3 4 8 7 6 5
              m i
    0 1 2 3 4 8 7 6 5
                m
    0 1 2 3 4 8 7 6 5
                m
    0 1 2 3 4 8 7 6 5
                m i  
    0 1 2 3 4 8 7 6 5
                  m
    0 1 2 3 4 8 7 6 5
                  m
    0 1 2 3 4 8 7 6 5
                  m i
    0 1 2 3 4 8 7 6 5
                    m
    0 1 2 3 4 8 7 6 5
                    m
    0 1 2 3 4 5 7 6 8
                    m
    pivot=5, start=5, end=7
    0 1 2 3 4 5 7 6 8
              m i
    0 1 2 3 4 5 7 6 8
              m   i
    0 1 2 3 4 5 7 6 8
              m
    pivot=7, start=6, end=7
    0 1 2 3 4 5 7 6 8
                m i
    0 1 2 3 4 5 7 6 8
                  m
    0 1 2 3 4 5 7 6 8
                  m
    0 1 2 3 4 5 6 7 8
                  m

### 快速排序的优化 - 打乱有序数组 ###

如果一个数组本身就是有序的，然后对他进行快速排序，则此时时间复杂度会变为O(n^2)，为了避免这种极端情况，我们需要随机打乱原数组的排序，来避免快速排序一个有序数组。

我们以双边循环为例，来改进算法

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    rl.on("line", (line) => {
      const arr = line.split(",");
      quickSort(arr); // 1,2,3,4,5,6,7,8,9
    
    /* 快速排序算法 */
    function quickSort(arr, start = 0, end = arr.length - 1) {
      if (start >= end) {
        return;
      }
    
      randomSwap(arr, start, end); // 每次快排前，将数组指定范围内的首元素和其他元素交换，避免快排一个有序数列
    
      let pivot = arr[start];
      let left = start;
      let right = end;
      console.log(`pivot=${pivot}, left=${left}, right=${right}`); // test
      visibleCursor(arr, left, right); // test
    
      while (left !== right) {
        while (right > left && arr[right] >= pivot) {
          right--;
          visibleCursor(arr, left, right); // test
        }
    
        while (left < right && arr[left] <= pivot) {
          left++;
          visibleCursor(arr, left, right); // test
        }
    
        if (right > left) {
          let tmp = arr[right];
          arr[right] = arr[left];
          arr[left] = tmp;
          visibleCursor(arr, left, right); // test
        }
      }
    
      arr[start] = arr[left];
      arr[left] = pivot;
      visibleCursor(arr, left, right); // test
    
      quickSort(arr, start, left - 1);
      quickSort(arr, left + 1, end);
    }
    
    /* 打乱有序数列 */
    function randomSwap(arr, start, end) {
      console.log("before swap:" + arr);
      const diff = end - start + 1;
      const index = Math.floor(Math.random() * diff);
      let tmp = arr[start + index];
      arr[start + index] = arr[start];
      arr[start] = tmp;
      console.log("after swap:" + arr);
    }
    
    /* left、right游标打印 */
    function visibleCursor(arr, left, right) {
      console.log(arr.join(" "));
      console.log(
        arr
          .slice()
          .map((_, index) => {
            if (index === left) {
              if (left === right) {
                return "↑";
              }
              return "L";
            } else if (index === right) {
              return "R";
            } else {
              return " ";
            }
          })
          .join(" ")
      );
    }

PS D:\Desktop\DS> node .\haha.js
    1,2,3,4,5,6,7,8,9
    before swap:1,2,3,4,5,6,7,8,9
    after swap:5,2,3,4,1,6,7,8,9 
    pivot=5, left=0, right=8     
    5 2 3 4 1 6 7 8 9
    L               R
    5 2 3 4 1 6 7 8 9
    L             R  
    5 2 3 4 1 6 7 8 9
    L           R    
    5 2 3 4 1 6 7 8 9
    L         R      
    5 2 3 4 1 6 7 8 9
    L       R        
    5 2 3 4 1 6 7 8 9
      L     R        
    5 2 3 4 1 6 7 8 9
        L   R        
    5 2 3 4 1 6 7 8 9
          L R        
    5 2 3 4 1 6 7 8 9
            ↑        
    1 2 3 4 5 6 7 8 9
            ↑        
    before swap:1,2,3,4,5,6,7,8,9
    after swap:2,1,3,4,5,6,7,8,9 
    pivot=2, left=0, right=3     
    2 1 3 4 5 6 7 8 9
    L     R
    2 1 3 4 5 6 7 8 9
    L   R
    2 1 3 4 5 6 7 8 9
    L R
    2 1 3 4 5 6 7 8 9
      ↑
    1 2 3 4 5 6 7 8 9
      ↑
    before swap:1,2,3,4,5,6,7,8,9
    after swap:1,2,3,4,5,6,7,8,9 
    pivot=3, left=2, right=3
    1 2 3 4 5 6 7 8 9
        L R
    1 2 3 4 5 6 7 8 9
        ↑
    1 2 3 4 5 6 7 8 9
        ↑
    before swap:1,2,3,4,5,6,7,8,9
    after swap:1,2,3,4,5,8,7,6,9
    pivot=8, left=5, right=8
    1 2 3 4 5 8 7 6 9
              L     R
    1 2 3 4 5 8 7 6 9
              L   R
    1 2 3 4 5 8 7 6 9
                L R
    1 2 3 4 5 8 7 6 9
                  ↑
    1 2 3 4 5 6 7 8 9
                  ↑
    before swap:1,2,3,4,5,6,7,8,9
    after swap:1,2,3,4,5,6,7,8,9
    pivot=6, left=5, right=6
    1 2 3 4 5 6 7 8 9
              L R
    1 2 3 4 5 6 7 8 9
              ↑
    1 2 3 4 5 6 7 8 9
              ↑

## 归并排序 ##

### 归并排序和中国好声音晋级机制 ###

归并排序非常类似于电视节目中音乐类选秀节目的晋级机制。

比如，中国好声音，

*  每个导师会通过盲选得到14名学员
 *  第一轮PK：14名学员进行两两分组，共7组，每组组内学员进行PK，胜出者可以晋级下一轮比赛，第一轮PK结束后，每个导师会得到7强学员，
 *  第二轮PK：7强学员再进行两两分组，而匹配不到对手的学员，直接晋级四强，剩余3组进行组内PK，得出其余三名四强学员。
 *  第三轮PK：4强学员继续两两分组PK，得出二强学员。
 *  第四轮PK：2强学员PK，得出最强学员。

最后四位导师带着各自的最强学员，进行总决赛。

当然，上面的晋级机制选拔出来的冠军是赛制公平的，但是亚军、季军、殿军是不公平的。

为什么这么说呢？

我们假设给14名学员的实力进行1~14的标记，1代表最弱，14代表最强。

![8f7ab5457f5c47269490b20cf2ce5e98.png][]

我们可以发现，冠军14确实是最强的，但是亚军12并非实力使然，而是利用了晋级机制的漏洞。真实实力排名亚军的13，由于运气比较差，在第一轮就遇到了冠军实力的14，所以早早退场。

因此为了保证公平，一般赛制都会引入复活赛概念。所谓复活赛，即在每轮比赛失败的学员中进行PK，复活出实力较强的失败学员，然后让他们再次挑战已经晋级的学员，将因为运气晋级的学员PK下去。

但是复活赛机制依旧不是公平的。

真正公平的赛制是这样的，比如第一轮选拔中，13被14PK下去了，这只能证明13的实力弱于14，并不能证明13的实力弱于第一轮中其他晋级选手，所以为了公平，13可以继续跳转除了14外的所有选手。

而这就是归并排序。

### 归并排序的原理 ###

归并排序是基于分治思想设计的排序算法。

归并排序的分解逻辑是，将无序数组不停的进行平分，每次平分都得到两个子序列，直到平分得到的子序列只有一个元素时，才停止平分。

如下图，就是归并排序对无序数组的分解过程，原数组为\[4,7,2,0,9,6,8,1,3,5\]，共10个元素，第一轮分解时，start=0，end=9, mid = (start+end)/2 = 4，则start~mid（0~4）分为一个子序列，mid+1~end（5~9）分为一个子序列。然后利用同样地方式将子序列平分，直到分解出来的子序列只有一个元素无法平分时停止。

![c8ee7d1520e3469db73a57c0fbda838f.png][]

当归并排序某个子序列完成彻底分解后，就可以进行合并操作，而合并操作就是将子序列合并为父序列/原数组的过程，并且合并前，需要对子序列与子序列进行比较排序。

![ac5b13a2031d44aea3195d6b0a939931.png][]

例如，\{4,7\}序列分解为4、7后就无法再次分解了，此时我们可以比较4、7，将小的首先放入父序列头部，然后再放其他的。

按此操作，即最终\{4,7\}序列内容依旧是\{4,7\}

![ce1310b6bb1e40c68462ffeaa61aee0d.png][]

此时\{4,7\}序列有序了，\{2\}只有单个元素所以也是有序的，因此可以将它们合并会父序列中。合并前，需要比较排序。

此时的比较策略是，先将\{4,7\}序列的最小值和\{2\}序列的最小值进行比较，小的先放入父序列中。

由于\{4,7\}序列是有序的，所以4是该序列的最小值，而\{2\}序列只有一个元素，所以2就是自身序列的最小值，比较4，2，发现2更小，所以将2放入父序列中，然后\{2\}序列就没有元素了，换句话说，\{4,7\}序列没有了比较对象了，因此\{4,7\}序列整个放入父序列中，因此父序列为\{2,4,7\}。

![0d3b4d4f54f1440c8653c64d3b951b75.png][]

接着，比较0，9，得到有序序列\{0,9\}

![1ea978b1d2bd4056b1ddcf8f9951fe9a.png][]

此时，\{2,4,7\}有序了，\{0,9\}有序了，因此可以将它们合并到父序列了。同样地，在合并前，对两个序列进行比较排序，

*  首先比较两个序列的最小值，即比较\{2,4,7\}的2，和\{0，9\}的0，最终0较小，被首先放入父序列中
 *  之后，比较\{2,4,7\}序列和\{9\}序列的最小值，即2和9的比较，最终2较小，被放入父序列
 *  之后，比较\{4,7\}序列和\{9\}序列的最小值，即4和9的比较，最终4较小，被放入父序列
 *  之后比较\{7\}序列和\{9\}序列的最小值，即7和9的比较，最终7较小，被放入父序列
 *  此时\{2,4,7\}序列的元素全部被放入了父序列，因此\{9\}序列没有了比较对象，直接放入父序列

因此父序列元素为\{0,2,4,7,9\}

按照上面的方式，同理可得如下

![c6ec552a5ffe4140a8245eb7c972c29f.png][]

### 归并排序的实现 ###

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    rl.on("line", (line) => {
      const arr = line.split(",");
      mergeSort(arr); // 4,7,2,0,9,6,8,1,3,5
      console.log(arr.join(" "));
    });
    
    /* 归并排序 */
    function mergeSort(arr, start = 0, end = arr.length - 1) {
      /* 归并排序分解逻辑 */
      if (start < end) { // 当子序列只有一个元素时，停止分解
        let mid = Math.floor((start + end) / 2);
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end); //分解到子序列只有一个元素时，或子序列有序时，进行合并
      }
    }
    
    /* 归并排序合并逻辑 */
    function merge(arr, start, mid, end) {
      let tmp = []; // tmp数组作为存储父序列的临时容器
      let i = start; // 游标i，指向有序子序列（start~mid）最小值的位置，初始时，有序子序列（start~mid）最小值的位置在start
      let j = mid + 1; // 游标j，指向有序子序列（mid+1~end）最小值的位置，初始时，有序子序列（mid+1~end）最小值的位置在mid+1
    
      for (let k = start; k <= end; k++) { // for循环的k是tmp数组的索引，我们需要将两个子序列排序后合入父序列中，因此k的循环范围是start~end
        if (i > mid) { // 当游标i已经超出子序列（start~mid）范围，则表示当前子序列元素已经全部加入父序列，因此另一个子序列（mid+1, end）的元素已经没有比较对象，可以直接加入父序列
          tmp[k] = arr[j++];
        } else if (j > end) { // 当游标j已经超出子序列（mid+1~end）范围，则表示当前子序列元素已经全部加入父序列，因此另一个子序列（start, mid）的元素已经没有比较对象，可以直接加入父序列
          tmp[k] = arr[i++];
        } else if (arr[i] < arr[j]) { // 比较两个子序列的最小值，将较小的存入tmp中，然后对应游标位置后移一位，表示之前游标指向的最小值已经合入父序列tmp中，同时tmp的k也随着for循环自增
          tmp[k] = arr[i++];
        } else {
          tmp[k] = arr[j++];
        }
      }
    
      for (let n = start; n <= end; n++) { // 将tmp数组中存储的父序列合入原始数组对应范围
        arr[n] = tmp[n];
      }
    }

### 归并排序的时间复杂度 ###

归并排序分解过程不停的将数组进行二分，假设数组元素有n个，则最多要分解logn轮，

![a25c57c459dc47f0b3f9527a8047e1d0.png][]

然后每轮合并时比较排序的次数最多是n次，因此归并排序的时间复杂度为O(nlogn)。

### 归并排序的非递归实现 ###

归并排序的递归实现中，递归仅用于将无序数组不停的平分，直到无序数组被平分至所有子序列都只有一个元素。如下图所示：

![a25c57c459dc47f0b3f9527a8047e1d0.png][]

也就是说，递归分解的最终目的是将

\[4,7,2,0,9,6,8,1,3,5\] 分解为 \{4\},\{7\},\{2\},\{0\},\{9\},\{6\},\{8\},\{1\},\{3\},\{5\}

然后进行合并。

但是，\[4,7,2,0,9,6,8,1,3,5\] 分解为 \{4\},\{7\},\{2\},\{0\},\{9\},\{6\},\{8\},\{1\},\{3\},\{5\} 的工作，并不一定要依赖于递归，通过for循环遍历出每一个数组元素，也能够完成 \[4,7,2,0,9,6,8,1,3,5\] 分解为 \{4\},\{7\},\{2\},\{0\},\{9\},\{6\},\{8\},\{1\},\{3\},\{5\} 的工作。并且改用for的话，消耗的内存要比递归函数小很多。

只是分解后的如何合并成了新的问题？

采用递归实现的归并排序的合并流程是依赖于分解流程的，也就是说基于递归的合并流程，其实是自顶向下的递归的回溯流程。

而当前我们不再使用递归来进行分解，而是采用for来进行分解，则合并流程就如下图所示，变成一个单纯的自底向上的流程。

![d6ee64cc41a54d33837e2ac29938d44f.png][]

自底向上的合并流程

*  第一轮：每两个元素合并为一个有序序列
 *  第二轮：每四个元素（两组有序序列）合并为一个有序序列
 *  第三轮：每八个元素（两组有序序列）合并为一个有序序列
 *  ......

如果原数组一共有n个元素，则需要合并 logn 轮，考虑到 logn 可能不是整数，所以对其进行向上取整。

因此，实现代码如下：

[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/126070168?spm=1001.2014.3001.5501
[fd93328fa69847fca91fdd10e3572fc7.png]: https://img-blog.csdnimg.cn/fd93328fa69847fca91fdd10e3572fc7.png
[dbb499119ed94f3bb395e6540b664a89.png]: https://img-blog.csdnimg.cn/dbb499119ed94f3bb395e6540b664a89.png
[8f7ab5457f5c47269490b20cf2ce5e98.png]: https://img-blog.csdnimg.cn/8f7ab5457f5c47269490b20cf2ce5e98.png
[c8ee7d1520e3469db73a57c0fbda838f.png]: https://img-blog.csdnimg.cn/c8ee7d1520e3469db73a57c0fbda838f.png
[ac5b13a2031d44aea3195d6b0a939931.png]: https://img-blog.csdnimg.cn/ac5b13a2031d44aea3195d6b0a939931.png
[ce1310b6bb1e40c68462ffeaa61aee0d.png]: https://img-blog.csdnimg.cn/ce1310b6bb1e40c68462ffeaa61aee0d.png
[0d3b4d4f54f1440c8653c64d3b951b75.png]: https://img-blog.csdnimg.cn/0d3b4d4f54f1440c8653c64d3b951b75.png
[1ea978b1d2bd4056b1ddcf8f9951fe9a.png]: https://img-blog.csdnimg.cn/1ea978b1d2bd4056b1ddcf8f9951fe9a.png
[c6ec552a5ffe4140a8245eb7c972c29f.png]: https://img-blog.csdnimg.cn/c6ec552a5ffe4140a8245eb7c972c29f.png
[a25c57c459dc47f0b3f9527a8047e1d0.png]: https://img-blog.csdnimg.cn/a25c57c459dc47f0b3f9527a8047e1d0.png
[d6ee64cc41a54d33837e2ac29938d44f.png]: https://img-blog.csdnimg.cn/d6ee64cc41a54d33837e2ac29938d44f.png