image.png

法一：归并排序

  • 记录原始数组中每个值的 原始位置，那么我们在归并排序的过程中就可以统计右边有多少比它小的，

image.png
image.png

  • merge的时候从大往小merge， 而且若左右组相等，先拷贝右边的

  • merge的时候从只要左组比右组大就产生结果

image.png
image.png
image.png
image.png
image.png

法二：改写有序表

  • 从右往左遍历数组，
  • 有一个结构，它能告诉我右边比当前数小的数有几个