欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序模板(非递归、求逆序对)

程序员文章站 2022-05-10 15:12:25
...

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

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

class Solution {
    private int ans=0;

    private void merge(int[] nums, int low, int mid, int high) {
        int[] tmp = new int[high-low+1];
        int k=0, i=low, j=mid+1;
        while(i <= mid && j <= high) {
            if(nums[i] >= nums[j]) {
                tmp[k++] = nums[i++];
            }
            else {
                tmp[k++] = nums[j++];
                ans += mid - i + 1;
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= high) {
            tmp[k++] = nums[j++];
        }

        k=0;
        i=low;
        while(i <= high) {
            nums[i++] = tmp[k++];
        }
    }

    private void mergeSort(int[] nums) {
        int low, mid, high;
        int size = 1, len = nums.length;
        while (size < len) {
            low = 0;
            while (low + size < len) {
                mid = low + size - 1;
                high = Math.min(mid + size, len - 1);
                merge(nums, low, mid, high);
                low = high + 1;
            }
            size *= 2;
        }
    }

    public int reversePairs(int[] nums) {
        mergeSort(nums);
        return ans;
    }
}

 

非递归归并排序模板

import java.util.Arrays;

class MergeSort {
    public static void main(String[] args) {
        int[] nums = {9, 8, 7, 6, 5, 4, 3, 2, 1};

        new Solution().mergeSort(nums);

        System.out.println(Arrays.toString(nums));
    }

    private void mergeSort(int[] nums) {
        int low, mid, high;
        int size = 1, len = nums.length;
        while (size < len) {
            low = 0;
            while (low + size < len) {
                mid = low + size - 1;
                high = Math.min(mid + size, len - 1);
                merge(nums, low, mid, high);
                low = high + 1;
            }
            size *= 2;
        }
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int[] tmp = new int[high-low+1];
        int k=0, i=low, j=mid+1;
        while(i <= mid && j <= high) {
            if(nums[i] >= nums[j]) {
                tmp[k++] = nums[i++];
            }
            else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= high) {
            tmp[k++] = nums[j++];
        }

        k=0;
        i=low;
        while(i <= high) {
            nums[i++] = tmp[k++];
        }
    }
}

相关标签: java 排序算法