C++求逆序对的方法

本⽂实例讲述了C++求逆序对的⽅法，分享给⼤家供⼤家参考之⽤。具体实现⽅法如下：

#include #include using namespace std;

int array[] = {3, 9, 7, 4, 5, 2};

const int size = sizeof array / sizeof *array;int temp[size];

//int numbers[size];

int reversePair(int *numbers, int start, int last, int &index, int &count){

if(start == last) return 0;

int mid = (last - start) / 2 + start;

reversePair(numbers, start, mid, index, count); reversePair(numbers, mid + 1, last, index, count); for(int i = start; i <= last; i++) temp[i] = numbers[i];

int index1 = start, index2 = mid + 1; index = start;

while(index1 <= mid && index2 <= last) { if(temp[index1] > temp[index2]) { numbers[index] = temp[index2]; count += mid - index1 + 1; index++; index2++;

} else if(temp[index1] == temp[index2]) { numbers[index] = temp[index1]; index++; index1++; index2++;

} else if(temp[index1] < temp[index2]) { numbers[index] = temp[index1]; index++; index1++; } }

if(index1 <= mid) { while(index1 <= mid) {

numbers[index] = temp[index1]; index++; index1++; }

} else {

while(index2 <= last) {

numbers[index] = temp[index2]; index++; index2++; } }

return count;}

void main(){

int count = 0; int index = 0;

reversePair(array, 0, size - 1, index, count); cout << \"count = \" << count << endl;}

希望本⽂所述对⼤家C++算法设计的学习有所帮助。