归并排序

分组排序之后合并(自顶向下)

// O(nlogn)
public void sort(Integer[] arr){
    sort(arr,0,arr.length-1);
}

private void sort(Integer[] arr, int l, int r){
    if(l>=r){
        return;
    }
    int mid = l+(r-l)/2;
    sort(arr,l,mid);
    sort(arr,mid+1,r);
    merge(arr,l,mid,r);
}

private void merge(Integer[] arr,int l, int mid, int r){
    Integer[] temp = Arrays.copyOfRange(arr,l,r+1);
    int i = l;
    int j = mid + 1;
    for(int k = l; k <= r; k++){
        if(i > mid){
            arr[k] = temp[j - l];
            j++;
        }else if(j > r){
            arr[k] = temp[i - l];
            i++;
        }else if(temp[i-l] <= temp[j-l]){
            arr[k] = temp[i-l];
            i++;
        }else{
            arr[k] = temp[j-l];
            j++;
        }
    }
}

• 优化1-有序数组

private void sort(Integer[] arr, int l, int r){
    if(l>=r){
        return;
    }
    int mid = l+(r-l)/2;
    sort(arr,l,mid);
    sort(arr,mid+1,r);
    if(arr[mid] > arr[mid+1]){
        merge(arr,l,mid,r);
    }
}

• 优化2-数据量小时选用插入排序

private void sort(Integer[] arr, int l, int r){
    if(r-l<=15){
        // 插入排序
        return;
    }
    int mid = l+(r-l)/2;
    sort(arr,l,mid);
    sort(arr,mid+1,r);
    if(arr[mid] > arr[mid+1]){
        merge(arr,l,mid,r);
    }
}

• 优化3-内存优化

private void merge(Integer[] arr,int l, int mid, int r,Integer[] temp){
    // 将临时创建的空间放到最外面,以参数形式传递到这里
    // Integer[] temp = Arrays.copyOfRange(arr,l,r+1);
    // 拷贝区间元素,使之一样
    System.arraycopy(arr,l,temp,l,r-l+1);
    int i = l;
    int j = mid + 1;
    for(int k = l; k <= r; k++){
        if(i > mid){
            arr[k] = temp[j];
            j++;
        }else if(j > r){
            arr[k] = temp[i];
            i++;
        }else if(temp[i] <= temp[j]){
            arr[k] = temp[i];
            i++;
        }else{
            arr[k] = temp[j];
            j++;
        }
    }
}

自低向上

public void sortBU(Integer[] arr){
    Integer[] temp = Arrays.copyOf(arr,arr.length);
    int n = arr.length;
    for(int sz=1; sz<n; sz+=sz){
        for(int i=0; i+sz<n; i+=sz+sz){
            if(arr[i+sz-1]>arr[i+sz]){
                merge(arr,i,i+sz-1,Math.min(i+sz+sz-1,n-1),temp);
            }
        }
    }
}

归并排序应用

• 逆序数对个数

public int reversePairs(int[] nums){
    int[] temp = new int[nums.length];
    return sort(nums,0,nums.length-1,temp);
}

public int sort(int[] nums,int l,int r,int[] temp){
    if(l>=r){
        return 0;
    }
    int res = 0;
    int mid = l+(r-l)/2
    res += sort(nums,l,mid,temp);
    res += sort(nums,mid+1,r,temp);
    if(nums[mid]>nums[mid+1]){
        res += merge(nums,l,mid,r,temp);
    }
    return res;
}

public int merge(int[] nums,int l,int mid,int r,int[] temp){
    System.arraycopy(nums,l,temp,r-l+1);
    int i = l;
    int j = mid + 1;
    int res = 0;
    for(int k=l; k<=r; k++){
        if(i>mid){
            nums[k] = temp[j];
            j++;
        }else if(j>r){
            nums[k] = temp[i];
            i++;
        }else if(temp[i]<=temp[j]){
            nums[k] = temp[i];
            i++;
        }else{
            res = res + mid - i + 1;
            nums[k] = temp[j];
            j++;
        }
    }
    return res;
}