归并排序求逆序数

Question

老师，有一块我没有想明白，就是归并排序求逆序数的时候，我看数组的左侧和右侧都排好顺序了，如果没有排好顺序的话怎么求逆序数呢

Answer 1

liuyubobobo 2017-04-20 01:23:31

使用归并排序求逆序的过程，会将原数组也排好序。这可以理解成是算法的“副效果”。很多算法带有这种“副效果”，因为在求解问题的过程中，也不得不改变原始数据。比如我们要想求出一个整数的二进制表示，就需要不断对这个整数做除以2的操作，直到这个整数为0。

如果不希望有算法的“副效果”，其实也很简单，制作一份原始数据的副本。比如，如果想求一个数组的逆序数，但是又不希望改变原始数组的顺序，那么就复制一份原始数组，求逆序数的操作在这份副本上进行，求出结果以后，再把这份副本销毁就可以了。这样原始数据没有改变，我们也求出了结果。只不过多了一步复制操作，时间复杂度是O(n)的。我们整体算法的时间复杂度依然是O(nlogn)的。

回头想，我们在做将一个整型转换成二进制的字符串这个操作的时候，通常会将这个操作设置成一个函数，将这个整型传进去。这个过程其实无形中建立了一个这个整型的副本。所以我们在做这件事情的时候，似乎，从来没有意识到，讲整数转化成二进制表示这个算法，其实是有“副效果”的：）

• 提问者 魏龙云 #1

  老师我再问下。原来数组是没有排好序的，求逆序数的时候要是把数组顺序又排好了之后再求逆序数，这样的话逆序数是不是就和原来没有排好序的不一样了呀，比如原来是4 3 5 7正常是1 但是排好序后为3 4 5 7逆序数就为0了呀，不知道我这么理解有没有问题老师

• liuyubobobo 回复 提问者 魏龙云 #2

  我们求逆序数的过程不是先排好序，再求逆序数；而是求原数组的逆序数，在这个过程中“顺便”排好了序。最终所求的逆序数，是原数组的逆序数哦。可以用你的测试用例跟一遍我给出的程序，就理解了：）