归并排序（Merge-Sort）

归并排序属于外部排序

基础部分

归并排序的算法思想：

左边处理一下（对左半边排序）

右边处理一下（对右半边排序）

最后处理左右两边的（两边一起处理）

代码实现

class MargeSort {
    public static void margeSort(int[] nums){
        margeSort(nums,0,nums.length - 1);
    }
    public static void margeSort(int[] nums,int l,int r){
        if(l >= r) return;
        int mid = (r + l) >> 1;
        margeSort(nums,l,mid);
        margeSort(nums,mid + 1,r);
        int[] numCopy = new int[r - l + 1];
        int k = 0;//numCopy的起始下标
        int i = l;//左数组的起始下标
        int j = mid + 1;//有数组的起始下标
        while(i <= mid || j <= r){
            if(j > r || (i <= mid && nums[i] < nums[j])){
                numCopy[k++] = nums[i++];
            }else{
                numCopy[k++] = nums[j++];
            }
        }
        for(int ind = l;ind <= r;ind++)
            nums[ind] = numCopy[ind - l];
    }
}

测试：

public class Main{
    public static void main(String args[]){
        int[] nums = new int[]{9,8,7,6,5,44,1,3,445,23};
        System.out.println(Arrays.toString(nums));
        MargeSort.margeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

[9, 8, 7, 6, 5, 44, 1, 3, 445, 23]
这里是已排序数组：[8, 9]
这里是已排序数组：[7, 8, 9]
这里是已排序数组：[5, 6]
这里是已排序数组：[5, 6, 7, 8, 9]
这里是已排序数组：[1, 44]
这里是已排序数组：[1, 3, 44]
这里是已排序数组：[23, 445]
这里是已排序数组：[1, 3, 23, 44, 445]
这里是已排序数组：[1, 3, 5, 6, 7, 8, 9, 23, 44, 445]
[1, 3, 5, 6, 7, 8, 9, 23, 44, 445]

归并排序在大数据场景下的应用

问题：电脑内存大小2GB，如何对一个40GB的文件进行排序

答：把40GB大文件分成20分2GB的小文件，然后借助外部存储区进行20路归并排序

经典面试题归并排序基础

LeetCode剑指 Offer 51. 数组中的逆序对

class Solution {
    int[] temp;
    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        return margeSort(nums,0,nums.length - 1);
    }
    public int margeSort(int[] nums,int l,int r){
        if(l >= r) return 0;
        int ans = 0;
        int mid = (l + r) >> 1;
        ans += margeSort(nums,l,mid);
        ans += margeSort(nums,mid + 1,r);
        int k = l;
        int p1 = l;
        int p2 = mid + 1;
        while(p1 <= mid || p2 <= r){
            if((p2 > r) || (p1 <= mid && nums[p1] <= nums[p2])){
                temp[k++] = nums[p1++];
            }else{
                temp[k++] = nums[p2++];
                ans += mid - p1 + 1;
            }
        }
        for(int i = l;i <= r;i++) nums[i] = temp[i];
        return ans;
    }
}

LeetCode23. 合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue priorityQueue = new PriorityQueue<>(
                new Comparator(){
                    public int compare(ListNode p,ListNode q){
                        return p.val - q.val;
                    }
                }
        );
        for(ListNode node : lists){
            if(node == null) continue;
            priorityQueue.offer(node);
        }
        ListNode head = new ListNode(0);
        ListNode node = head;
        while(!priorityQueue.isEmpty()){
            node.next = priorityQueue.poll();
            node = node.next;
            if(node.next != null) priorityQueue.offer(node.next);
        }
        return head.next;
    }
}

LeetCode148. 排序链表

class Solution {
    public ListNode sortList(ListNode head) {
        int n = 0;
        ListNode l = head;
        while(l != null){
            n++;
            l = l.next;
        }
        return margeSort(head,n);
    }
    public ListNode margeSort(ListNode node,int len){
        if(node == null || node.next == null) return node;
        int l = len / 2;
        int r = len - l;
        ListNode res = new ListNode(0);
        ListNode p = node;
        int ll = l;
        while(ll-- != 1){//寻找右链表的前一个节点
            p = p.next;
        }
        ListNode rightHead = p.next;
        p.next = null;
        ListNode ln = margeSort(node,l);
        ListNode rn = margeSort(rightHead,r);
        p = ln;
        ListNode q= rn;
        ListNode k = res;
        while(p != null || q != null){
            if(q == null ||(p != null && p.val < q.val)){
                k.next = p;
                p = p.next;
                k = k.next;
            }else{
                k.next = q;
                q = q.next;
                k = k.next;
            }
        }
        return res.next;
    }
}

LeetCode1305. 两棵二叉搜索树中的所有元素

class Solution {
    public List getAllElements(TreeNode root1, TreeNode root2) {
        List root1List = new ArrayList();
        List root2List = new ArrayList();
        List res = new ArrayList();
        treeMid(root1,root1List);
        treeMid(root2,root2List);
        while(!root1List.isEmpty() || !root2List.isEmpty()){
            if(root2List.isEmpty() || (!root1List.isEmpty() && root1List.get(0)  
归并排序进阶 
LeetCode327. 区间和的个数 
class Solution {
    long[] temp;
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sum = new long[nums.length + 1];
        temp = new long[nums.length + 1];
        sum[0] = 0;
        for(int i = 0;i = r) return 0;
        int mid = (l + r) >> 1;
        int ans =0;
        ans += mergeSort(sum,l,mid,lower,upper);
        ans += mergeSort(sum,mid + 1,r,lower,upper);
        ans += countTwoSum(sum,l,mid,mid + 1,r,lower,upper);
        //归并排序
        int k = l;
        int l1 = l;
        int l2 = mid + 1;
        while(l1 <= mid || l2 <= r){
            if(l2 > r ||(l1 <= mid && sum[l1] <= sum[l2])){
                temp[k++] = sum[l1++];
            }else{
                temp[k++] = sum[l2++];
            }
        }
        for(int i = l;i <= r;i++) sum[i] = temp[i];
        return ans;
    }
    public int countTwoSum(long[] sum,int l_start,int l_end,int r_start,int r_end,int lower,int upper){
        int ans = 0;
        int k1 = l_start;
        int k2 = l_start;
        for(int j = r_start;j <= r_end;j++){
            long a = sum[j] - upper;
            long b = sum[j] - lower;
            while(k1 <= l_end && sum[k1] < a) k1++;
            while(k2 <= l_end && sum[k2] <= b) k2++;
            ans += k2  - k1;
        }
        return ans;
    }
}
 
LeetCode315. 计算右侧小于当前元素的个数 
class Solution {
    Num[] temp;
    public List countSmaller(int[] nums) {
        Num[] num = new Num[nums.length];
        temp = new Num[nums.length];
        for(int i = 0;i < nums.length;i++){
            num[i] = new Num(nums[i],i);
        }
        mergeSort(num,0,num.length - 1);
        for(int i = 0;i < num.length;i++) temp[num[i].ind] = num[i];
        List res = new ArrayList();
        for(Num n : temp)
            res.add(n.cnt);
        return res;
    }
    public void mergeSort(Num[] num,int l,int r){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(num,l,mid);
        mergeSort(num,mid + 1,r);
        int k = l;
        int l1 = l;
        int l2 = mid + 1;
        while(l1 <= mid || l2 <= r){
            if(l2 > r || (l1 <= mid && num[l1].val > num[l2].val)){
                num[l1].cnt += r - l2 + 1;
                temp[k++] = num[l1++];
            }else{
                temp[k++] = num[l2++];
            }
        }
        for(int i = l;i <= r;i++) num[i] = temp[i];
    }
}
class Num{
    int val;
    int ind;
    int cnt;
    public Num(){}
    public Num(int val,int ind){
        this.val = val;
        this.ind = ind;
        this.cnt = 0;
    }
}
 
LeetCode1508. 子数组和排序后的区间和 
class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        PriorityQueue priorityQueue = new PriorityQueue<>(
            new Comparator(){
                public int compare(Data a,Data b){
                    return a.sum - b.sum;
                }
            }
        );
        for(int i = 0;i < n;i++){
            priorityQueue.offer(new Data(i,i,nums[i]));
        }
        int ans = 0;
        for(int i = 1;i <= right;i++){
            Data d = priorityQueue.poll();
            if(i >= left) ans = (ans + d.sum) % (1000000007);
            if(d.j + 1 < n) priorityQueue.offer(new Data(d.i,d.j + 1,d.sum + nums[d.j + 1]));
        }
        return ans;
    }
}
class Data{
    int i;
    int j;
    int sum;
    public Data(){}
    public Data(int i,int j,int sum){
        this.i = i;
        this.j = j;
        this.sum = sum;
    }
}

归并排序（Merge-Sort）

Java相关栏目本月热门文章