白话解析归并排序

r囧r小猫 2023-05-30 06:03 22阅读 0赞

简单来说，归并排序主要是将多个有序的序列合并为一个有序的序列.

我们首先看下2个简单的数 **5 , 2  **，那么直接将5和2比较交换位置就变成 **2,5** 。然后再加2个数 **4,3 **，同理，比较交换变成 **3,4** 。

现在我们将**2,5** 和 **3,4** 这2个序列合并为一个有序序列, 对于没有什么算法基础的同学第一个想到可能是先找出最小的数，然后是第二小的数，第三小的数等等，最后依次将其放入一个新数组中即可完成。

但是今天我们来讨论另一种方案 , 我们先将2个序列的第一个数**2和3**进行比较选出较小的**2**放进新数组，然后将第一个序列下标后移一位为**5继续和3**比较选出较小的**3**放进新数组，再将第二个序列下标后移一位为**4继续和5**比较选出较小的**4**放进新数组，最后将**5**放进新数组，这样新数组的数据就为 **2,3,4,5** 的有序序列。这就叫做 **归并排序。**

现在我们来看下归并排序的代码：

public static void mergeSort(int arr[],int left,int right){
            if(left>=right)return;
    
            int mid=(right+left)/2;
    
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
    
            merge(arr,left,mid,right);
    
        }
    
        private static void merge(int[] arr, int left, int mid, int right) {
    
            int tmp[]=new int[right-left+1];
            int leftIndex=left;
            int rightIndex=mid+1;
            int tmpIndex=0;
    
            while (leftIndex<=mid && rightIndex<=right){
                if(arr[leftIndex]<=arr[rightIndex]){
                    tmp[tmpIndex++]=arr[leftIndex++];
                }else{
                    tmp[tmpIndex++]=arr[rightIndex++];
                }
            }
    
            int start=leftIndex,end=mid;
    
            if(rightIndex<=right){
                start=rightIndex;
                end=right;
            }
    
            while (start<=end){
                tmp[tmpIndex++]=arr[start++];
            }
    
            for(leftIndex=0;leftIndex<=right-left;leftIndex++){
                arr[left+leftIndex]=tmp[leftIndex];
            }
        }

mergeSort 方法中的 arr 为排序的数组， left 和 right 分别为arr数组 的左边界下标和右边界下标，这里是采用分治的方式对数组递归，然后进行归并排序的操作。也就是对数组不断进行二分，直至左边界大于等于右边界不能二分为止。

现在我们来看下数组 **5, 3, 2, 6, 4, 1** 的归并执行过程，其中合并就是指的是执行**merge**方法：

**                        5 3 2 6 4 1                 left=0   right=5  
                    第一次递归                5 3 2                     left=0   right=2  
                    第二次递归                  5 3                      left=0   right=1  
                    第三次递归                   5                        left=0   right=0  left>=right，达到终止条件返回  
                    第四次递归                   3                        left=1   right=1  left>=right，达到终止条件返回  
                    第一次合并           3 5 2 6 4 1                 left=0  mid=0 right=1  
                    第五次递归                   2                        left=2   right=2  left>=right，达到终止条件返回  
                    第二次合并           2 3 5 6 4 1                 left=0  mid=1 right=2  
                    第六次递归                6 4 1                     left=3   right=5  
                    第六次递归                 6 4                       left=3   right=4  
                    第六次递归                  6                         left=3   right=3  left>=right，达到终止条件返回  
                    第七次递归                  4                         left=4   right=4  left>=right，达到终止条件返回  
                    第三次合并           2 3 5 4 6 1                 left=3  mid=3 right=4  
                    第八次递归                  1                         left=5   right=5  left>=right，达到终止条件返回  
                    第四次合并           2 3 5 1 4 6                 left=3  mid=4 right=5  
                    第五次合并           1 2 3 4 5 6                 left=0  mid=2 right=5**

上面就是执行归并排序的详细过程了，**标红是归并过程中发生的数据交换。**

现在我们来详细解析一下**merge**方法，以上面的最后一次归并为例，我们看下merge的执行过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70][]

首先会创建一个 tmp 数组，用于存放已经排序的数据。然后以 **mid** 为中心分为左右2个子数组，分别用 **leftIndex**和**rightIndex** 2个下标进行遍历，选出较小的那个数，将其对应的下标加1，循环往复，直至遍历到终点为止。最后将子数组中剩余的数据放进tmp数组中，将tmp中的数据复制进原数组 arr 中即可。

### 归并优化： ###

针对merge方法，还有一种优化的方式:

private static void mergeGuard(int[] arr, int left, int mid, int right) {
            int[] leftArr = new int[mid - left + 2];
            int[] rightArr = new int[right - mid + 1];
    
            for (int i = 0; i <= mid - left; i++) {
                leftArr[i] = arr[left + i];
            }
            // 第一个数组添加哨兵（最大值）
            leftArr[mid - left + 1] = Integer.MAX_VALUE;
    
            for (int i = 0; i < right - mid; i++) {
                rightArr[i] = arr[mid + 1 + i];
            }
            // 第二个数组添加哨兵（最大值）
            rightArr[right-mid] = Integer.MAX_VALUE;
    
            int i = 0;
            int j = 0;
            int k = left;
            while (k <= right) {
                // 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
                if (leftArr[i] <= rightArr[j]) {
                    arr[k++] = leftArr[i++];
                } else {
                    arr[k++] = rightArr[j++];
                }
            }
        }

这个主要是将左右数组的边界分别存储整型的最大值，这样在归并的时候，就可以将左右数组中的所有数据都放进arr中，不需要在数据比较完成后，额外将边界数据放入新数组中。

### 总结： ###

归并排序，本质上就是采用分治的方式，将序列一点点拆分为一个个数，最后进行合并。但是人的思维都是正向的，将一个个数合并为一个有序序列时很容易理解，逆向将序列拆分再合并就比较难理解一点。本文先采用拆分的方式，带大家理解归并的核心，然后带领大家一步步的去深入理解归并排序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019111415284952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy,size_16,color_FFFFFF,t_70