归并排序

方法

[L,R]范围排序

先求出中点位置,先把左侧排好序,然后右侧排好序,然后整合(merge)

代码实现

public class MergeSort {
    public static void sort(int[] arr){
        if (arr ==null || arr.length <2){
            return;
        }
        process(arr,0,arr.length-1);
    }
    //分析时间复杂度的区域
    public static void process(int[] arr,int left,int right){
        if (left == right){
            return;
        }//O(1)
        int mid = left + (right-left)/2;//O(1)
        process(arr,left,mid);//调用子过程
        process(arr,mid+1,right);//调用子过程
        merge(arr,left,mid,right);//O(n)
    }
    public static void merge(int[] arr,int left,int mid,int right){
        //额外辅助空间
        int[] temp = new int[right-left+1];
        int i = 0;
        int p1 = left;//只往右走,不回退
        int p2 = mid+1;//只往右走,不回退
        //判断是否越界,没有越界的话,就谁小就拷贝到temp[]中,然后指针后移
        while (p1 <= mid && p2 <= right){
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //最终都会有一方越界,谁先越界就直接拷贝剩下的
        //P2先越界
        while (p1 <= mid){
            temp[i++] = arr[p1++];
        }
        //P1先越界
        while (p2 <= right){
            temp[i++] = arr[p2++];
        }
        //把temp[]中的数据拷贝回原来的数组中
        //时间复杂度O(n)
        for (i = 0; i < temp.length; i++) {
            arr[left+i] = temp[i];
        }
    }
}

时间复杂度

这就可以使用master求解时间复杂度了,master可以在算法工具专栏中查看

T(N) = 2*(T(N)/2) + O(n)

那么就是a=2,b=2,d=1

那么就是log(b,a) = d --> O(N^d*logN)

即时间复杂度是O(NlogN)