关于算法导论上一道题的思考，求逆序对数目

喜欢ヅ旅行 2022-05-16 12:23 131阅读 0赞

题目是第二章的一个思考题：

Problems 2-4: Inversions Let A\[1 ‥ n\] be an array of n distinct numbers. If i < j and A\[i\] > A\[j\], then the pair (i, j) is called an inversion of A. List the five inversions of the array 〈2, 3, 8, 6, 1〉. What array with elements from the set \{1, 2, . . . , n\} has the most inversions? How many does it have? What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)

求逆序对数目，这里给出第四个问题的解法，使用归并排序来实现，归并排序的代码是我在网上找到的，我只是在里面添加了一些代码。依附于归并排序的算法的复杂度，这个求逆序的时间复杂度的最好最坏和平均复杂度和归并的一致。如下：

\#include <stdio.h> \#include <stdlib.h> int all\_count = 0; void merge(int data\[\], int p, int q, int r) \{ int i = 0; int j = 0; int k = 0; int n1 = 0; int n2 = 0; int low\_count = 0; int move\_count = 0; int \*L = NULL; int \*R = NULL; n1 = q - p + 1; n2 = r - q; L = (int \*)malloc(sizeof(int) \* n1); R = (int \*)malloc(sizeof(int) \* n2); for(i = 0, k = p; i < n1; i++, k++) L\[i\] = data\[k\]; for(i = 0, k = q + 1; i < n2; i++, k++) R\[i\] = data\[k\]; for(k = p, i = 0, j = 0; i < n1 && j < n2; k++) \{ if(L\[i\] < R\[j\]) \{ data\[k\] = L\[i\]; move\_count += low\_count; i++; \} else \{ data\[k\] = R\[j\]; low\_count++; j++; \} \} if(i < n1) /\*all the left is in the left list greater than the right\*/ \{ for(j = i; j < n1; j++, k++) \{ data\[k\] = L\[j\]; move\_count += low\_count; \} \} if(j < n2) \{ for(i = j; i < n2; i++, k++) data\[k\] = R\[i\]; \} all\_count += move\_count; free(L); free(R); \} void merge\_sort(int data\[\], int p, int r) \{ if(p < r) \{ int q = (p + r) / 2; merge\_sort(data, p, q); merge\_sort(data, q + 1, r); merge(data, p, q, r); \} \} void test\_merge\_sort() \{ int data\[\] = \{7, 1, 9, 10, 2, 3, 4\}; printf("The count of the reverse is %d\\n", all\_count); merge\_sort(data, 0, sizeof(data)/sizeof(data\[0\]) - 1); printf("The count of the reverse is %d\\n", all\_count); \} int main() \{ test\_merge\_sort(); return 0; \}

具体的实现其实问题已经描述的很清楚了。不多说了。