逆序数的计算
常规的做法
时间：O(N^2)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int foo(const vector<int>& array)
6 {
7 int ret = 0;
8 for (vector<int>::size_type i = 0; i != array.size() - 1; ++i)
9 {
10 for (vector<int>::size_type j = i + 1; j != array.size(); ++j)
11 {
12 if (array[i] > array[j])
13 {
14 ++ret;
15 }
16 }
17 }
18 return ret;
19 }
20
21 int main()
22 {
23 vector<int> array;
24
25 for (int i = 10; i > 0; --i)
26 {
27 array.push_back(i);
28 }
29 cout << foo(array) << endl;
30 return 0;
31 }
改进的做法
利用分治法，借助归并排序求解逆序数。
时间复杂度：O(NlogN)
在归并排序的基础做一个修改即可：
不是算右边的相对左边的逆序数，这样太过于繁杂
而是算左边相当于右边的逆序数，这样可以就在这一个地方做统一处理
即当检测到左边大于右边的时候，则所有剩下的左边的数都相对于当前右边的数大，所以逆序数都要加 1 。
count += (end1 - begin1 + 1);
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 int count = 0;
7
8 void merge(int array[], int low, int mid, int high)
9 {
10 int i, k;
11 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
12 int begin1 = low;
13 int end1 = mid;
14 int begin2 = mid + 1;
15 int end2 = high;
16
17 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
18 if(array[begin1]<=array[begin2])
19 {
20 temp[k] = array[begin1++];
21
22 }
23 else
24 {
25 //++count;
26
27 // 不是算右边的相对左边的逆序数，这样太过于繁杂
28 // 而是算左边相当于右边的逆序数，这样可以就在这一个地方做统一处理
29 count += (end1 - begin1 + 1);
30 temp[k] = array[begin2++];
31 }
32 if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
33 {
34 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
35 //count += (end1 - begin1 + 1) * (high - mid);
36 }
37 if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
38 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
39 memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
40 free(temp);
41 }
42
43 int merge_sort(int array[], unsigned int first, unsigned int last)
44 {
45 int mid = 0;
46 if(first<last)
47 {
48 mid = (first+last)/2;
49 merge_sort(array, first, mid);
50 merge_sort(array, mid+1,last);
51 merge(array,first,mid,last);
52 }
53 return count;
54 }
55
56
57 int foo(int array[], int n)
58 {
59 return merge_sort(array, 0, n - 1);
60 }
61
62 int main()
63 {
64 int array[] = {9, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0};
65 // int array[] = {1, 3, 2, 4, 3};
66 // int array[] = {1, 3, 2};
67 cout << foo(array, sizeof (array) / sizeof (*array)) << endl;
68 return 0;
69 }
http://www.cnblogs.com/dskit/archive/2009/12/16/1625942.html
http://hi.baidu.com/xiaohanhoho/blog/item/277a09392a0e4722b8998fdc.html
http://www.cppblog.com/asp/articles/14261.html
http://www.cublog.cn/u2/62093/showart_484338.html
http://blog.csdn.net/guzhilei1986/archive/2008/04/10/2276782.aspx
posted on 2011-06-22 01:11
unixfy 阅读(535)
评论(0) 编辑 收藏 引用