比武大会
衡山，武当 ，峨眉，华山，少林，昆仑，蜀山七大派召开新一届英雄大会，根据各掌门的武艺排名来划分江湖地位。当前各门派掌门的实际武力值如下
衡山-60 武当-80 峨眉-70 华山-75 少林-90 昆仑-85 蜀山-100
上一届英雄大会的江湖地位从低到高 依次为
华山，峨眉，昆仑，武当，衡山，蜀山，少林
顾本次安排座位也是按上次江湖地位来安排的，少林上届地位最高，安排在最上座，华山上届地位最低，安排在最下座,如下图
1569225273941
下面裁判宣布英雄大会第1轮比武开始，从上届地位最低的开始进行挑战，只能挑战当前座椅后一把座椅上的门派
第一次比武，华山挑战峨眉，华山武力75>峨眉70，挑战成功，交换二者座位位置
1569225767110
交换后，座椅座次变成了
1569225909670
第二次比武：获胜后的华山派继续挑战昆仑，华山武力75<昆仑85 挑战失败，不交换座椅位置
1569226065107
第三次比武：获胜后的昆仑继续挑战武当
1569226310119
交换座位后，座椅座次变成了
1569226379291
第四次比武：获胜后的昆仑继续挑战衡山派
1569226544650
交换座位后，座椅座次变成了
1569226586118
第5次比武：获胜后的昆仑继续挑战蜀山派
1569226683695
第6次比武：获胜后的蜀山派续挑战少林
1569226866260
交换座位后，座椅座次变成了
1569226900406
最终，经过第1轮6次比武，根据武力值比较选出了武力值最大的蜀山，放到座位的最上座
1569230554837
经过一轮比武后，选出了武力值最大的门派，坐到了最高位的座位，但是还得接着选出武力值第二大的门派，坐到次高位的座位上，所以裁判宣布开始进行第二轮比武大会
第二轮需要参加比武的门派有：峨眉，华山，武当，衡山，昆仑，少林
注意：武力值最大的坐在最高位的蜀山，不需要再参与后续的比武了，因为经过第一轮比武，已经确认蜀山是7大派中最厉害的了，所以不需要参加接下来的比武
第2轮第1次比武，峨眉挑战华山
1569227638511
第2轮第2次比武，获胜的华山继续挑战武当
1569227733013
第2轮第3次比武，获胜的武当继续挑战衡山
1569227811886
交换座位后，座椅座次变成了
1569228056330
第2轮第4次比武，获胜的武当继续挑战昆仑
1569228189290
第2轮第5次比武，获胜的昆仑继续挑战少林
1569228260744
最终经过第二轮5次比武，选出了剩余6大派中武力值最大的少林坐上第二高坐
1569230393993
接着裁判宣布在剩余的5大派中选出武力值最大的门派，坐上第三高的宝座
第3轮第1次比武开始，峨眉武力70<华山75，挑战失败，不交换座椅位置
1569228607366
第3轮第2次比武开始，获胜的华山继续挑战衡山，华山武力75>衡山60，挑战成功，交换座椅位置
1569228710430
交换座位后，座椅座次变成了
1569228765517
第3轮第3次比武开始，获胜的华山继续挑战武当：华山武力75<武当80，挑战失败，不交换座椅位置
1569228837932
第3轮第4次比武开始
江湖地位最低的蜀山挑战比它高一名的昆仑，获胜的武当继续挑战昆仑:武当武力80<昆仑85，挑战失败，不交换座椅位置
1569228946283
最终经过第3轮4次比武，选出了剩余5大派中武力值最大的昆仑坐上第三高宝坐
1569230240302
接着裁判宣布在剩余的4大派中选出武力值最大的门派，坐上第四高的宝座
第4轮第1次比武开始，峨眉挑战衡山：峨眉武力70>衡山60，挑战成功，交换座椅位置
1569229282659
交换座位后，座椅座次变成了
1569229322602
第4轮第2次比武开始,获胜的峨眉继续挑战华山，峨眉武力70<华山75，挑战失败，不交换座椅位置
1569229618231
第4轮第3次比武开始,获胜的华山继续挑战武当：华山75<武当80，挑战失败，不交换座椅位置
1569229759357
经过第4轮3次比武，选出了剩余四大派中武力值最高的武当，坐上第四高宝座
1569229930368
接着裁判宣布在剩余的3大派中选出武力值最大的门派，坐上第五高的宝座
第5轮第1次比武开始，衡山挑战峨眉：衡山武力60<峨眉70 挑战失败，不交换座位位置
1569230961356
第5轮第2次比武开始，获胜的峨眉继续挑战华山：峨眉武力70<华山75 挑战失败，不交换座位位置
1569231031856
经过第5轮2次比武，选出了剩余3大派中武力值最高的华山，坐上第5高宝座
1569231121707
接着裁判宣布在剩余的2大派中选出武力值最大的门派，坐上第六高的宝座
第6轮第1次比武开始，衡山挑战峨眉：衡山武力60<峨眉70 挑战失败，不交换座位位置
1569231216690
经过第6轮1次比武，选出了剩余2大派中武力值最高的峨眉，坐上第6高宝座
1569231345294
经过6轮比武，选出了武力值前6的六大派，剩下的衡山派就不用在进行第7轮比武了，因为只剩下他一个门派了，直接坐在最低位的座位即可
1569231474133
观察规律
七大门派需要按武力值高低来排序，经过了6轮比武
第1轮比武：比较了6次
第2轮比武：比较了5次
第3轮比武：比较了4次
第4轮比武：比较了3次
第5轮比武：比较了2次
第6轮比武：比较了1次
所以比较的轮数=要排序的元素总数-1
每轮比较的次数=要排序的元素总数-当前比武轮数
实现代码
public static int[] BubbleSort(int [] arr ){
// arr.length-1 表示需要比较的轮数
for(int i=0;i<arr.length-1;i++){
//arr.length-1 -i 表示每轮要比较的次数
for( int j=0 ;j < arr.length-1 -i ;j++ ){
if( arr[j] >arr[j+1]){
int temp;
temp =arr[j+1];
arr[j+1] =arr[j];
arr[j]=temp;
}
}
}
return arr;
}
冒泡优化
第4轮比武后的结果如下，发现其实已经是有序的了，后面进行的第5轮-第6轮都是多余的
1569229930368
第5轮比武后结果
1569231121707
第6轮比武后结果
1569231474133
顾发现规律，只要一轮比武中，如果没有发生位置交换，则不需要再往后进行了后面的轮数比较了，直接返回当前排序结果即为最终排好了序的结果
优化代码
public static int[] BubbleSort(int [] arr ){
// arr.length-1 表示需要比较的轮数
for(int i=0;i<arr.length-1;i++){
/**
* 如果一轮比较中，没有发送位置交换，则当前排序结果已经是排好序的结果了，直接返回接口
* 提前结束比较的标识
*/
boolean breakFlag=true;
//arr.length-1 -i 表示每轮要比较的次数
for( int j=0 ;j < arr.length-1 -i ;j++ ){
if( arr[j] >arr[j+1]){
int temp;
temp =arr[j+1];
arr[j+1] =arr[j];
arr[j]=temp;
breakFlag=false;
}
}
if(breakFlag){
return arr;
}
}
return arr;
}
算法时间复杂度
观察代码可发现：双层循环，顾执行的次数为 顾平均时间复杂度为O（
)
网友评论