反轉計數值的排序

Question

的下面下面是一個代碼來計數在一個array.I反轉已經在該部分中一個疑問：

 inv_count = _mergeSort(arr, temp, left, mid);--i 

    inv_count += _mergeSort(arr, temp, mid+1, right);--ii 

    inv_count += merge(arr, temp, left, mid+1, right);--iii 

在反轉次數，總的反轉將等於到i + ii + iii，但我無法理解「我和ii的inv_count如何得到一個值，它們被遞歸地調用並填充到函數堆棧中，但無處價值被傳遞給inv_count for i和ii，儘管在iii中，inv_count使用invcount = inv_count + mid-i得到值;

int mergeSort(int arr[], int array_size) 
{ 
    int *temp = (int *)malloc(sizeof(int)*array_size); 
    return _mergeSort(arr, temp, 0, array_size - 1); 
} 

/* An auxiliary recursive function that sorts the input array and 
    returns the number of inversions in the array. */ 
int _mergeSort(int arr[], int temp[], int left, int right) 
{ 
    int mid, inv_count = 0; 
    if (right > left) 
    { 
    /* Divide the array into two parts and call _mergeSortAndCountInv() 
     for each of the parts */ 
    mid = (right + left)/2; 

    /* Inversion count will be sum of inversions in left-part, right-part 
     and number of inversions in merging */ 
    inv_count = _mergeSort(arr, temp, left, mid); 

    inv_count += _mergeSort(arr, temp, mid+1, right); 

    /*Merge the two parts*/ 
    inv_count += merge(arr, temp, left, mid+1, right); 
    } 
    return inv_count; 
} 

/* This funt merges two sorted arrays and returns inversion count in 
    the arrays.*/ 
int merge(int arr[], int temp[], int left, int mid, int right) 
{ 
    int i, j, k; 
    int inv_count = 0; 

    i = left; /* i is index for left subarray*/ 
    j = mid; /* i is index for right subarray*/ 
    k = left; /* i is index for resultant merged subarray*/ 
    while ((i <= mid - 1) && (j <= right)) 
    { 
    if (arr[i] <= arr[j]) 
    { 
     temp[k++] = arr[i++]; 
    } 
    else 
    { 
     temp[k++] = arr[j++]; 

    /*this is tricky -- see above explanation/diagram for merge()*/ 
     inv_count = inv_count + (mid - i); 
    } 
    } 

    /* Copy the remaining elements of left subarray 
    (if there are any) to temp*/ 
    while (i <= mid - 1) 
    temp[k++] = arr[i++]; 

    /* Copy the remaining elements of right subarray 
    (if there are any) to temp*/ 
    while (j <= right) 
    temp[k++] = arr[j++]; 

    /*Copy back the merged elements to original array*/ 
    for (i=left; i <= right; i++) 
    arr[i] = temp[i]; 

    return inv_count; 
} 

Answer 1

以下是反演計數的工作代碼。 - i --ii --iii與反演計數無關。

合併排序過程中的反演總數等於從排序左側部分和排序右側部分獲得的反演總數，並將左側部分與右側部分合並。如果您不清楚代碼，請做評論。

#include <iostream> 
#include <stdio.h> 
#include <limits.h> 
#include <algorithm> 
using namespace std; 
const int size = 1000000; 
long long int array[size]; 
long long int merge(long long int a[], long long int beg, long long int mid, 
    long long int end) { 
    long long int inverse = 0; 
    long long int lsize = (mid - beg) + 1; 
    long long int rsize = (end - mid); 
    long long int left[lsize + 1]; 
    long long int right[rsize + 1]; 
    long long int i; 
    long long int j = beg; 
    for (i = 0; i < lsize; ++i, ++j) { 
     left[i] = a[j]; 
    } 
    j = mid + 1; 
    for (i = 0; i < rsize; ++i, ++j) { 
     right[i] = a[j]; 
    } 
    left[lsize] = LONG_LONG_MAX; 
    right[rsize] = LONG_LONG_MAX; 
    j = 0; 
    i = 0; 
    for (int k = beg; k <= end; ++k) { 
     if (left[i] <= right[j]) { 
      a[k] = left[i]; 
      ++i; 
     } else { 
      a[k] = right[j]; 
      inverse += (lsize - i); 
      ++j; 
     } 
    } 
    return inverse; 
} 

long long int merge_sort(long long int iArray[], long long int beg, 
     long long int end) { 
    if (beg < end) { 
     long long int mid; 
     long long int left = 0; 
     long long int right = 0; 
     long long int total = 0; 
     mid = (beg + end)/2; 
     left = merge_sort(iArray, beg, mid); 
     right = merge_sort(iArray, mid + 1, end); 
     total = merge(iArray, beg, mid, end); 
     return left + right + total; 
    } else { 
     return 0; 
    } 
}