首页 > 代码库 > 【Todo】求逆序对数总结
【Todo】求逆序对数总结
用归并排序方式
最原始的方法的复杂度是O(n^2)。
使用归并排序的方式，可以把复杂度降低到O(nlgn).
设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉A[j]，则(i,j)就称为A中的一个逆序对。
例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,<3,2><4,2><5,2>，共4个。
注：我觉得方法是在归并过程中，记录每次归并，后面的分组中被放到了前面的元素的个数。
的确是这样的。下面这个也是MergeSort的基本算法框架：
int gCount = 0; template<class Iterator>int merge(Iterator begin, Iterator mid, Iterator end) { Iterator iL = begin; Iterator iR = mid; int count = distance(begin, end); vector<int> v(count); vector<int>::iterator it = v.begin(); while(iL != mid && iR != end) { if(*iL <= * iR) { *it++ = *iL++; } else { gCount += distance(iL, mid); *it++ = *iR++; } } if(iL == mid) copy(iR, end, it); if(iR == end) copy(iL, mid, it); copy(v.begin(), v.end(), begin); return 0;}template<class Iterator>int mergeSort(Iterator begin, Iterator end){ int count, step; count = distance(begin, end); if(count <= 1) { return 0; } step = count / 2; mergeSort(begin, begin + step); mergeSort(begin + step, end); merge(begin, begin + step, end); return 0;}
重点在 gCount += distance(iL, mid) （注：distance其实就是位置的减法）
逆序对数实质就是插入排序过程中要移动元素的次数。
要移动的元素的位数即第一个序列中还未插入到新序列中的元素的个数
即： distance(iL, mid)
【Todo】求逆序对数总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。