calc_reverse_num.cpp

#include <iostream>
#include <iomanip>

using namespace std;

#define SORT_NUM 4

int my_count=0;//全局变量

void create_array_with_random_numbers(int myArray[], int len){
    for (int i = 0; i < len; ++i) {
        sranddev();
        myArray[i] = rand() % 100;
    }
}

void print_array(int myArray[], int len){
    for (int i = 0; i < len; ++i) {
        cout << right << setw(3) << myArray[i];
    }
    cout << endl;
}

void merge(int myArray[], int low, int mid, int high){
    int i,j,k;
    int backupArray[high+1];
    for (i = low; i <= high; ++i) {
        backupArray[i] = myArray[i];
    }

    for(i = low,j = mid+1,k = i;i <= mid && j <= high;k++){
        if(backupArray[i] <= backupArray[j]){
            myArray[k] = backupArray[i++];
        }
        else{
            //在merge_sort的基础上加上下面这句话即可。由于merge的左数组和右数组都是有序的，一旦出现backupArray[i] >= backupArray[j],左数组在i之后全部构成逆序对。
            my_count += (mid-i+1);
            myArray[k] = backupArray[j++];
        }
    }

    while(i <= mid){
        myArray[k++] = backupArray[i++];
    }
    while(j <= high){
        myArray[k++] = backupArray[j++];
    }


}

void merge_sort(int myArray[], int low, int high){
    if(low < high){
        int mid = (low + high) / 2;
        merge_sort(myArray, low, mid);
        merge_sort(myArray, mid+1, high);
        merge(myArray, low, mid, high);
    }
}


int calc_reverse_num(int myArray[], int len){
    merge_sort(myArray, 0, len-1);
    return my_count;
}


int main()
{

    int len = SORT_NUM;
    int myArray[len];
    create_array_with_random_numbers(myArray, len);
    print_array(myArray, len);
    cout << calc_reverse_num(myArray, len);


    return 0;
}