零、数据结构和算法系列目录
数据结构和算法系列目录(不断更新)：
http://blog.csdn.net/adrastos/article/details/9093857
一、问题描述
先来说明一下什么是逆序数。大家比较熟悉的是自然排序，即数值较小数排在数值较大数的前面。而如果数值较大的数排在了数值较小数的前面则逆序数的个数+1。举个例子如果有序列4,5,2,1,3，则这个序列总共有(4,2), (4,1), (4,3), (5,2), (5,1), (5,3), (2,1)总共7个逆序数。这个问题的需求就是现有一个文件，每行有一个数字(数值小于100000的正整数)，所有数字不重复，求这个文件中所有数的逆序数的个数。
这个问题是一个较为常见的问题，我把这个问题放在归并排序后面来介绍是因为，它可以用归并排序稍加改动即可实现问题的解答。在后面进行详细叙述。
二、问题分析
根据逆序数的定义可知，一种最为直白的方法就是暴力求解。所谓暴力求解就是从数组中第一个元素开始直到最后一个元素，发现逆序数进行计数器+1操作。伪代码如下：
for i : 1 to n - 1
for j : i + 1 to n
if(a[i] > a[j])
++count
++j
++i
这种暴力解决的方法显然时间复杂度很高(
归并算法的主要思想是把原问题分半成两个子问题，在分别解决两个子问题，并将两个子问题进行合并。那么，我们把这种想法应用到求逆序数中来。即把原问题分成两半，分别求这两个子问题的逆序数，在求合并时满足要求的逆序数。我们再进一步分析这个问题。应用归并排序的算法思路，那么在进行递归到最后的时候，即子问题只有一个元素时，显然不需要排序，也就是说不需要求逆序数(即逆序数的个数为0)，往上进行递归时，左右两个字序列都已经排好序了，也就是说他们已经是自然序列，逆序数为0。这么一来，逆序数就是合并过程中产生的逆序数的个数。值得注意的是，这时候两边的字序列已经有序，那么不妨设为A和B两个字序列，如果A中第i个元素比B中的第j个元素大的话，那么A中第i个元素后面的所有元素都会比B中的第j个元素大，即这时产生的逆序数的个数为length(A)
- i + 1。知道了这个关系，那么也就知道了怎么来计算逆序数的个数了。
具体的算法步骤请参照前面的《排序-归并排序》，这里就不再给出。
三、程序实现
从文件中读取数字：
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
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(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;
}
三、后续工作
这里有给出了一个运用分治算法思想解决问题的例子。在后续的博客中还会给出其他一些应用分治思想解决问题的例子。
四、参考资料
1. Introduction to Algorithms(Second Edition), Thomas H.Cormen & Charles E.Leiserson
2. 排序-归并排序, http://blog.csdn.net/adrastos/article/details/9265529
说明：
数据结构和算法博客系列的目录为：http://blog.csdn.net/adrastos/article/details/9093857
如有错误还请各位指正，欢迎大家一起讨论给出指导。
上述程序完整代码下载链接：
最后更新时间2013-07-09