webservice开发学习系列

比武大会

衡山，武当 ，峨眉，华山，少林，昆仑，蜀山七大派召开新一届英雄大会，根据各掌门的武艺排名来划分江湖地位。当前各门派掌门的实际武力值如下

衡山-60 武当-80 峨眉-70 华山-75 少林-90 昆仑-85 蜀山-100

上一届英雄大会的江湖地位从低到高 依次为

华山，峨眉，昆仑，武当，衡山，蜀山，少林

顾本次安排座位也是按上次江湖地位来安排的，少林上届地位最高，安排在最上座，华山上届地位最低，安排在最下座,如下图

下面裁判宣布英雄大会第1轮比武开始，从上届地位最低的开始进行挑战，只能挑战当前座椅后一把座椅上的门派

第一次比武，华山挑战峨眉，华山武力75>峨眉70，挑战成功，交换二者座位位置

交换后，座椅座次变成了

第二次比武：获胜后的华山派继续挑战昆仑，华山武力75<昆仑85 挑战失败，不交换座椅位置

第三次比武：获胜后的昆仑继续挑战武当

交换座位后，座椅座次变成了

第四次比武：获胜后的昆仑继续挑战衡山派

交换座位后，座椅座次变成了

第5次比武：获胜后的昆仑继续挑战蜀山派

第6次比武：获胜后的蜀山派续挑战少林

交换座位后，座椅座次变成了

最终，经过第1轮6次比武，根据武力值比较选出了武力值最大的蜀山，放到座位的最上座

经过一轮比武后，选出了武力值最大的门派，坐到了最高位的座位，但是还得接着选出武力值第二大的门派，坐到次高位的座位上，所以裁判宣布开始进行第二轮比武大会

​ 第二轮需要参加比武的门派有：峨眉，华山，武当，衡山，昆仑，少林

注意：武力值最大的坐在最高位的蜀山，不需要再参与后续的比武了，因为经过第一轮比武，已经确认蜀山是7大派中最厉害的了，所以不需要参加接下来的比武

第2轮第1次比武，峨眉挑战华山

第2轮第2次比武，获胜的华山继续挑战武当

第2轮第3次比武，获胜的武当继续挑战衡山

​ 交换座位后，座椅座次变成了

第2轮第4次比武，获胜的武当继续挑战昆仑

第2轮第5次比武，获胜的昆仑继续挑战少林

最终经过第二轮5次比武，选出了剩余6大派中武力值最大的少林坐上第二高坐

接着裁判宣布在剩余的5大派中选出武力值最大的门派，坐上第三高的宝座

第3轮第1次比武开始，峨眉武力70<华山75，挑战失败，不交换座椅位置

第3轮第2次比武开始，获胜的华山继续挑战衡山，华山武力75>衡山60，挑战成功，交换座椅位置

交换座位后，座椅座次变成了

第3轮第3次比武开始，获胜的华山继续挑战武当：华山武力75<武当80，挑战失败，不交换座椅位置

第3轮第4次比武开始

江湖地位最低的蜀山挑战比它高一名的昆仑，获胜的武当继续挑战昆仑:武当武力80<昆仑85，挑战失败，不交换座椅位置

最终经过第3轮4次比武，选出了剩余5大派中武力值最大的昆仑坐上第三高宝坐

接着裁判宣布在剩余的4大派中选出武力值最大的门派，坐上第四高的宝座

第4轮第1次比武开始，峨眉挑战衡山：峨眉武力70>衡山60，挑战成功，交换座椅位置

交换座位后，座椅座次变成了

第4轮第2次比武开始,获胜的峨眉继续挑战华山，峨眉武力70<华山75，挑战失败，不交换座椅位置

第4轮第3次比武开始,获胜的华山继续挑战武当：华山75<武当80，挑战失败，不交换座椅位置

经过第4轮3次比武，选出了剩余四大派中武力值最高的武当，坐上第四高宝座

接着裁判宣布在剩余的3大派中选出武力值最大的门派，坐上第五高的宝座

第5轮第1次比武开始，衡山挑战峨眉：衡山武力60<峨眉70 挑战失败，不交换座位位置

第5轮第2次比武开始，获胜的峨眉继续挑战华山：峨眉武力70<华山75 挑战失败，不交换座位位置

经过第5轮2次比武，选出了剩余3大派中武力值最高的华山，坐上第5高宝座

接着裁判宣布在剩余的2大派中选出武力值最大的门派，坐上第六高的宝座

第6轮第1次比武开始，衡山挑战峨眉：衡山武力60<峨眉70 挑战失败，不交换座位位置

经过第6轮1次比武，选出了剩余2大派中武力值最高的峨眉，坐上第6高宝座

经过6轮比武，选出了武力值前6的六大派，剩下的衡山派就不用在进行第7轮比武了，因为只剩下他一个门派了，直接坐在最低位的座位即可

观察规律

七大门派需要按武力值高低来排序，经过了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轮都是多余的

第5轮比武后结果

第6轮比武后结果

顾发现规律，只要一轮比武中，如果没有发生位置交换，则不需要再往后进行了后面的轮数比较了，直接返回当前排序结果即为最终排好了序的结果

优化代码

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;
    }

算法时间复杂度

​ 观察代码可发现：双层循环，顾执行的次数为 $ij$ 顾平均时间复杂度为O（$nn$)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 451261884@qq.com