本文实例讲述了C++求逆序对的方法，分享给大家供大家参考之用。具体实现方法如下：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream>
#include <vector>
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++算法设计的学习有所帮助。
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。