归并排序求逆序对

Question

Answer 1

liuyubobobo 2019-07-29 02:18:33

每次逆序对数量添加的过程，是当前右半部分指的那个元素，比左半部分指的元素小，右半部分的这个元素，和所有左半部分未处理的元素构成了逆序对。关键词是“未处理”。已经处理的元素没有影响。

请再仔细理解我的代码中的注释。

建议使用一个小的测试用，比如8, 7, 6, 5, 4, 3, 2, 1，实际跟踪一下这个程序，注意看一下，每次我们计算逆序对的时候，计算的是多少？这个数值到底表示哪些逆序对？有没有重复？有没有遗漏？

如果你认为if(j > r)的地方需要添加数值，这些数值对应的是哪些逆序对？（一旦你去具体思考是哪些逆序对，就会更清楚自己哪里想的不对了：））

继续加油！：）

• Nihaomamama #1

  老师有可以把这段代码git地址粘出来吗？我找了github上没有找到，谢谢。

• liuyubobobo 回复 Nihaomamama #2

  C++ 版：https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28C++%29/Optional-04-Inversion-Number/main.cpp Java 版：https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28Java%29/Optional-04-Inversion-Number/src/bobo/algo/InversionCount.java 继续加油！：）

• Nihaomamama 回复 liuyubobobo #3

  谢谢老师，真的太负责了。这个看完我继续买老师的课程。