三位逆序数的计算方法_PHP基础

当前位置：网站建设 > 技术支持

资料来源：网络整理时间：2023/3/5 20:26:34 共计：3593 浏览

三位逆序数的计算方法？

比如4 3 1 2

4第一个，所以数目为0

3的前面是4，大于3的数目为1

1的前面是4 3 ，大于1的数目为2

2的前面是4 3 1，大于2的数目为2

所以逆序数为1+2+2 = 5

求逆序数的两种方法

常规方法是按照逆序数的规则做，结果复杂度是O(n*n)，一般来说，有两种快速的求逆序数的方法

分别是归并排序和树状数组法

2. 归并排序

归并排序是源于分而治之思想，详细的过程可以查阅其他资料，总体思想是划分一半，各自排好序后将两个有序序列合并起来。

如何修改归并排序求逆序数?

首先我们假设两个有序序列a[i]和b[i]，当合并时：

由于a[i]已是有序，所以对于a[i]的各个元素来说，排在它前面且比它大的数目都是0

当b[i]中含有比a[i]小的元素时，我们必然将b[i]元素插到前面，那么就是说，在b[i]原先位置到该插的位置中，所有数都比b[i]大且排在它前面

所以这是b[i]的数目为新插入位置newPos - 原来位置oldPos

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。