统计逆序对
代码说明:
资源描述 Description 设a[0…n-1]是一个包含n个数的数组,若在ia[j],则称(i, j)为a数组的一个逆序对(inversion)。 比如 有5个逆序对。请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分元素大于右半部分元素的数量。 其中前两部分(1)和(2)由递归来实现。要保证算法最后效率O(nlogn),第三部分(3)应该如何实现? 此题请勿采用O(n^2)的简单枚举算法来实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中逆序对的个数有关系吗?什么关系? 输入格式 第一行:n,表示接下来要输入n个元素,n不超过10000。 第二行:n个元素序列。 输出格式 逆序对的个数。 输入样例 5 2 3 8 6 1 输出样例 5
下载说明:请别用迅雷下载,失败请重下,重下不扣分!


