一、问题描述
先来说明一下什么是逆序数。大家比较熟悉的是自然排序，即数值较小数排在数值较大数的前面。而如果数值较大的数排在了数值较小数的前面则逆序数的个数+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&
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。知道了这个关系，那么也就知道了怎么来计算逆序数的个数了。
具体的算法步骤请参照前面的《排序-归并排序》，这里就不再给出。
三、程序实现
从文件中读取数字：
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);&
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);
}递归进行逆序数的计算：
merge_count(int *numbers, int begin, int end)&
&&& int merge(int *, int, int, int);&
&&& 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;&
merge_count(int *numbers, int begin, int end)
&int merge(int *, int, int, int);
&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;
}两个排序好的子序列逆序数的计算：
merge(int *numbers, int begin, int middle, int end)&
&&& int n1 = middle - begin + 1;&
&&& int n2 = end -&
&&& int* numbers1 = (int*)malloc((n1 + 1) * sizeof(int));&
&&& int* numbers2 = (int*)malloc((n2 + 1) * sizeof(int));&
&&& int i,&
&&&&&&& j,&
&&& 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 = k & end + 1; k++)&
&&&&&&& if(numbers1[i] & numbers2[j])&
&&&&&&& {&
&&&&&&&&&&& numbers[k] = numbers1[i];&
&&&&&&&&&&& i++;&
&&&&&&&&&&&&
&&&&&&& }&
&&&&&&& else&
&&&&&&& {&
&&&&&&&&&&& numbers[k] = numbers2[j];&
&&&&&&&&&&& j++;&
&&&&&&&&&&& if(i & n1)&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&& totalCount += (middle - begin + 1 - i);&
&&&&&&&&&&& }&
&&&&&&&&&&&&
&&&&&&& }&
&&& free(numbers1);&
&&& free(numbers2);&
&&& return 0;&
merge(int *numbers, int begin, int middle, int end)
&int n1 = middle - begin + 1;
&int n2 = end -
&int* numbers1 = (int*)malloc((n1 + 1) * sizeof(int));
&int* numbers2 = (int*)malloc((n2 + 1) * sizeof(int));
&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;
&for(k = k & end + 1; k++)
&&if(numbers1[i] & numbers2[j])
&&&numbers[k] = numbers1[i];
&&&numbers[k] = numbers2[j];
&&&if(i & n1)
&&&&totalCount += (middle - begin + 1 - i);
&free(numbers1);
&free(numbers2);
&return 0;
}三、后续工作
这里有给出了一个运用分治算法思想解决问题的例子。在后续的博客中还会给出其他一些应用分治思想解决问题的例子。扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
用两种求法求的逆序数
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
1：先看前面的1,然后是顺的,再6,嗯,比1大顺,在3比6小逆,以后其他依次,有几个小就加几这是一种.2：还有一种从后往前,7,比7大的有一个8,8比8大的没有,接着4比4大的有5,6两个,以后依次,这是第二种,看你喜欢怎么用就选哪一种!
为您推荐：
其他类似问题
扫描下载二维码逆序数的含义及求法，大学线代
提问：级别：高二来自：山东省潍坊市
回答数：1浏览数：
逆序数的含义及求法，大学线代
如题，关于逆序数，求详细
&提问时间： 11:08:34
最佳答案此答案已被选择为最佳答案，但并不代表问吧支持或赞同其观点
回答：级别：大一 17:53:28来自：山东省临沂市
逆序：在一个排列中，如果两个数的前后顺序与大小顺序相反，即前面的数大于后面的数，则称这两个数为一个逆序；
逆序数：一个排列中逆序的总数称为这个排列的逆序数。
例如，排列34512中，4的前面没有数字比它大，逆序数为0，同理5的逆序数为0，1的逆序数为3，2的逆序数为3，所以这个排列的逆序数为0+0+3+3=6
我我记着这是大学线代第一章最前面学的。
提问者对答案的评价：
虽然没懂，但是谢谢哈
总回答数1，每页15条，当前第1页，共1页
同类疑难问题
最新热点问题您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
1.求下列各排列的逆序数.doc 11页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
1.求下列各排列的逆序数
你可能关注的文档：
··········
··········
1. 求下列各排列的逆序数.
(3) n(n?1)…321；
(4) 13…(2n?1)(2n)(2n?2)…2.
(1) τ()=11;
(2) τ()=36;
(3) τ(n(n?1)…3·2·1)= 0+1+2 +…+(n?1)=;
(4) τ(13…(2n?1)(2n)(2n?2)…2)=0+1+…+(n?1)+(n?1)+(n?2)+…+1+0=n(n?1).
2. 求出j，k使9级排列24j157k98为偶排列。
解：由排列为9级排列，所以j,k只能为3、6.由2排首位，逆序为0,4的逆序数为0，1的逆序数为3，7的逆序数为0，9的为0，8的为1.由0+0+3+0+1=4，为偶数.若j=3,k=6，则j的逆序为1，5的逆序数为0，k的为1,符合题意；若j=6,k=3,则j的逆序为0，5的逆序数为1，k的为4，不符合题意.
所以j=3、k=6.
3. 写出4阶行列式中含有因子的项。
由题意有：
D4中含的项为：
4. 在6阶行列式中，下列各项应带什么符号？
所以该项带正号。
所以该项带正号。
5. 用定义计算下列各行列式.
【解】(1) D=(?1)τ(;
（3）由题意知：
6. 计算下列各行列式.
【解】(1) ;
7. 证明下列各式.
【证明】(1)
(3) 首先考虑4阶范德蒙行列式:
从上面的4阶范德蒙行列式知，多项式f(x)的x的系数为
但对（*）式右端行列式按第一行展开知x的系数为两者应相等，故
(4) 对D2n按第一行展开，得
据此递推下去，可得
(5) 对行列式的阶数n用数学归纳法.
当n=2时，可直接验算结论成立，假定对这样的n?1阶行列式结论成立，进而证明阶数为n时结论也成立.
按Dn的最后一列，把Dn拆成两个n阶行列式相加：
但由归纳假设
8. 计算下列n阶行列式.
【解】(1) 各行都加到第一行，再从第一行提出x+(n?1),得
将第一行乘（?1）后分别加到其余各行，得
(2) 按第二行展开
(3) 行列式按第一列展开后，得
9. 计算n阶行列式.
【解】各列都加到第一列，再从第一列提出，得
将第一行乘（?1）后加到其余各行，得
10. 计算阶行列式（其中）.
【解】行列式的各列提取因子,然后应用范德蒙行列式.
11. 已知4阶行列式D中第3列元素依次为-1，2，0，1，它们的余子式依次为8，7，2，10，求行列式D的值。
12. 用克拉默法则解方程组.
【解】（1）因为
D=；D1=；D2=
(3)方程组的系数行列式为
故原方程组有惟一解，为
13. 满足什么条件时，线性方程组有唯一解？
要使方程组有唯一解，必须D，于是：
当不等于1，时，方程组有唯一解。
14. λ和μ为何值时，齐次方程组
【解】要使该齐次方程组有非零解只需其系数行列式
故或时，方程组有非零解.
15. 求三次多项式，使得
【解】根据题意，得
这是关于四个未知数的一个线性方程组，由于
于是所求的多项式为
正在加载中，请稍后...
11页42页36页29页30页35页31页28页12页12页