快捷導(dǎo)航

逆序?qū)?wèn)題(Java實(shí)現(xiàn))歸并詳解

更新時(shí)間：2026年05月09日 11:52:14 作者：-添磚Java

文章介紹了計(jì)算給定正整數(shù)序列中逆序?qū)?shù)量的方法,特別是使用歸并排序進(jìn)行拆分和合并時(shí)統(tǒng)計(jì)逆序?qū)?通過(guò)遞歸拆分序列,并在合并過(guò)程中統(tǒng)計(jì)逆序?qū)?shù)量,從而得到整個(gè)序列的逆序?qū)倲?shù),此方法能有效處理包含重復(fù)數(shù)字的序列

題目

對(duì)于給定的一段正整數(shù)序列，逆序?qū)褪切蛄兄衋i>aj，且i<j的有序?qū)Γ蛔⒁庑蛄兄锌赡苡兄貜?fù)數(shù)字，并分析算法的時(shí)間性能。

例如：有6個(gè)數(shù)字，分別是5,4,2,6,3,1，則逆序?qū)?shù)目是11。

思想

一個(gè)亂序的數(shù)組，使用歸并排序的方法對(duì)其進(jìn)行拆分拆分，最后剩余兩個(gè)已經(jīng)排好序的數(shù)組（如圖1）

?圖1：

然后對(duì)兩個(gè)數(shù)組再進(jìn)行歸并排序，排序的同時(shí)統(tǒng)計(jì)逆序?qū)?，比?與1對(duì)比可以產(chǎn)生逆序?qū)Γ瑒t4與1、5與1也能產(chǎn)生逆序?qū)?，按照此思路即可統(tǒng)計(jì)出所有的逆序?qū)Α?/p>

代碼：

package com.itwyc;

import java.util.*;

public class Main {
    public static long count = 0;   // 逆序?qū)€(gè)數(shù)
    public static void getCount(int[] nums) {
        if (nums.length > 1) {
            int[] left_temp = getLeftTemp(nums, 0); // 得到左邊數(shù)組           
            int[] right_temp = getLeftTemp(nums, 1);// 得到右邊數(shù)組              
            getCount(left_temp); // 將得到的數(shù)組繼續(xù)拆分                                   
            getCount(right_temp);
            merge(nums, left_temp, right_temp);// 歸并排序，歸并的同時(shí)統(tǒng)計(jì)逆序?qū)?                    
        }
    }

    public static int[] getLeftTemp(int[] temp, int a) {
        int[] current;
        if (a == 0) {
            current = new int[temp.length / 2];
            for (int i = 0; i < temp.length / 2; i++) {
                current[i] = temp[i];
            }
        } else {
            current = new int[temp.length - temp.length / 2];
            for (int i = 0; i < temp.length - temp.length / 2; i++) {
                current[i] = temp[temp.length / 2 + i];
            }
        }
        return current;
    }

    public static void merge(int[] nums, int[] left_temp, int[] right_temp) {
        int index = 0;
        int left = 0;
        int right = 0;
        int left_len = left_temp.length;
        int right_len = right_temp.length;
        while (left < left_len && right < right_len) {// 如果左邊的數(shù)大于右邊的數(shù)，則為逆序?qū)?                  
            if (left_temp[left] > right_temp[right]) {
                count += (left_len - left);// 如果此數(shù)為逆序?qū)?，則此數(shù)右邊的數(shù)也為逆序?qū)?，因?yàn)閮蓚€(gè)數(shù)組內(nèi)已經(jīng)排好序                              
                nums[index++] = right_temp[right++];
            } else {
                nums[index++] = left_temp[left++];
            }
        }
        while (left < left_len) {
            nums[index++] = left_temp[left++];
        }
        while (right < right_len) {
            nums[index++] = right_temp[right++];
        }
    }

    public static void main(String[] args) {

        /**
         *  逆序?qū)?wèn)題
         */
        int[] nums = {8, 7, 6, 5, 4, 3, 2, 1};
        getCount(nums);
        System.out.println("逆序?qū)τ? + count + "個(gè).");
    }
}