（原题见算法导论思考题2-4） 题目： 假设A[1…n]是一个有n个不同数的数组。若i>j且A[i]<A[j]，则对偶（i，j）称为A的一个逆序对（inversion）。 a.插入排序的运行时间与输入数组中逆序对的数量有什么关系。 b.给出一个确定在n个元素任意排列中逆序对数量的算法，最坏情况需要 Θ(nlgn) 时间。 解答： a.插入排序的每次交换位置涉及一对逆序对，总共交换的次数就是逆序对的数量。即运行时间为： O(n+d) ，n为数组大小，d为逆序对数目，一个n个元素的数组中逆序对数目最多为 n(n−1)2 个。 b.通过修改归并排序，可以得到其中逆序对的数量。归并排序仅在merge过程中更改了元素的顺序，merge过程对L和R两个数组进行归并操作，设x为当前L中的首元素，y为当前R中的首元素，若x>y，则说明y和L中剩余的每个元素都构成了一对逆序对，记录下每次归并过程中所有的逆序对数目即可得到总的逆序对数目。代码如下：
#include <stdio.h> #include <stdlib.h> void printArray(int *array, int head, int tail) { static int count = 0; printf("%d::", count); count++; for (int i = head; i <= tail; i++) printf("%d ", array[i]); printf("\n"); } int merge_count(int *array, int head, int mid, int tail) { int count = 0; int *temp = (int*)calloc(tail - head + 1, sizeof(int)); if (temp == NULL) { printf("error!\n"); return -1; } int i = head, k = mid + 1; int j = 0; while (i <= mid && k <= tail) { if (array[i] <= array[k]) { temp[j] = array[i]; ++j; ++i; } else if (array[i] > array[k]) { count += mid - i + 1; temp[j] = array[k]; ++j; ++k; } } //注意该次调用剩余部分不会再统计逆序对个数，不然会重复统计 while (i <= mid) { temp[j] = array[i]; ++j; ++i; } while (k <= tail) { temp[j] = array[k]; ++j; ++k; } for (int i = 0; i < j; ++i) { array[i + head] = temp[i]; } printArray(array, head, tail); return count; } int merge_sort_count(int *array, int head, int tail) { if (head >= tail) return 0; int mid = (head + tail) / 2; int inversions = 0; inversions += merge_sort_count(array, head, mid); inversions += merge_sort_count(array, mid + 1, tail); inversions += merge_count(array, head, mid, tail); return inversions; } int main(int argc, char const *argv[]) { int array[5] = {1, 7, 4, 5, 2}; printf("%d\n", merge_sort_count(array, 0, 4)); return 0; }（原题见算法导论第三版5.2-5） 题目： 设A[1..n]是由n个不同数构成的数列，假设A的元素构成<1, 2, 3, .., n>上的一个均匀随机排列，请计算其中逆序对的数目期望。 解答： 设 Xij 为位置i和位置j上存在一个逆序对的随机变量，当位置i和位置j上存在逆序对时 Xij 值为1。位置i和位置j上存在逆序对的概率为1/2。因此，有： E( Xij )=1/2 记X为存在的逆序对的总个数，则有： E(X)=∑n−1i=1∑nj=i+1E(Xij)=n(n−1)4
