今天遇到求逆序對的問題，經過一番思索之後，特意來總結一下。因為也學習到了很多方法，以前自己一些百思不得其解的問題也有了解答。
先上一個簡單的問題：
分析：題目中說使用插入排序，也就是在排序過程中計算交換的次數，按照插入排序的原理，先定第一個，再定前兩個的順序，以此類推，只要交換了，我的次數就加一，但實際上，我們一直按照原始序列的順序一直在往後走，所以（好，重點來了）我們要插入的就是前面比我大的數字前面的位置，也就是說，我需要交換的次數就是前面比我大的數字的個數，那麼我考慮那就沒必要進行交換了，直接進行和前面的數字進行比較就可以了啊，只要前面有比你現在所比較的數大，則加一。其實這很像我們線代學過的逆序數，就是求逆序數的個數。
接下來就是寫代碼：
1 #include<stdio.h>
2 int main() {
3 int n,m;
4
5 scanf("%d\n",&n);
6
7 int count = 0;
8 for(int i=0; i < n; i++) {
9 scanf("%d\n",&m);
10 int ch[m];
11 for(int j=0; j < m; j++) {
12 scanf("%d",&ch[j]);
13 }
14
15 for(int k=1; k < m; k++) {
16 for(int l=0; l < k; l++) {
17 if(ch[k] < ch[l]) count++;
18 }
19 }
20 }
21 printf("%d\n",count);
22
23 return 0;
24 }
這裡的代碼就是普普通通的代碼，通俗易懂。當然，兩個循環那裡可以進行算法的優化，有心的讀者自己去嘗試吧。或者說看接下來的內容也可以收獲另一種求逆序數的方法。
好，接下來，我們講述重點的問題，相信很多人都可以解決前面的問題，但接下來的問題就不是那麼容易了，需要思考與一些代碼技巧。
注意：Hint : 直接使用兩層迴圈來找答案的話會超過系統時間限制。
所以就必須尋求算法復雜度低的算法，按照提示，說在歸並的過程當中計算逆序數對，首先要熟悉歸並排序的原理，再結合問題來看。於是我在紙上進行了演算，先不斷地進行二分，然後就兩個兩個相比較，就是分為兩組，每組一個數，如果後面這個比前面的大，那就是一個逆序數對，然後就加一，並且將小的數字放在前面，於是合並，就得到了包含兩個數的有序的一組數。接下來就是比較每組兩個數的比較，如果第二組的第一個數大於第一組的第一個數，就加二，因為它比前面這組所有數都小。然後歸並。以此類推。原則就是：如果後面這組數的某個數比前面這組的第i個數小，則逆序對數加上（mid-i+1）。
雖然明白了原理，對於歸並不熟悉的同學，我覺得還是比較難的，特別是其中的一些技巧。
不多說。先分析代碼如何寫，先寫框架：
1 #include<stdio.h>
2
3 int count = 0;//逆序數對
4 void mergeSort(int lo,int hi) {
5
6 }
7
8 int main() {
9 int N;
10 scanf("%d",&N);
11
12 for(int i=0; i < N; i++) {
13 scanf("%d",&ch[i]);
14 }
15
16 mergeSort(0,N-1);//歸並排序
17
18 printf("%d\n",count);
19 return 0;
20 }
這部分框架應該都能看懂。接下來講述歸並。首先原理就是先二分，分別排序，後歸並。
1 void mergeSort(int lo,int hi) {
2 if(lo < hi) {
3
4 int mid =( lo + hi ) / 2;//另一種寫法：int mid = ( lo + hi ）>> 1;(學過計算機組成的應該知道，最終代碼都會轉換成二進制，二進制數字向右移一位代表除以2）
5 //二分排序
6 mergeSort(lo,mid);
7 mergeSort(mid + 1,hi);
8 //歸並
9 Merge(lo,mid,hi);
10 }
11 }
其實這差不多也是個框架，只不過注意一下 lo < hi 這個條件。
然後重點在於歸並這部分，設置標記點，i = lo 和 j = mid+1 循環的條件應該是
1 int i = lo;
2 int j = mid + 1;
3 while(i <= mid&&j <= hi) {
4
5 }
如果後面前面這組數的第i個數大於後面某個數，count就加mid-i+1。當然歸並時需要一個臨時數組來存儲這些改變位置的數，
1 int i = lo;
2 int j = mid + 1;
3 int x = lo;
4
5 while(i <= mid&&j <= hi) {
6 if ( ch[i] > ch[j]) {
7 count += mid - i + 1;
8 temp[x++] = ch[j++];
9 }
10 else {
11 temp[x++] = ch[i++];
12 }
13 }
當然，這還有個要注意的地方，如果前面這組數已經排完了，然後後面這組數還沒完就已經退出了循環，那這個臨時數組就沒有歸並所有的數進來，就不完整。此時就應該加上
1 while(i <= mid) temp[x++] = ch[i++]; 2 while(j <= hi) temp[x++] = ch[j++];
然後當然我們還要把這個臨時數組的值又返回到原來的數組中，以便於這個數組在下一輪進行歸並。
1 for(int k = lo; k <= hi ; k++) 2 ch[k] = temp[k];
好，這樣，我們就完成整個代碼的編寫
這是完整的源代碼：
1 #include<stdio.h>
2
3 void Merge(int ,int ,int );
4 void mergeSort(int ,int );
5
6 int ch[20000],temp[20000];//最大有20000個數，注意這裡要是全局變量，易於使用。
7 int count = 0;//逆序數，一定要是全局變量，這樣就可以無論怎麼遞歸都會一直加。原先的想法就是遞歸中返回逆序對的數，不斷累加，實現起來比這個困難。這個直接就是全局變量，方便簡潔。
8
9 void mergeSort(int lo,int hi) {//遞歸函數裡不斷二分排序，歸並。
10 if(lo < hi) {
11
12 int mid =( lo + hi ) / 2;
13
14 mergeSort(lo,mid);
15 mergeSort(mid + 1,hi);
16
17 Merge(lo,mid,hi);
18 }
19 }
20
21 void Merge(int lo,int mid,int hi) {//進行歸並
22 int i = lo;
23 int j = mid + 1;
24 int x = lo;
25
26 while(i <= mid&&j <= hi) {
27 if ( ch[i] > ch[j]) {
28 count+= mid - i + 1;
29 temp[x++] = ch[j++];
30 } else {
31 temp[x++] = ch[i++];
32 }
33 }
34
35 while(i <= mid) temp[x++] = ch[i++];
36 while(j <= hi) temp[x++] = ch[j++];
37
38 for(int k = lo; k <= hi ; k++)
39 ch[k] = temp[k];
40
41 }
42 int main() {
43 int N;
44 scanf("%d",&N);
45
46 for(int i=0; i < N; i++) {
47 scanf("%d",&ch[i]);
48 }
49
50 mergeSort(0,N-1);
51
52 printf("%d\n",count);
53 return 0;
54 }
這裡帶給我最大的收獲就是count是全局變量，因此才可以在不斷的遞歸中一直累加，我原先的想法就是在遞歸中看能不能返回逆序對的個數，或者在參數中間加入逆序對的個數一直傳遞。這次終於得到了解答，還有這個歸並時他創建的臨時數組也很巧妙，最終又賦值給原數組。最棒的就是遞歸這部分，以前老是理不清，想不清，看來以後得多用用遞歸。
2016-02-25 12:37:30
