js2

在很早之前，我曾经发过一篇文章，讲的是冒泡排序的交换次数就是逆序数。可是，这样计算逆序数的话，时间成本就很高，比较冒泡是时间复杂度为O(N²)的算法呢！那怎么办呢？其实，我们可以使用归并排序的思想来计算逆序数。 （以下内容需要先了解归并排序，具体讲解可以看我的这一篇文章：） 我们会发现，在进行升序的归并排序时，每一次后方元素移到前面来的移动距离就是本次操作的逆序数