归并排序思路整理

逃离我推掉我的手 2023-02-17 15:53 5阅读 0赞

首先介绍一下归并排序:  
**归并排序是采用归并的思路进行排序，该算法采用经典的分治策略（把一个大问题分解为若干个小的问题进而求解的过程)。字面上看起来还是很抽象的，接下来给出归并排序的整个示意图：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
解释：这里的“分”和“治"的过程都是递归进行，实际上”分“过程不做任何操作，在”分“的过程中持续压栈，直到最后序列中的元素只有一个。然后再进行”治“也就是归并操作。这个部分需要在代码片段中认真体会。

前面说到”分“只是在逻辑上分裂序列，实际不做任何操作。重点就在于”治“也就是归并操作。那么，如何把分裂的元素归并成一个有序的序列呢？这里需要定义一个临时的数组temp\[\],用来存放排好序的序列。所以如何放置元素到临时数组temp\[\]又是一个问题。  
这里的放置原则是：**由于两个序列都已经有序，我们只需要从这两个序列的低位轮番比较，将比较结果小的值放置到temp\[\]临时数组中，然后继续拿出该值所在序列中的下一个元素比较，直到某个序列中没有元素后，再将另一方的剩余元素依次放置再temp\[\]临时数组后面即可。此时临时数组里面存放的序列是两个序列的有序合并，最后将临时数组拷贝给原数组即可。**

以上这个过程不难体会。

经过”分“和”治“的阶段，待排序列就已经成了有序序列。到此还不理解没关系，接下来给出完整代码，因为一段正确的代码是具有唯一逻辑性的，这段代码重点除了理解递归的过程之外还要理解temp\[\]拷贝的过程（它不是一次性拷贝的，而是每归并一次就拷贝一次）。

/**
         * 分裂+归并
         * @param arr 待排序数组
         * @param left 左序列起始下标
         * @param right 右序列起始下标
         * @param temp 临时数组
         */
        public static void mergerSort(int[] arr,int left,int right,int[] temp){
        
            if (left < right){
        
                int mid = (left + right) / 2;
                mergerSort(arr,left,mid,temp);//左递归
                mergerSort(arr,mid + 1,right,temp);//右递归
                merger(arr,left,mid,right,temp);//调用归并方法
            }
        }
        /**
         * 归并
         * @param arr 待排列数组
         * @param left 左序列起始下标
         * @param mid 用来分割左右序列
         * @param right 右序列起始下标
         * @param temp 临时数组
         */
        public static void merger(int[] arr,int left,int mid,int right,int[] temp){
        
            int i = left;//存储左序列起始下标
            int j = mid + 1;//存储右序列起始下标
            int t = 0;//临时数组下标
            //这个循环的过程就是两个有序序列直接比较的过程，小的放入到临时数组中
            while (i <= mid && j <= right){
        
                if (arr[i] < arr[j]){
        
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else {
        
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
            }
            //循环结束到此，表示左右序列已经比较完了，最后将剩余的数据依次放入temp数组
            while (i <= mid){
        
                temp[t] = arr[i];
                i++;
                t++;
            }
            while (j <= right){
        
                temp[t] = arr[j];
                j++;
                t++;
            }
            //至此temp已经存好了排序好的序列,然后将temp数组拷贝给原数组
            t = 0;//初始化
            int tempLeft = left;//临时存储left,
            while (tempLeft <= right){
        
                arr[tempLeft] = temp[t];
                t ++;
                tempLeft ++;
            }
    
        }

总结：可以看到，当待排序列中有8位元素时，只需要归并7此，80次则需要79次，n次也就需要归并n-1次。可以看到，归并次数呈线性增长。相比冒泡、插入排序的呈指数增长，归并排序的效率还是挺快的，经测试效率跟快速排序差不多。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200614222318127.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center