1回答

liuyubobobo

2017-04-20

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

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

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

0

2

liuyubobobo

回复

魏龙云

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

2017-04-21

共2条回复