本文实例讲述了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++算法设计的学习有所帮助。
