Java基础数组-冒泡排序算法

悠悠 2023-10-08 16:39 37阅读 0赞

冒泡排序算法

*  1、每一次循环结束之后，都要找出最大的数据，放到参与比较的这堆数据的最右边。（冒出最大的那个气泡。）
 *  2、核心：  
    拿着左边的数字和右边的数字比对，当左边 > 右边的时候，交换位置。

原始数据：  
3, 2, 7, 6, 8  
第1次循环：(最大的跑到最右边。)  
2, 3, 7, 6, 8 （3和2比较，2 < 3，所以2和3交换位置）  
2, 3, 7, 6, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）  
2, 3, 6, 7, 8 （7和6交换位置）  
2, 3, 6, 7, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）

经过第1次循环，此时剩下参与比较的数据：2, 3, 6, 7  
第2次循环：  
2, 3, 6, 7 (2和3比较，不需要交换位置)  
2, 3, 6, 7 （3和6比较，不需要交换位置）  
2, 3, 6, 7 (6和7比较，不需要交换位置)

经过第2次循环，此时剩下参与比较的数据：2, 3, 6  
第3次循环：  
2, 3, 6 (2和3比较，不需要交换位置)  
2, 3, 6 （3和6比较，不需要交换位置）

经过第3次循环，此时剩下参与比较的数据：2, 3  
第4次循环：  
2, 3 (2和3比较，不需要交换位置)

--------------------

参与比较的数据：9 8 10 7 6 0 11  
第1次循环：  
8 9 10 7 6 0 11 (第1次比较：交换)  
8 9 10 7 6 0 11 (第2次比较：不交换)  
8 9 7 10 6 0 11 (第3次比较：交换)  
8 9 7 6 10 0 11 (第4次比较：交换)  
8 9 7 6 0 10 11 (第5次比较：交换)  
8 9 7 6 0 10 11 (第6次比较：不交换)  
最终冒出的最大数据在右边：11

参与比较的数据：8 9 7 6 0 10  
第2次循环：  
8 9 7 6 0 10（第1次比较：不交换）  
8 7 9 6 0 10（第2次比较：交换）  
8 7 6 9 0 10（第3次比较：交换）  
8 7 6 0 9 10（第4次比较：交换）  
8 7 6 0 9 10（第5次比较：不交换）

参与比较的数据：8 7 6 0 9  
第3次循环：  
7 8 6 0 9（第1次比较：交换）  
7 6 8 0 9（第2次比较：交换）  
7 6 0 8 9（第3次比较：交换）  
7 6 0 8 9（第4次比较：不交换）

参与比较的数据：7 6 0 8  
第4次循环：  
6 7 0 8（第1次比较：交换）  
6 0 7 8（第2次比较：交换）  
6 0 7 8（第3次比较：不交换）

参与比较的数据：6 0 7  
第5次循环：  
0 6 7（第1次比较：交换）  
0 6 7（第2次比较：不交换）

参与比较的数据：0 6  
第6次循环：  
0 6 （第1次比较：不交换）  
时间复杂度：O( n^2 )  
空间复杂度：O(1)

#### 示例代码： ####

public class BubbleSort {
        
        public static void main(String[] args) {
        
    
            int[] arr = {
        3,1,6,2,5,8,4};
    
            //冒泡排序算法
            int count = 0;
            int count2 = 0;
            for(int i = arr.length-1;i>0;i--){
        
                for(int j = 0;j<i;j++) {
        
                    //统计次数// 不管是否需要交换位置，总之是要比较一次的。
                    count++;
                    if (arr[j] > arr[j+1]) {
        
                        // 交换位置。
                        // arr[j] 和 arr[j+1] 交换
                        //arr[j] = arr[j+1];
                        int temp;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        //统计交换次数
                        count2++;
                    }
                }
    
            }
            System.out.println("比较次数：" + count);
            System.out.println("交换次数：" + count2);
    
            for(int i = 0;i<arr.length;i++){
        
                System.out.println(arr[i]);
            }
        }
    }

#### 运行结果： ####

![在这里插入图片描述][2929f0389fab43289cf356a811f55dd6.png]

[2929f0389fab43289cf356a811f55dd6.png]: https://img-blog.csdnimg.cn/2929f0389fab43289cf356a811f55dd6.png