网上有关这题的解答很多，比如：http://blog.csdn.net/qcgrxx/article/details/8005221 讲的很详细了。
有关逆序对的题目：http://www.cppblog.com/ickchen2/articles/62422.html
但是在最后一问中关于怎样求一个排列中逆序对的个数的问题上，我虽然知道网上很多修改归并排序O(nlgn)的算法可以求解，但是我还有另外一个用堆栈O(n)的方法，我自认为是正确的，但是被某判卷是错误的，很是郁闷，下面我把主要过程记下来，希望各位大侠能帮忙指正。
比如算法导论上的例子，数组a为<2,3,8,6,1>有5个逆序对，分别为(2,1), (3,1), (8,6), (8,1), (6,1)。
那么我可以这样做，使用堆栈数据结构，堆栈中存放的是数对(x,y), 其中x为数组a中的元素，y为数组中以x开头可以形成的逆序对的个数。初始时堆栈为空，逆序对个数为ans=0，从右向左扫描数组，如下：
1. 因为第一个元素为1，不能形成逆序对，所以将(1,0)压入栈。
2. 因为6比栈顶元素1大，所以可以形成(6,1)这一个逆序对，又因为1对应的逆序对是0个，所以6对应的逆序对是0++即1个；所以将(6,1)压栈，ans++为1.
3. 因为8比栈顶元素6大，所以可以形成(8,6)这一个逆序对，既然8和6可以形成逆序对，那么8可以和以6开头的元素都形成逆序对，即8可以形成1++=2个逆序对；所以将(8,2)压栈，ans+=2为3.
4. 因为3比栈顶元素8小，所以(8,2)弹栈。
5. 因为3比栈顶元素6小，所以(6,1)弹栈。
6. 因为3比栈顶元素1大，此时的栈顶为(x,y)=(1,0)，所以可以形成y++=1个逆序对，将(3,1)压栈，ans+=1为4.
7. 因为2比栈顶元素3小，所以(3,1)弹栈。
8. 因为2比栈顶元素1大，所以可以形成y++=0++=1个逆序对，将(2,1)压栈，ans+=1为5.
9. 所有元素都已经测试过了，最终ans为5即为逆序对的个数。
因为以上算法只要遍历一遍数组即可，所以时间复杂度为O(n)。
我觉得以上思路合情合理，不知道哪里有错误，求各位指点！