归并排序

image.png image.png

空间复杂度O(n),时间复杂度O(nlog(n))

    public static void mergeSort(int[] a, int low, int high){
        if(low < high){
            int mid = (low+high)/2;
            //左排序
            mergeSort(a, low, mid);
            //右排序
            mergeSort(a, mid+1, high);
            //合并
            merge(a, low,mid,high);
        }
    }

    private static void merge(int[] a, int low, int center, int high) {
        int[]tempArr = new int[a.length];
        int mid = center +1;//右数组
        int temp = low;//左数组
        int third = low;//临时数组
        while(low <= center && mid<= high){
            //比较两个数组，谁小取谁
            if(a[low] <= a[mid]){
                tempArr[third++] = a[low++];
            }else{
                tempArr[third++] = a[mid++];
            }
        }
        //左剩余，全部加进去
        while(low <= center){
            tempArr[third++] = a[low++];
        }
        //右剩余，全部加进去
        while(mid <= high){
            tempArr[third++] = a[mid++];
        }
        //临时数组给原始数组赋值
        while(temp <= high){
            a[temp] = tempArr[temp];
            temp++;
        }
    }