求排列的逆序数
发布网友
发布时间：2023-09-24 04:12
共1个回答
热心网友
时间：2024-11-25 20:19
求排列的逆序数：
O(n2)
分治O(nlogn)：
1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数
2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成（要求O(n)实现）
由归并排序改进得到，加上计算逆序的步骤
MergeSortAndCount：归并排序并计算逆序数
注意：在一个排列中，如果一对数的前后位置与大小顺序相反（即前面的数大于后面的数），那么这一对数就被称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
