【算法与数据结构】一道检测inversion count的初级算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

【算法与数据结构】一道检测inversion count的初级算法

简介: (转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目            这是一道检测inversion count的算法。它将检测输入序列中反序输入的个数,即检测其中有几对A[i] > A[j], i < j 比如输入4,3,2,1,输出应该为3+2+1=6.。 因为: 1.  4比3,2,1大,但4在输入序列

(转载请注明出处:http://blog.csdn.net/buptgshengod

1.题目    

       这是一道检测inversion count的算法。它将检测输入序列中反序输入的个数,即检测其中有几对A[i] > A[j], i < j

比如输入4,3,2,1,输出应该为3+2+1=6.。 因为:

1.  4比3,2,1大,但4在输入序列中是第一位,比3,2,1的index都小

2.  3比2,1大

3.  2比1大

2.代码部分

/*

 *

解:用冒泡法将序列从小到大排序,计算一共移动多少位,就有几个这样的序列对。时间复杂度:O(n²)

 */


public class Test {

 public static void main(String[] args){

int i,j;

int t;

int number=0;

final int n=4;

int[] list = new int[n];

 

System.out.println("随机产生数列");

for(i=0;i<n;i++){

list[i]=(int)( Math.random()*100);

    System.out.print(list[i]+",");

}

 

 

for(i=0;i<n-1;i++){

for(j=0;j<n-1;j++){

if(list[j+1]>=list[j]){

 

}

else{

t=list[j+1];

list[j+1]=list[j];

list[j]=t;

number++;

}

}

}

System.out.println(); 

System.out.println("有 "+number+" 对A[i] > A[j], i < j"); 

 

 }

}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章