逆序數的計算
常規的做法
時間：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://m.shnenglu.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 閱讀(559)
評論(0) 編輯 收藏 引用