一、問題描述
先來說明一下什麼是逆序數。大家比較熟悉的是自然排序，即數值較小數排在數值較大數的前面。而如果數值較大的數排在了數值較小數的前面則逆序數的個數+1。舉個例子如果有序列4,5,2,1,3，則這個序列總共有(4,2), (4,1), (4,3), (5,2), (5,1), (5,3), (2,1)總共7個逆序數。這個問題的需求就是現有一個文件，每行有一個數字(數值小於100000的正整數)，所有數字不重復，求這個文件中所有數的逆序數的個數。
這個問題是一個較為常見的問題，我把這個問題放在歸並排序後面來介紹是因為，它可以用歸並排序稍加改動即可實現問題的解答。在後面進行詳細敘述。
二、問題分析
根據逆序數的定義可知，一種最為直白的方法就是暴力求解。所謂暴力求解就是從數組中第一個元素開始直到最後一個元素，發現逆序數進行計數器+1操作。偽代碼如下：
[cpp]
for i : 1 to n - 1
for j : i + 1 to n
if(a[i] > a[j])
++count
++j
++i
for i : 1 to n - 1
for j : i + 1 to n
if(a[i] > a[j])
++count
++j
++i這種暴力解決的方法顯然時間復雜度很高()，所以要考慮有沒有時間復雜度更低的算法。在前面說過，這個問題放到歸並排序後給出是因為這個問題可以用歸並算法稍加改動實現。這樣一來，我們就可以把時間復雜程度降為O(nlgn)了。下面我們用歸並算法的思路來簡單分析一下這個問題。
歸並算法的主要思想是把原問題分半成兩個子問題，在分別解決兩個子問題，並將兩個子問題進行合並。那麼，我們把這種想法應用到求逆序數中來。即把原問題分成兩半，分別求這兩個子問題的逆序數，在求合並時滿足要求的逆序數。我們再進一步分析這個問題。應用歸並排序的算法思路，那麼在進行遞歸到最後的時候，即子問題只有一個元素時，顯然不需要排序，也就是說不需要求逆序數(即逆序數的個數為0)，往上進行遞歸時，左右兩個字序列都已經排好序了，也就是說他們已經是自然序列，逆序數為0。這麼一來，逆序數就是合並過程中產生的逆序數的個數。值得注意的是，這時候兩邊的字序列已經有序，那麼不妨設為A和B兩個字序列，如果A中第i個元素比B中的第j個元素大的話，那麼A中第i個元素後面的所有元素都會比B中的第j個元素大，即這時產生的逆序數的個數為length(A) - i + 1。知道了這個關系，那麼也就知道了怎麼來計算逆序數的個數了。
具體的算法步驟請參照前面的《排序-歸並排序》，這裡就不再給出。
三、程序實現
從文件中讀取數字：
[cpp]
int
read_numbers(char * sourceFile)
{
FILE *fptr = NULL;
char oneLine[9];
char charNumebr[9];
int index = 0;
if(NULL == (fptr = fopen(sourceFile, "r")))
{
fprintf(stderr, "Cannot open the input file\n");
exit(0);
}
fgets(oneLine, 9, fptr);
while(!feof(fptr))
{
strncpy(charNumebr, oneLine, strlen(oneLine) - 1);
charNumebr[strlen(oneLine) - 1] = 0;
numbers[index] = atoi(charNumebr);
index++;
fgets(oneLine, 9, fptr);
}
if(-1 == fclose(fptr))
{
printf("The input file failure to close\n");
exit(0);
}
return index;
}
int
read_numbers(char * sourceFile)
{
FILE *fptr = NULL;
char oneLine[9];
char charNumebr[9];
int index = 0;
if(NULL == (fptr = fopen(sourceFile, "r")))
{
fprintf(stderr, "Cannot open the input file\n");
exit(0);
}
fgets(oneLine, 9, fptr);
while(!feof(fptr))
{
strncpy(charNumebr, oneLine, strlen(oneLine) - 1);
charNumebr[strlen(oneLine) - 1] = 0;
numbers[index] = atoi(charNumebr);
index++;
fgets(oneLine, 9, fptr);
}
if(-1 == fclose(fptr))
{
printf("The input file failure to close\n");
exit(0);
}
return index;
}遞歸進行逆序數的計算：
[cpp]
int
merge_count(int *numbers, int begin, int end)
{
int merge(int *, int, int, int);
int middle;
if(begin < end)
{
middle = (end + begin) / 2;
merge_count(numbers, begin, middle);
merge_count(numbers, middle + 1, end);
merge(numbers, begin, middle, end);
}
return 0;
}
int
merge_count(int *numbers, int begin, int end)
{
int merge(int *, int, int, int);
int middle;
if(begin < end)
{
middle = (end + begin) / 2;
merge_count(numbers, begin, middle);
merge_count(numbers, middle + 1, end);
merge(numbers, begin, middle, end);
}
return 0;
}兩個排序好的子序列逆序數的計算：
[cpp]
int
merge(int *numbers, int begin, int middle, int end)
{
int n1 = middle - begin + 1;
int n2 = end - middle;
int* numbers1 = (int*)malloc((n1 + 1) * sizeof(int));
int* numbers2 = (int*)malloc((n2 + 1) * sizeof(int));
int i,
j,
k;
for(i = 0; i < n1; i++)
numbers1[i] = numbers[begin + i];
numbers1[i] = MAX;
for(i = 0; i < n2; i++)
numbers2[i] = numbers[middle + i + 1];
numbers2[i] = MAX;
i = 0;
j = 0;
for(k = begin; k < end + 1; k++)
{
if(numbers1[i] < numbers2[j])
{
numbers[k] = numbers1[i];
i++;
continue;
}
else
{
numbers[k] = numbers2[j];
j++;
if(i < n1)
{
totalCount += (middle - begin + 1 - i);
}
continue;
}
}
free(numbers1);
free(numbers2);
return 0;
}
int
merge(int *numbers, int begin, int middle, int end)
{
int n1 = middle - begin + 1;
int n2 = end - middle;
int* numbers1 = (int*)malloc((n1 + 1) * sizeof(int));
int* numbers2 = (int*)malloc((n2 + 1) * sizeof(int));
int i,
j,
k;
for(i = 0; i < n1; i++)
numbers1[i] = numbers[begin + i];
numbers1[i] = MAX;
for(i = 0; i < n2; i++)
numbers2[i] = numbers[middle + i + 1];
numbers2[i] = MAX;
i = 0;
j = 0;
for(k = begin; k < end + 1; k++)
{
if(numbers1[i] < numbers2[j])
{
numbers[k] = numbers1[i];
i++;
continue;
}
else
{
numbers[k] = numbers2[j];
j++;
if(i < n1)
{
totalCount += (middle - begin + 1 - i);
}
continue;
}
}
free(numbers1);
free(numbers2);
return 0;
}三、後續工作
這裡有給出了一個運用分治算法思想解決問題的例子。在後續的博客中還會給出其他一些應用分治思想解決問題的例子。
