Question

之前看到的 给定有序表A[1:n],修改合并排序算法,求出该有序表的逆序对数?的回答

Answer 1

怎么实现的,你百度一下,网上一堆源码,我这么打字给你说一时半会儿也说不清楚.有需要的话加我详聊.

为什么要分成两组?好吧这个问题问的好.

你想一下归并排序为什么要分成两组.首先,这是分治思想.可能你会疑惑为什么分治就能降低复杂度.如果只单纯的看合并两个排好序的数组的复杂度只要O（n）.同样的,计算数组left部分和right部分之间构成的逆序对也只要O（n）的复杂度.一层一层这么分下去,每一层都只需要完成一个合并就可以了,所以总的复杂度才会是O（n＊logn）.明白了么?