设A[0 .. n - 1]是一个包含n个不同数的数组。如果在i < j的情况下，有A[i] > A[j]，则(i, j)就称为A中的一个逆序对
1
/**//*
2
名称：逆序数（归并排序）
3
*/
4
#include <iostream>
5#include <time.h>
6#include <stdlib.h>
7using namespace std;
8int inverseNumber;
9void mergeSort(int*, int);
10void __mergeSort(int*, int, int);
11void merge(int*, int, int, int);
12int main(void)
13
{
14 int n;
15 int *array;
16
srand(time(NULL)); /**//*void srand(unsigned seed)；*/
17 while (true)
18 {
19 cin >> n;
20 array = new int[n];
21 /**//*随机生成数组*/
22 for (int i = 0; i < n; ++i)
23 {
24 array[i] = rand() % 100; /**//*int rand(void)；*/
25
}
26
27 /**//*排序前*/
28 for (int i = 0; i < n; ++i)
29 {
30 cout << array[i] << ' ';
31 }
32 cout << endl;
33
34 /**//*初始化为0*/
35 inverseNumber = 0;
36 /**//*归并排序*/
37 mergeSort(array, n);
38 cout << inverseNumber << endl;
39
40 delete array;
41 }
42 return 0;
43}
44void mergeSort(int* array, int length)
45{
46 __mergeSort(array, 0, length - 1);
47}
48void __mergeSort(int* array, int first, int last)
49{
50 /**//*只有有两个元素*/
51 if (first < last)
52 {
53 int middle = first + (last - first) / 2;
54 __mergeSort(array, first, middle);
55 __mergeSort(array, middle + 1, last);
56 merge(array, first, middle, last);
57 }
58}
59void merge(int* array, int first, int middle, int last)
60{
61 int* temp = new int[last - first + 1];
62 int i = first;
63 int j = middle + 1;
64 int k = 0;
65 while (i <= middle && j <= last)
66 {
67 /**//*取较小者*/
68 if (array[i] <= array[j])
69 {
70 temp[k] = array[i];
71 ++i;
72 }
73 else
74 {
75 temp[k] = array[j];
76 ++j;
77 inverseNumber += middle - (i - 1);
78 }
79 ++k;
80 }
81 /**//*前半部分没有复制完*/
82 if (i <= middle)
83 {
84 while (i <= middle)
85 {
86 temp[k] = array[i];
87 ++i;
88 ++k;
89 }
90 }
91 /**//*后半部分没有复制完*/
92 if (j <= last)
93 {
94 while (j <= last)
95 {
96 temp[k] = array[j];
97 ++j;
98 ++k;
99 }
100 }
101 /**//*复制回原数组*/
102 for (int p = first, q = 0; p <= last; ++p, ++ q)
103 {
104 array[p] = temp[q];
105 }
106 /**//*释放内存*/
107 delete temp;
108}
posted on 2012-10-22 22:38
zhuxin 阅读(124)
评论(0) 编辑 收藏 引用 所属分类:
数学