배열 의 역순 대 수량, 시간 복잡 도 O (n * lg n) 를 구하 십시오.

제목.
알고리즘 서론 제3 판 2 장의 네 번 째 사고 문제 다.
원제:
A [1... n] 가 n 개의 다른 수 를 가 진 배열 이 라 고 가정 합 니 다.만약 에 i < j 및 A [i] > A [j] 라면 대구 (i, j) 를 A 의 역순 대 라 고 부른다.
n 개 요소 의 모든 배열 에서 역순 으로 수량 을 확인 하 는 알고리즘 을 제시 합 니 다. 시간 복잡 도 O (n * lg n).
(알림: 병합 정렬 수정)
 
분석 하 다.
먼저 직관 적 인 해법 이 있다. 즉, 배열 A 를 차례대로 옮 겨 다 니 며 요소 A [i] 뒤에 몇 개의 작은 숫자 가 존재 하 는 지 찾 아 총 횟수 를 통계 하면 된다.그러나 이런 해법 은 간단 하지만 시간 복잡 도 는 O (n ^ 2) 이 고 코드 도 간단 합 니 다. 여 기 는 예 를 들 지 않 습 니 다.다음은 병합 정렬 방법 으로 역순 의 수량 을 계산 하 는 방법 을 말한다.
병합 단계 에 역순 이 얼마나 존재 하 는 지 항상 역순 대 수량 = 왼쪽 부분 역순 대 + 오른쪽 부분 역순 대 + 합병 부분 역순 대 가 있 습 니 다.
관건 은 합병 부분의 역순 대 수량 을 어떻게 얻 느 냐 하 는 것 이다. 합병 할 때 i 가 왼쪽 배열 의 역순 색인 이 고 j 는 오른쪽 배열 의 역순 색인 이다. A [i] 가 A [j] 보다 크다 는 것 을 발견 하면 (mid – i) 의 역순 이 생 길 것 이다.A [i + 1], A [i + 2]... A [mid - 1] 가 A [j] 보다 크기 때문이다.그 중 mid 는 오른쪽 배열 에서 시 작 된 색인 입 니 다.
 
해답

public class Main {
 
    public static void main(String[] args) {
        int[] arr = new int[] { 2, 3, 8, 6, 1 };
        int inversionCount = mergeSort(arr, 0, arr.length);
        printArray(arr);
        System.out.println("inversionCount: " + inversionCount);
    }
 
    public static int mergeSort(int[] arr, int start, int end) {
        int inversionCount = 0;
        int length = end - start;
        if (length > 1) { //     1     
            int mid = (start + end) / 2;
            inversionCount += mergeSort(arr, start, mid); // sort left
            inversionCount += mergeSort(arr, mid, end); // sort right
            inversionCount += merge(arr, start, mid, end);
        }
        return inversionCount;
    }
 
    public static int merge(int[] arr, int start, int mid, int end) {
        // check input
        if (arr == null || start < 0 || end > arr.length) {
            return 0;
        }
        int[] temp = new int[end - start];
        int inversionCount = 0;
        int i = start; //       
        int j = mid; //       
        int k = 0; // temp    
        while (i < mid && j < end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                //    arr[i] > arr[j]，    (mid - i)       
                inversionCount += mid - i;
            }
        }
        if (i != mid) {
            System.arraycopy(arr, i, temp, k, mid - i);
        } 
        if (j != end){
            System.arraycopy(arr, j, temp, k, end - j);
        }
        System.arraycopy(temp, 0, arr, start, temp.length);
        return inversionCount;
    }
 
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}

실행 결과:

1 2 3 6 8 
inversionCount: 5

​
원수 조 는 [2, 3, 8, 6, 1] 이 고 그 역순 대 는 (2, 1), (3, 1)、 (8, 1)、 (6, 1)、 (8, 6) 모두 5 쌍 입 니 다.
우리 운행 결과 에 부합 하 다.