【Java基础】冒泡排序算法原理+实现

深碍√TFBOYSˉ_ 2022-08-23 04:51 124阅读 0赞

几年前的一篇博客中已简单介绍了冒泡排序的原理和过程：[\[两种常见的排序算法\]][Link 1] .今天又恰逢冒泡，索性再来回顾深入一下.

#  **冒泡动画：** #

![Center][]

#  冒泡原理： #

两两比较，大数后移，小数前移；  
 每轮产生一个最大值，放在最后；

#  冒泡过程: #

曾经一位伟人说，循环语句怎么破，按循环逻辑写一遍，你就明白了. so,这里小编就按每一次循环比较的逻辑将结果打印出来了，要好好看...

定义数组:[4, 1, 3, 6, 2]
    -----------当i=0时
    ------------------当j=0次交换
    --------------------------j(0)和j(1)比较
    1 4 3 6 2  
    ------------------当j=1次交换
    --------------------------j(1)和j(2)比较
    1 3 4 6 2  
    ------------------当j=2次交换
    --------------------------j(2)和j(3)比较
    1 3 4 6 2  
    ------------------当j=3次交换
    --------------------------j(3)和j(4)比较
    1 3 4 2 6  
    -----------当i=1时
    ------------------当j=0次交换
    --------------------------j(0)和j(1)比较
    1 3 4 2 6  
    ------------------当j=1次交换
    --------------------------j(1)和j(2)比较
    1 3 4 2 6  
    ------------------当j=2次交换
    --------------------------j(2)和j(3)比较
    1 3 2 4 6  
    -----------当i=2时
    ------------------当j=0次交换
    --------------------------j(0)和j(1)比较
    1 3 2 4 6  
    ------------------当j=1次交换
    --------------------------j(1)和j(2)比较
    1 2 3 4 6  
    -----------当i=3时
    ------------------当j=0次交换
    --------------------------j(0)和j(1)比较
    1 2 3 4 6  
    ---最终排序结果：[1, 2, 3, 4, 6]

# 冒泡优化： #

观察上述运行结果，可以看出，在第3次循环比较时，结果已经是排序完成的结果,说明之后的几次比较是不需要的.那如何才能让它在排序完成之后就停止接着往下比较呢？

重点在这里：**加标识.** 这样优化过后的时间复杂度最好的情况是O(n)

具体代码优化**：[点这里][Link 2]**

#  冒泡实现： #

import java.lang.reflect.Array;
    import java.util.Arrays;
    
    public class sort {
    
    	public static void main(String[] args){
            // 定义一个数组  
            int[] array = {4,1,3,6,2};  
            //打印出数组信息  
            System.out.println("定义数组:"+Arrays.toString(array));  
            
            //调用排序方法
        	bubbleSort(array);
        	
            //打印出最终排序结果  
           System.out.println("---最终排序结果："+Arrays.toString(array)); 
    	
    	}
    	public static void bubbleSort(int[] array){
    		//外层循环--是循环的次数
    		for(int i=0;i<array.length-1;i++){
    			//打印出是第几轮循环
    			System.out.println("-----------当i="+i+"时");
    			//内层循环-一一轮中比较的次数
    			for(int j=0;j<array.length-i-1;j++){
    				//判断比较的数字大小，true就交换，false就不动
    				if(array[j]>array[j+1]){
    					//交换逻辑
    					int temp=array[j];
    					array[j]=array[j+1];
    					array[j+1]=temp;
    				}
    				//打印是第几次交换
    				System.out.println("------------------当j="+j+"次交换");
    				System.out.println("--------------------------j("+j+")和j("+(j+1)+")比较");
    				//循环输出，数组中的数字
    				 for (int l = 0; l < array.length; l++) {  
    		                System.out.print(array[l] + " ");  
    		            }  
    		            System.out.println(" ");  			
    			}	
    		}	
    	}
    }<strong style="font-family: FangSong_GB2312;font-size:18px; background-color: rgb(255, 255, 255);">    </strong>

**总结:**

冒泡排序最坏的时间复杂度是O(n²)，效率比较低，所以在实际应用中使用较少. 但作为一种经典排序算法，还是值得学习.

[Link 1]: http://blog.csdn.net/u010542940/article/details/9115495
[Center]: /images/20220722/fd2086cb89b949d5ae9800015508635c.png
[Link 2]: http://blog.csdn.net/cbs612537/article/details/8513723