【算法100天 | 12】归并排序的非递归写法（Java实现）

痛定思痛。 2023-09-26 11:14 27阅读 0赞

#### 文章目录 ####

*   *  一、归并排序（递归版）
     *   *  1、思路
         *  2、代码
     *  二、归并排序（迭代版）
     *   *  1、思路
         *  2、代码

### 一、归并排序（递归版） ###

#### 1、思路 ####

归并排序算法的核心思想：分治；

> **分治包含两步：分、合**
> 
> 1.  分：将一个大问题划分成很多个小的问题，然后递归处理；
> 2.  合：将分阶段处理小问题后的结果整合到起来。

![在这里插入图片描述][c4bc63eb089445988c59b3f334881491.png]

图片引自：https://blog.csdn.net/estxiyang/article/details/118528016。

#### 2、代码 ####

/**
     * 归并排序（递归版），时间复杂度：O(nlogn)，空间复杂度：O(n)
     */
    public static void sort(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return;
        }
        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = new int[arr.length];
        sort(arr, 0, arr.length - 1, temp);
    }
    
    // 第一步：分
    private static void sort(int[] arr, int left, int right, int[] temp) {
        
        if (left == right) {
        
            return;
        }
        int mid = left + (right - left) / 2;
        // 左边归并排序，使得左子序列有序
        sort(arr, left, mid, temp);
        // 右边归并排序，使得右子序列有序
        sort(arr, mid + 1, right, temp);
        // 将两个有序子数组合并操作
        merge(arr, left, mid, right, temp);
    }
    
    // 第二步：合
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        
        // 左序列指针
        int pLeft = left;
        // 右序列指针
        int pRight = mid + 1;
        // 临时数组指针
        int t = 0;
        while (pLeft <= mid && pRight <= right) {
        
            temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
        }
        // 将左序列剩余元素填充进temp中
        while (pLeft <= mid) {
        
            temp[t++] = arr[pLeft++];
        }
        // 将右序列剩余元素填充进temp中
        while (pRight <= right) {
        
            temp[t++] = arr[pRight++];
        }
    
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while (left <= right) {
        
            arr[left++] = temp[t++];
        }
    }

我们都知道归并排序的时间复杂度：O(nlogn)，空间复杂度：O(n)；但从递归版本的代码我们不太好看出这个时间复杂度为什么为O(nlogn)，下面看迭代版本的代码，时间复杂度就很清晰。

### 二、归并排序（迭代版） ###

#### 1、思路 ####

在递归版版本中有一个隐式的步长概念，而步长的范围为\[`1` , `array.lenth / 2`)，就整个递归的过程来看：

> 1.  步长为1代表最底层的递归，即：每两个数字一组进行排序；
> 2.  步长为2代表次底层的递归，即：每四个数字一组进行排序（而这四个数字中前两个和后两个各是有序的）；
> 3.  … 直到最后步长刚好大于等于`array.lenth / 2`，进行排序的一组数据囊括了数组中所有的数据。

迭代依旧沿用递归的思想，区别在于：迭代版本中需要显式的操作步长。

**在操作步长的过程中，有三个边界问题需要特殊处理：**

> 1.  数组中剩余的数据不超过一个半组（左半组），则不需要对剩余的数据分组归并，进而调整步长，以 2 \* mergeStep分组排序；
>     
>         if (mergeStep >= n - left) {
>                
>             break;
>         }
> 2.  右半组的数据数据不足够时，右边界为：`n - 1`；
>     
>         int right = Math.min(mid + mergeStep, n - 1);
>         merge(arr, left, mid, right, temp);
> 3.  步长超过数组的一半，说明已经排序结束了。

#### 2、代码 ####

/**
     * 归并排序（迭代版），时间复杂度：O(nlogn)，空间复杂度：O(n)
     */
    public static void sort2(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return;
        }
        int n = arr.length;
        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = new int[n];
    
        // 步长 （即 步长 + 1个数放在一起排序）
        int mergeStep = 1;
        while (mergeStep < n) {
        
            // 左组中的第一个位置
            int left = 0;
            // 把整个数组中所有的数据全局以mergeStep分组排序
            while (left < n) {
        
                // 数组中剩余的数据不超过一个半组（左半组），则不需要分组归并，进而调整步长，以 2 * mergeStep分组排序
                if (mergeStep >= n - left) {
        
                    break;
                }
                int mid = left + mergeStep - 1;
                // 右半组的数据足够，右边界是mid + mergeStep；数据不足够，右边界则是：n - 1
                int right = Math.min(mid + mergeStep, n - 1);
                merge(arr, left, mid, right, temp);
                left = right + 1;
            }
            // 步长超过数组的一半，说明已经排序结束了，再继续循环，会出现边界溢出问题。比如数组的长度为int的最大值，
            if (mergeStep > n / 2) {
        
                break;
            }
            // 调整步长，以 2 * mergeStep分组排序
            mergeStep <<= 1;
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        
        // 左序列指针
        int pLeft = left;
        // 右序列指针
        int pRight = mid + 1;
        // 临时数组指针
        int t = 0;
        while (pLeft <= mid && pRight <= right) {
        
            temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
        }
        // 将左序列剩余元素填充进temp中
        while (pLeft <= mid) {
        
            temp[t++] = arr[pLeft++];
        }
        // 将右序列剩余元素填充进temp中
        while (pRight <= right) {
        
            temp[t++] = arr[pRight++];
        }
    
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while (left <= right) {
        
            arr[left++] = temp[t++];
        }
    }

[c4bc63eb089445988c59b3f334881491.png]: https://img-blog.csdnimg.cn/c4bc63eb089445988c59b3f334881491.png