算法训练——归并排序算法（LeetCodeHOT100）

摘要

博文主要介绍归并算法的原理和相关练习题目。

一、算法练习题

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

归并排序与逆序对是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题； 治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；

合并阶段本质上是合并两个排序数组 的过程，而每当遇到左子数组当前元素>右子数组当前元素 时，意味着 左子数组当前元素 至 末尾元素与右子数组当前元素构成了若干「逆序对」 。 因此，考虑在归并排序的合并阶段统计「逆序对」数量，完成归并排序时，也随之完成所有逆序对的统计。

class Solution {
    int count = 0;
    public int reversePairs(int[] array) {
         // 长度小于2则无逆序对
        if (array.length < 2) {
            return 0;
        }
        // 进入归并
        mergeSort(array, 0, array.length - 1);
        return count;
    }
    private void mergeSort(int[] array, int left, int right) {
        // 找分割点
        int mid = (left + right) >> 1;
        if (left < right) {
            // 左子数组
            mergeSort(array, left, mid);
            // 右子数组
            mergeSort(array, mid + 1, right);
            // 并
            merge(array, left, mid, right);
        }
    }
    private void merge(int[] array, int left, int mid, int right) {
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr = new int[right - left + 1];
        // 临时数组的下标起点
        int index = 0;

        // 保存在原数组的起点下标值
        int s = left;

        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid + 1;

        while (l  1;
        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);
        merge(a, l, mid, r);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int P1 = start;
        int P2 = mid + 1;
        int cur = 0;

        int[] tmp = new int[end - start + 1]; //临时数组用于存储一次归并过程中排序好的元素，

        int[] tmpIndex = new int[end - start + 1];//临时数组的索引数组，存储这临时数组中每个元素对应的下标

        while (P1 = 0) {
            nums1[index--] = nums2[r--];
        }
    }


    @Test
    public void test(){
        merge(new int[]{0},0,new int[]{1},1);
    }
}

23. 合并K个升序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
         if (lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    /**
     * @description 两个链表的合并
     * @param: a
     * @param: b
     * @date: 2022/2/17 0:13
     * @return: 归并算法.mergeKLists23.ListNode
     * @author: xjl
     */
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

148. 排序链表

同样的也是的归并排序算法

切分

合并链表

package 归并排序算法;

public class sortList148v2 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //快慢指针切割
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        // 合并链表
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode result=mergetwolist(left,right);
        return result;
    }

    /**
     * 链表和合并
     *
     * @param l1
     * @param l2
     * @return
     */
    private ListNode mergetwolist(ListNode l1, ListNode l2) {
        ListNode dumy = new ListNode(-1);
        ListNode curr = dumy;
        while (l1 != null && l2 != null) {
            if (l1.val> l2.val){
                curr.next=l2;
                l2=l2.next;
            }else {
                curr.next=l1;
                l1=l1.next;
            }
            curr=curr.next;
        }
        while (l1!=null){
            curr.next=l1;
            curr=curr.next;
            l1=l1.next;
        }
        while (l2!=null){
            curr.next=l2;
            curr=curr.next;
            l2=l2.next;
        }
        return dumy.next;
    }
}

912. 排序数组

就是的一个的归并排序的原理 

class Solution {
    public int[] sortArray(int[] nums) {
         if (nums.length < 2) {
            return nums;
        }
        split_array(nums, 0, nums.length - 1);
        return nums;
    }

    public void split_array(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        split_array(nums, left, mid);
        split_array(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    public void merge(int[] nums, int left, int mid, int right) {
        int[] array = new int[right - left + 1];
        int index = 0;

        int s = left;

        int l = left;
        int r = mid + 1;

        while (l