冒泡排序BubbleSort(两种写法)

川长思鸟来 2022-05-23 09:47 214阅读 0赞

冒泡排序的核心理念是什么?那就是相邻两数比较,前面的数比后面的数小的话,就交换位置,每次循环找到该次排序的最小值,然后放到该次循环数组的队尾,因此便利到最后,留的就是最大的数.  
那么在这里说下冒泡排序的两种写法,一种是从前往后遍历,另一种是从后往前遍历,这两种遍历方式代码如下:

System.out.println("\n_______________________________________________________");
            //对数组进行循环,每次都是tempArray[i]与tempArray[i+1]进行比较
            //对第一种排序方式进行统计
            int count = 0;
            //对第二种排序方式进行统计
            int count2 = 0;
            for (int i = 0;i<tempArray.length-1;i++){
                //声明tempNum进行中间变量存储
                int tempNum = -1;
                int tempNum2 = -1;
                //第一种排序
                for (int j = 0;j < (tempArray.length-i-1);j++){
                    //如果tempArray[j]<tempArray[j+1],则置换两个存储位置上的数字
                    //全部轮询过后把最小的放到最后面
                    if (tempArray[j]<tempArray[j+1]){
                        tempNum = tempArray[j];
                        tempArray[j] = tempArray[j+1];
                        tempArray[j+1] = tempNum;
                    }
                    //不变
                    count++;
                    System.out.println("\n经第一种的第"+(count)+"次排序方式,此趟排序后,数组为:");
                    for(int num:tempArray){
                        System.out.print(num+" ");
                    }
                }
                //第二种排序,从后往前比较,内部第一轮比较后,可以实现:最小值在最后面,最大值在最前面,所以每次去头去尾比较内部
                for (int j = (tempArray.length-i-2);j >= i;j--){
                    //如果tempArray[j]<tempArray[j+1],则置换两个存储位置上的数字
                    System.out.println("\n此时第"+(j+1)+"位上的数字跟第"+(j+2)+"位上的数字比较");
                    if (tempArray2[j]<tempArray2[j+1]){
                        tempNum2 = tempArray2[j];
                        tempArray2[j] = tempArray2[j+1];
                        tempArray2[j+1] = tempNum2;
                        System.out.println("第"+(j+1)+"位上的数字与第"+(j+2)+"上的数字交换位置");
                    }
                    count2++;
                    System.out.println("\n经第二种的第"+(count2)+"次排序方式此趟排序后,数组为:");
                    for(int num2:tempArray2){
                        System.out.print(num2+" ");
                    }
                }
            }
            System.out.println("第一种循环次数为:"+count);
            System.out.println("经过第一种排序后的数组为:");
            for(int num:tempArray){
                System.out.print(num+" ");
            }
            System.out.println("\n_______________________________________________________");
            System.out.println("第二种循环次数为:"+count2);
            //循环次数为(奇数时),(N-1)+(N-2-1)+(N-4-1)+(N-6-1)+...+(N-2n+1)=nN-N²((N=n/2)+1);
            //循环次数为(偶数时),(N-1)+(N-2-1)+(N-4-1)+(N-6-1)+...+(N-2n+1)=nN-N²(N=n/2);
            System.out.println("经过第二种排序后的数组为:");
            for(int num2:tempArray2){
                System.out.print(num2+" ");
            }
            System.out.println("\n_______________________________________________________");

接下来对这两种方法简单分析,其实主要的分析都在代码备注里面,这里再赘述几点:  
1.为什么第二种方法取值范围为j = (tempArray.length-i-2)?  
答:因为外层循环是从0开始的,所遍历的最大取值下标为tempArray.length-1,又因为每次比较是j的值与j+1的值比较,所以,j+1最大可取到tempArray.length-1则,j最大可取到tempArray.length-2.  
2.为什么后序便利比顺序遍历效率高?  
答:先序便利,只关注最小值,然后像波浪一样把最小值推到最后面,中间不关注最大值,但是后续遍历时,虽然也是把最小值推到最后,但是在推最小值的同时,最大的值被推到了前面,两级分化,然后第二次大循环就是在抛除了两极的数组进行再次的后序便利,所以效率较高.  
3.时间复杂度上两种排序方式的差异.  
答:从时间复杂度上来看,第一种先序遍历,当数组有n个数时,所经历的内层循环总数为:(n-1)+(n-2)+…+(n-n)=\[n\*(n-1)\]/2.  
第二种后续遍历,当有n个数时,如果n为奇数时:,所经历的的内层循环总数为;(N-1)+(N-2-1)+(N-4-1)+(N-6-1)+…+(N-2n+1)=nN-N²((N=n/2)+1),其中N为数组长度2除以2并且向上取整.,如果n为偶数时:,所经历的的内层循环总数为;(N-1)+(N-2-1)+(N-4-1)+(N-6-1)+…+(N-2n+1)=nN-N²(N=n/2),其中N为数组长度2除以2.  
经程序验证输出排序效果:  
![这里写图片描述][70]  
ps:屏幕长度有限,就随机了三个数进行排序,有需要的可以上本人的GitHub进行代码下载,输入个10000,让随机生成的一万长度的数组进行排序也是没问题的,本文GitHub地址为:[https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/BubbleSort.java][https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_BubbleSort.java]  
Over!

[70]: /images/20220523/1efc40ea222d4944901d36c1d838205a.png
[https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_BubbleSort.java]: https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/BubbleSort.java