编辑代码

#include <iostream>
#include <math.h>

using namespace std;

// 归并排序的核心思想是不断把无序数组进行切分左右两个长度基本相等的数组，直至切分的数组里面的数据个数为1，
// 此时可以认为这个只有一个数据的数组就是有序的
// 然后将切分后的左右两个有序数组进行合并，两个合并后的有序数据就是有序的，
// 再继续将合并后的左右两个的有序数组合并，直至将整个数组合并完成，这个数组就有序了
int mergeReveredOrder(int array[], int arrStart, int arrMiddle, int arrEnd) {
    int num = 0;
    int arrLen = arrEnd - arrStart;
    if (arrLen < 2) {
        cout << "Please check your implementation." << endl;
        return 0;
    }

    int *temp = new int(arrLen);
    int i = arrStart;
    int j = arrMiddle;
    int tempIndex = 0;

    while (i < arrMiddle && j < arrEnd) {
        if (array[i] > array[j]) {
            temp[tempIndex] = array[j];
            ++j;
            num += (arrMiddle - i);
        }
        else {
            temp[tempIndex] = array[i];
            ++i;
        }
        ++tempIndex;
    }

    // 小数组有剩余数据
    while (i < arrMiddle) {
        temp[tempIndex++] = array[i++];
    }

    while (j < arrEnd) {
        temp[tempIndex++] = array[j++];
    }

    // 把排好序的数据拷贝回去
    for ((tempIndex = 0, i = arrStart); (tempIndex < arrLen && i < arrEnd); (++tempIndex, ++i)) {
        array[i] = temp[tempIndex];
    }

    delete []temp;
    temp = NULL;

    return num;
}
// array 需要排序的数组
// arrStart 数组起始位置的下标
// arrEnd数组终止位置的下标+1
int countReversedOrder(int array[], int arrStart, int arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 0) {
        cout << "Please check your input." << endl;
        return false;
    }

    int num = 0;

    // 写终止条件
    if (arrLen == 0 || arrLen == 1) {
        return 0;
    } 

    // 把数组平均分成两分
    // floor表示取下整数：2.5的下整数2
    int middle = arrStart + floor(arrLen / 2);

    num += countReversedOrder(array, arrStart, middle);
    num += countReversedOrder(array, middle, arrEnd);
    // 合并
    return num + mergeReveredOrder(array, arrStart, middle, arrEnd);
}



int main(){
    int array0[] = {};
    int arrayLen = sizeof(array0)/sizeof(int);

    cout << "The amount of reversed order is " << countReversedOrder(array0, 0, arrayLen) << endl;


    cout << "=========================================" << endl;

    int array1[] = {1};
    arrayLen = sizeof(array1)/sizeof(int);


    cout << "The amount of reversed order for {1} is " << countReversedOrder(array1, 0, arrayLen) << endl;


    cout << "=========================================" << endl;

    int array2[] = {2, 1};
    arrayLen = sizeof(array2)/sizeof(int);

   
     cout << "The amount of reversed order for  {2, 1} is " << countReversedOrder(array2, 0, arrayLen) <<endl;
   
    cout << "=========================================" << endl;

    int array3[] = {1, 5, 3};
    arrayLen = sizeof(array3)/sizeof(int);

   
     cout << "The amount of reversed order for  {1, 5, 3} is " << countReversedOrder(array3, 0, arrayLen) <<endl;
   


    cout << "=========================================" << endl;

    int array4[] = {9, 12, 8, 7};
    arrayLen = sizeof(array4)/sizeof(int);


     cout << "The amount of reversed order for {9, 12, 8, 7} is " << countReversedOrder(array4, 0, arrayLen) <<endl;


    cout << "=========================================" << endl;

    int array5[] = {2, 4, 3, 1, 5,6};
    arrayLen = sizeof(array5)/sizeof(int);


    cout << "The amount of reversed order for  {2, 4, 3, 1, 5,6} is " << countReversedOrder(array5, 0, arrayLen )<<endl;



}