算法

算导学习——逆序对数量

算导学习——逆序对数量 仅使用C++中类的部分性质,整体语言风格为C 需要前置知识:归并排序 符号A[1...n]指数组元素下标从1开始,到n结束,包括1和n 假设A[1..n]是一个有n个不同数的数组。若i<j且A[i]>A[j],则对偶(i,j)称为A的一个逆序对(inversion) 求给定长度为n数组中逆序对的数量。要求最坏的情况需要\(\Theta(n lgn)\)时间