归并排序JAVA实现(详解)

小咪咪 2022-09-06 10:21 126阅读 0赞

归并排序,顾名思义,就是递归和合并的过程.归并排序的时间复杂度是O(nlogn)。该算法采用经典的分治（divide-and-conquer）策略.（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)  
下面通过图文的方式来对归并进行详解:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]  
分阶段比较好理解,将整个长度的数组进行递归,使得得到的每一个数组都是有序的.  
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将\[4,5,7,8\]和\[1,2,3,6\]两个已经有序的子序列，合并为最终序列\[1,2,3,4,5,6,7,8\]，来看下实现步骤。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 2]

import java.util.Arrays;
    
    public class MergeSort { 
        public static void main(String[] args) { 
            int[] arr={ 11,24,25,86,64,2,3,63,43};
            System.out.println("归并排序前的序列为:"+ Arrays.toString(arr));
            sort(arr,0,arr.length-1);
            System.out.println("归并排序后的序列为:"+ Arrays.toString(arr));
        }
        public static  int[] sort(int[] data,int low,int high){ 
            int mid=(low+high)/2;
            if(low < high){ 
                sort(data,low,mid);
                sort(data,mid+1,high);
                merge(data,low,mid,high);
            }
            return  data;
        }
    
        private static void merge(int[] data, int low, int mid, int high) { 
            int[] temp=new int[high-low+1];
            int i=low;
            int j=mid+ 1;
            int k=0;
            //比较两者,将最小的数添加到temp数组中
            while (i<=mid && j<=high){ 
                if(data[i]<data[j]){ 
                    temp[k++]=data[i++];
                }else{ 
                    temp[k++]=data[j++];
                }
            }
            //剩余的数添加到数组当中
            while (i<=mid){ 
                temp[k++]=data[i++];
            }
            //剩余的数添加到数组当中
            while (j<=high){ 
                temp[k++]=data[j++];
            }
            //最后去覆盖原来的数组
            for (int x=0;x<temp.length;x++){ 
                data[x+low]=temp[x];
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]: /images/20220829/031ea91a774a47b0a0c20a687ba0449f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/5dc309d607ca4dbf8483aa3c0e286aa2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/45de365bf56e4d698784b39759554c0b.png