编辑代码

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

using namespace std;


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 array[] = {1, 8, 6};
    int arrayLen = sizeof(array)/sizeof(int);

   
     cout << "{1, 8, 6} 的逆序对有" << countReversedOrder(array, 0, arrayLen) <<"个"<<endl;
   



}