零、数据结构和算法系列目录
数据结构和算法系列目录(不断更新)：
一、问题描述
先来说明一下什么是逆序数。大家比较熟悉的是自然排序，即数值较小数排在数值较大数的前面。而如果数值较大的数排在了数值较小数的前面则逆序数的个数+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;} 递归进行逆序数的计算：
intmerge_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;} 两个排序好的子序列逆序数的计算：
intmerge(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. 排序-归并排序,
说明：
数据结构和算法博客系列的目录为：
如有错误还请各位指正，欢迎大家一起讨论给出指导。
上述程序完整代码下载链接：
最后更新时间2013-07-09