归并排序（常见经典排序算法）

我会带着你远行 2023-09-28 08:17 47阅读 0赞

> **步骤：1.将序列中待排序数字分为若干组，每个数字分为一组**
> 
>  **2.将若干个组两两合并，保证合并后的组是有序的**
> 
>  **3.重复第二步操作直到只剩下一组，排序完成**
> 
>  **基本思路：归并排序，先将数组进行拆分，每次拆成两份，然后继续拆分直到一组有两个元素为止，然后再进行两两整合排序，重复两两整合排序直至数组元素排序完成。**
> 
> **平均时间复杂度：O（nlogn）**

###  **两组两组整合过程如下图所示：** ###

![a868a38dbad8905e118a8408e9d7cb80.gif][]

![a7400f7d5353444999eb9a2412c2cf5e.png][]

![ae52441e11de48f39232fb8da1ce7c38.png][]

![ed1b258c35a14fd58a25da202422235f.png][]

![89f773208cce48918bc4d546249f9f6f.png][]

import java.util.Arrays;
    
    //归并排序：先分再合
    public class MergeSort {
        public static void main(String[] args) {
            int[] arr = {3,1,4,6,22,0,33,2,745,5,56,8};
            int[] temp = new int[arr.length];
            System.out.println("未排序数组："+ Arrays.toString(arr));
            mergeSort(arr,0,arr.length-1,temp);
            System.out.println("已排序数组："+ Arrays.toString(arr));
        }
    
        //mergeSort（）方法：将数组分组出来
        public static void mergeSort(int[] arr,int left,int right,int[] temp){
            //将数组进行分组
            if (left < right){
                int l = left;
                int r = right;
                int middle = (l+r)/2;
                //将分组进行排序整合
                merge(arr,left,middle,right,temp);//将左边的部分继续分
                mergeSort(arr,0,middle,temp);//将右边的部分继续分
                mergeSort(arr,middle+1,r,temp);
            }
        }
    
        public static void merge(int[] arr,int left,int middle,int right,int[] temp){
            int l = left;
            int r = middle+1;
            int t = 0;//用于临时数组下标索引
    
            while(l <= middle && r <= right){
                //先将两个部分整合
                temp[t++] = arr[l] <= arr[r]?arr[l++] : arr[r++];
    //            if (arr[l] <= arr[r]){
    //                temp[t] = arr[l];
    //                t++;l++;
    //            }else{
    //                temp[t] = arr[r];
    //                t++;r++;
    //            }
            }
            //如果左边的部分还有元素没有被合并，则接着l继续合并
            while(l <= middle){
                temp[t++] = arr[l++];
    //            temp[t] = arr[l];
    //            t++;l++;
            }
            //如果右边的部分还有元素没有被合并，则接着r继续合并
            while (r <= right){
                temp[t++] = arr[r++];
    //            temp[t] = arr[r];
    //            t++;r++;
            }
    
            //将temp临时数组中的元素顺序传到arr数组中
            t = 0;
            int tempLeft = left;
            while(tempLeft <= right){
                arr[tempLeft] = temp[t];
                tempLeft++;t++;
            }
        }
    }

**---end---**

**扫描下方二维码**

**添加好友，备注【交流】**

**可私聊相互学习，共同进步，资源共享**

![e8cc62348185492485d4c3bcb7c6657d.jpeg][]

[a868a38dbad8905e118a8408e9d7cb80.gif]: https://img-blog.csdnimg.cn/img_convert/a868a38dbad8905e118a8408e9d7cb80.gif
[a7400f7d5353444999eb9a2412c2cf5e.png]: https://img-blog.csdnimg.cn/a7400f7d5353444999eb9a2412c2cf5e.png
[ae52441e11de48f39232fb8da1ce7c38.png]: https://img-blog.csdnimg.cn/ae52441e11de48f39232fb8da1ce7c38.png
[ed1b258c35a14fd58a25da202422235f.png]: https://img-blog.csdnimg.cn/ed1b258c35a14fd58a25da202422235f.png
[89f773208cce48918bc4d546249f9f6f.png]: https://img-blog.csdnimg.cn/89f773208cce48918bc4d546249f9f6f.png
[e8cc62348185492485d4c3bcb7c6657d.jpeg]: https://img-blog.csdnimg.cn/e8cc62348185492485d4c3bcb7c6657d.jpeg