10年IT老兵重学数据结构与算法（五）

锻炼自己的写作能力第五弹，今天来谈谈和快速排序类似的归并排序，快速排序是找到合适的位置，先分割无序中的两段，在递归排序，而归并是每一段递归单独排序好，再进行最后的合并。两者的思想类似，但是方式上还是有点差异。

话不多说，进入举例子环节{8,4,5,7,1,3,6,2}，首先拆分获取数组的中位数，本例子中为1位中间节点，拆成8、4、5、7和1、3、6、2，分别对两段分别排序，这里运用了递归的思想，分开的两段继续拆分，直到最小拆分单元，这里识别为数组为最小单元即终止递归。

以下为引用某个大神的截图

这里合并数组，可以设定个临时的数组，以中间节点为边界，分别比对，假设4、5、7、8和1、2、3、6是分割后排序完成，则每次取分割后的比对，谁较小就存入最终的数组。

最后完成整个的排序。

 public static int[] temp;
    public static void mergeSort(int[] nums){
        temp=new int[nums.length];
        mergeSort(nums,0,nums.length-1);
    }
    public static void mergeSort(int[] nums,int lo,int hi){
        if(lo==hi){
            return;
        }

        int mid=lo+(hi-lo)/2;
        mergeSort(nums,lo,mid);
        mergeSort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
    }
    private static void merge(int[] nums, int lo, int mid, int hi){

        for(int i=lo;i<=hi;i++){
            temp[i]=nums[i];
        }
        int i=lo,j=mid+1;
        for(int p=lo;p<=hi;p++){
            if(i==mid+1){
                nums[p]=temp[j++];
            }else if(j==hi+1){
                nums[p]=temp[i++];
            }else if(temp[i]>temp[j]){
                nums[p]=temp[j++];
            }else{
                nums[p]=temp[i++];
            }
        }
    }