【算法-排序算法-归并排序】

上篇文章说的是快速排序，这篇文章将归并排序。

归并排序和快速排序的思路有类似的地方，都是二分思想+递归调用的思路。但归并排序的核心技巧是两个有序数组的合并，快速排序的核心在于找到中间元素并使左边的元素小于中间元素，右边元素大于或等于中间元素。下面是练习代码

public class GuibinSort {
    public static void main(String[] args){
        int[] arrs = {12,3,5,1,7,5,44,80};
        gbsort(arrs,0,arrs.length-1);
        for (int b : arrs){
            System.out.print(b + "," );
        }
    }
    public static void gbsort(int[] arrs,int low,int high){
        if(low==high){
            return;
        }
        int mid = low + (high-low)/2;
        gbsort(arrs,low,mid);
        gbsort(arrs,mid+1,high);

        //两个排序数组合并，这里是核心思想，使用两个指针
        int j=mid+1;
        int i=low;
        int[] clone = arrs.clone();
        for(int k=low;k<=high;k++){
            if(i>mid && j<=high){
                arrs[k] = clone[j++];
                continue;
            }
            if(j>high && i<=mid){
                arrs[k] = clone[i++];
                continue;
            }
            if(clone[i]>clone[j]){
                arrs[k] = clone[j++];
                continue;
            }
            arrs[k] = clone[i++];
        }
    }
}