“365算法每日学计划”：05打卡-图解冒泡排序（多解法）

一、思路

在进行冒泡法排序（升序）时，需要将数组元素（len）两两比较，如果 前面的元素大于后面的元素，则交换两个数，否则，比较下一个元素和它的下一个元素的大小，依次执行，执行一次循环，可以找到当前数组中最大的一个元素，然后问题规模变小，然后找出len-1个元素里的最大值，使之成为第二大元素，依次执行，需要在外层嵌套一层循环。

二、优化

考虑如果数组中的数据已经是排好序的，那么就不需要遍历那么多次，定义一个标志位，如果没有执行交换，则说明数组中的元素已经排好序了，这时直接跳出循环。

三、图解

这里写图片描述

四、代码实现

假如有几个数字int score[] = {67, 69, 75, 88}; 按照从大到小排序。

有2种思路

第一种，score[j] 和 score[j+1] 比较 如果 前者比后者小，把前者和后者调换顺序，两两调换后一轮下来 最小的会被排到最后去。每一轮j都从0开始，当i轮排序，就有最后面的i个数字因为他是最小的，所以后面的每轮都不用理他了，也就是 score.length-1-i 往后的数不用管了，如上，第一轮有4个数字 i为0 ，那么score.length-1-i 为3，也就是下标是3以后的可以不用管，3往后没有数字，所以第一轮所有的数字都要参加比较，第二轮I=1 score.length-1-i 为2 也就是说 下标2后面的 下标为3的数字不用比了，因为两两比较厚，67会到 score[3],实现代码如下：

 for(int i =0;i < score.length - 1;i++)  
            {  
                for(int j = 0;j <  score.length - 1-i;j++)// j开始等于0，  
                {  
                    if(score[j] < score[j+1])  
                    {  
                        int temp = score[j];  
                        score[j] = score[j+1];  
                        score[j+1] = temp;  
                    }  
                }  
            }  

第二种思路，用88 和 75 比较，在和69 比较 在和 67 比较，发现88是最大的，吧他排到第一位(index=0的位置)，然后i=1,也就是第二轮，就不用看下标为0的88了因为他是老大，然后接着比较。；

    for(int i =0;i < score.length - 1;i++)  
            {  
                for(int j = (score.length - 2);j >= i;j--)  
                {  
                    if(score[j] < score[j+1])  
                    {  
                        int temp = score[j];  
                        score[j] = score[j+1];  
                        score[j+1] = temp;  
                    }  
                }  
            }  

说明下j为啥=

 (score.length - 2)

因为length=4,我最多能让下标2和下标3的数字比较(j+1最大等于3)，也就是4-2=2 j最大=2，2和2+1比较 然后1和2比较，然后 0和1 比较。

五、时间复杂度分析

最好的情况下时间复杂度为O（n）：当待排序的数据已经按顺序排好的情况下

最坏的情况下时间复杂度为O（n^2）:因为要比较n-1趟，，每一趟又要比较（n-1-i）次

参考资料

• https://blog.csdn.net/qq_34992845/article/details/53271184
• https://blog.csdn.net/shuaizai88/article/details/73250615