八、从归并排序到数列的逆序数对（微软面试题）

---

 

---

1.逆序数对的定义

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。

2.求逆序数对的两种实现方法

1）
一般的方法是从前向后统计每个数字跟后面的数字是否能组成逆序数对，代码为：

1. int main(void)

2. {

3. printf(“数列的逆序数对”);

4. const int MAXN = 8;

5. int a[MAXN] = { 6, 4, 7, 54, 32, 66, 2, 89 };

6. int nCount = 0;

7. int i, j;

8. for (i = 0; i < MAXN; i++)

9. {

10. for (j = i + 1; j < MAXN; j++)

11. {

12. if (a[i] > a[j])

13. nCount++;

14. }

15. }

16. printf(“逆序数对为： %dn”, nCount);

17. return 0;

18. }

由于这种方法用到了双循环，时间复杂度为O（N^2^）。

2）我们也可以利用归并排序过程中，序列合并时的比较来得到逆序数对的个数

1. void mergearray(int a[], int first, int mid, int last, int

   temp[])

2. {

3. int i = first, j = mid + 1;

4. int m = mid, n = last;

5. int k = 0;

6. while (i <= m && j <= n)

7. {

8. //如果左边的小于右边的，则左边的标识i向右移动一位

9. if (a[i] < a[j])

10. temp[k++] = a[i++];

11. //如果左边的大于右边的，说明左边的第m-i个数也大于右边的，形成了m-i+1个逆序数对，右边的标识j向右移动一位

12. else

13. {

14. temp[k++] = a[j++];

15. g_nCount += m - i + 1;

16. }

17. }

18. while (i <= m)

19. temp[k++] = a[i++];

20. while (j <= n)

21. temp[k++] = a[j++];

22. for (i = 0; i < k; i++)

23. {

24. a[first + i] = temp[i];

25. }

26. }

这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N *
LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N *
LogN)