归并排序（Java）

ゝ一世哀愁。 2024-04-08 13:44 7阅读 0赞

#### 这里写目录标题 ####

*   *   *  6.9 归并排序
         *  本次归并排序出自韩顺平的数据结构与算法

#### 6.9 归并排序 ####

**基本介绍**

归并排序（MERGE—SORT） 是利用归并的思想实现的排序方式，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则是将分的阶段得到的各答案“修补”在一起，即分而治之。

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

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QIk1VOS4-1661761674839)(C:\\Users\\86139\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220828233038164.png)\]][img-QIk1VOS4-1661761674839_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220828233038164.png]

代码实现

package com.ldm.sort;
    
    import java.util.Arrays;
    
    /**
     * @author 梁东明
     * 2022/8/29
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class MergeSort {
        public static void main(String[] args) {
            int[] arr = {8,4,5,7,1,3,6,2};
            int[] temp = new int[arr.length];  //归并排序需要额外的空间
            //本人非常建议你在此处下一个断点,跟着debug一步一步查看代码的执行过程
            //这样有利于你理解代码,否则单单看注解很难看懂.
            mergerSort(arr,0, arr.length-1, temp);
            System.out.println("归并排序后~\n"+ Arrays.toString(arr));
        }
        //下面两个方法充分利用 分-治 的思想
        /**
         * 分解的方法
         * @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);
    
                //合并
                merge(arr,left,mid,right,temp);
            }
        }
    
        /**
         * //合并方法
         * @param arr  排序的数组
         * @param left  左边有序列表的初始索引
         * @param mid    中间索引
         * @param right  右边的索引
         * @param temp  做中转的临时数组
         */
        public static void merge(int[] arr,int left, int mid,int right,int[] temp){
            int i = left;   //初始化i,左边有序序列的初始索引
            int j = mid +1 ;   //初始化j,右边有序序列的初始索引
            int t = 0;       //指向temp数组的当前索引
    
            //第一步:
            //先把左右两边有序的数据按照规则填充到temp数组
            //直到左右两边的有序序列,有一边完全处理完毕
            while (i <=mid && j<=right){ //开始遍历左右两边
                if(arr[i] < arr[j]){ //谁小谁就进入temp数组,记得后移,方便后续遍历
                    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数组的元素重新插入到arr中
            //注意,并不是每次拷贝所有数据
            t = 0;
            int tempLeft = left;
            System.out.println("tempLeft=\t"+tempLeft +"\tright=\t"+ right);
            while(tempLeft <= right ){
                arr[tempLeft] = temp[t];
                t++;
                tempLeft++;
            }
        }
    }

#### 本次归并排序出自韩顺平的数据结构与算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 69-71p，视频共有三个，不到一个小时。二倍速20分钟即可看完。你确定不去听听韩老师的课？

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[4c7f2e11efa54659af337e48602a0f5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8b447fb7608b43438191efe87c9b9e63.png
[img-QIk1VOS4-1661761674839_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220828233038164.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c4530960426d4aad9113c23397324f4a.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=71&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031