数据结构与算法之归并排序

灰太狼 2023-07-09 02:14 1阅读 0赞

**归并排序：  
将数组分解为左右两个部分，不断对左右两个部分进行左右递归分解，  
直到每个部分只有一个元素，然后对不断对其进行合并，最终经过n-1次合并  
成为有序序列；**

**分解过程**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]

**合并过程：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 1]

**代码：**

package com.yg.sort;/*
    @author  Mu_Mu
    @date    2020/2/27  10:13
    
    */
    
    import java.util.Arrays;
    
    public class MergetSort {
        
        public static void main(String[] args) {
        
            int []arr={
        8,4,5,7,1,2,9};
            int []temp=new int[arr.length];
            mergeSort(arr,0,arr.length-1,temp);
            System.out.println(Arrays.toString(arr));
        }
    
    
        //分+合
        public static void mergeSort(int []arr,int left,int right,int []temp){
        
            if(left<right){
        
                int mid=(left+right)/2;
                //向左分治
                mergeSort(arr,left,mid,temp);
                //向右分治
                mergeSort(arr,mid+1,right,temp);
                //合并
                merge(arr,left,mid,right,temp);
    
            }
        }
    
    
    //合并算法 总共合并n-1次
    /*
    
    * @param arr 需要排序的数组
     * @param left 需要合并的左边的索引
     * @param mid  中间索引
     * @param right 需要合并的右边索引
     * @param temp  存放合并后数据的数组
            * @return : void
            * @date : 2020/2/27 11:00
     */
    
        public static void merge(int []arr,int left,int mid,int right,int[]temp){
        
            int l=left;//左边数组的索引
            int r=mid+1;//右边数组的索引
            int t=0;//tem的索引
            while (l<=mid && r<=right){
        
                if(arr[l]<=arr[r]){
        
                    temp[t]=arr[l];
                    t++;
                    l++;
                }else {
        
                    temp[t]=arr[r];
                    t++;
                    r++;
                }
            }
            //如果左边还未全部进入temp，就将左边依次加入temp
                while (l<=mid){
        
                    temp[t]=arr[l];
                    t++;
                    l++;
                }
    
                //如果右边还未全部进入temp，就将右边依次加入temp
            while (r<=right){
        
                temp[t]=arr[r];
                t++;
                r++;
            }
    
            //将temp数组的元素拷贝到arr中
            t=0;
            //第一次合并tempLeft为0，right=1    第二次tempLeft为2，right=3
            //最后一次tempLeft为0，right=n-1
            int tempLeft=left;
            while (tempLeft<=right){
        
                arr[tempLeft]=temp[t];
                t++;
                tempLeft++;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020022713111535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227131154782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk=,size_16,color_FFFFFF,t_70