《算法导论》Problem 2-4 Inversions
2024-09-30 05:21:07
在Merge Sort的基础上改改就好了。
public class Inversions { public static int inversions(int [] A,int p, int r) { if(p<r) { int q = (int) Math.floor( (p+r)/2 ); int left = inversions(A,p,q); int right = inversions(A,q+1,r); int c = combine(A,p,q,r); return left + right + c; } return 0; } public static int combine(int [] A, int p, int q, int r) { int total_inversions = 0; int n1 = q-p+1; int n2 = r-q; int [] L = new int[n1]; int [] R = new int[n2]; for(int i=0; i<n1; i++) L[i] = A[p+i]; for(int i=0; i<n2;i++) R[i]=A[q+i+1]; int i=0; int j=0; int counter = p; while(i<L.length && j<R.length) { if(L[i]<=R[j]) { A[counter]=L[i]; i++; } else { A[counter]=R[j]; j++; total_inversions += (q-(p+i)+1); } counter++; } if(i==L.length) { for(int k=j;k<R.length;k++) A[counter++] = R[k]; } else { for(int k=i;k<L.length;k++) A[counter++] = L[k]; } return total_inversions; } public static void main(String[] args) { int A[] = {2,3,8,6,1,7,9,1}; int num_of_inversions = inversions(A,0,A.length-1); System.out.println(num_of_inversions); } }
最新文章
- SqlServer实现先将所有数据排好序再进行分页
- Python:no encoding declared 错误
- C和指针 第一章 字符串处理程序
- 惩罚因子(penalty term)与损失函数(loss function)
- UNIX网络编程-recv、send、read、write之间的联系与区别
- Linux内核分析——期末总结
- cnblogs用户体验
- Oracle使用%rowtype变量存储一行数据
- JLRoutes--处理复杂的URL schemes-备
- CSS3入门
- C++中构造函数或析构函数定义为private
- 反射Reflection创建
- UWP 圆形菜单
- Cause: java. lang.InstantiationException: tk.mybatis.mapper.provider.base.BaseInsertProvider
- Python—模块介绍
- C-Lodop提示“有窗口已打开,先关闭它(持续如此请刷新页面)!”
- react-native中的图片
- linux 源码安装PHP
- python语言中的数据类型之列表
- mysql处理旧数据-使用模板以及临时表,不建议直接使用本表!!
热门文章
- js获取当前日期与星期
- Local declaration of &#39;XXX&#39; hides instance variable
- JS限制 获取动太ID,播放视频
- oracle中的exists 和in
- Android:TextView最小行数设置
- CodeForces 682C Alyona and the Tree(广搜 + 技巧)
- HDU 1054 Strategic Game 最小点覆盖
- 转:WebDriver(Selenium2) 判断页面是否刷新的方法
- linux下安装rabbitmq
- DataBinding注意事项Error parsing XML: duplicate attribute以及如何在listview中使用DataBinding