冒泡排序的实现及优化

分手后的思念是犯贱 2022-04-18 05:19 176阅读 0赞

## 冒泡实现原理 ##

冒泡排序是交换排序中最简单的排序方法，基本思想是两两比较相邻的关键码，如果反序就反过来交换。

for(int i=0;i<arr.length-1;i++) {
    			for(int j=0;j<arr.length-1;j++) {	
    				 if(arr[j]>arr[j+1]) {
    					 temp=arr[j];//将下标为j的值赋值给temp
    					 arr[j]=arr[j+1];//再将下标为j+1的赋值给j
    					 arr[j+1]=temp;	//再将temp的值赋值给arr[j+1]			 		
    				  }		
    			  }

用上以上代码基本就可以实现排序，但是这样会出现一个问题，可能排序已经完成了，可是程序依然要所有循环结束才停止，这样大大的浪费了时间和资源，怎么去规避这种情况呢？  
我们可以设置一个检测，当循环时发生了值交换，也就是执行

if(arr[j]>arr[j+1]) {
    					 temp=arr[j];//将下标为j的值赋值给temp
    					 arr[j]=arr[j+1];//再将下标为j+1的赋值给j
    					 arr[j+1]=temp;	//再将temp的值赋值给arr[j+1]			 		
    				  }

就执行下一个循环，如果没有发生交换，就表示已经完成排序，就可以结束循环。  
代码实现：

for(int i=0;i<arr.length-1;i++) {
            boolean flag=true;
    		for(int j=0;j<arr.length-1;j++) {	
    			 if(arr[j]>arr[j+1]) {
    				 temp=arr[j];//将下标为j的值赋值给temp
    				 arr[j]=arr[j+1];//再将下标为j+1的赋值给j
    				 arr[j+1]=temp;	//再将temp的值赋值给arr[j+1]	
    				 flag=false;		 		
    			  }		
              if(flag){
                   break;
                   }
    		  }

## 完整代码 ##

package com.list.test;
    
    import java.util.Arrays;
    
    public class MaoPao {
    
    	public static void main(String[] args) {
    		int[] arr= {3,5,54,12,47,59,26,6,584,422};
    		System.out.println(Arrays.toString(arr));
    		int temp=0;
    		for(int i=0;i<arr.length-1;i++) {
    			boolean flag=true;
    			for(int j=0;j<arr.length-1;j++) {	
    				 if(arr[j]>arr[j+1]) {
    					 temp=arr[j];
    					 arr[j]=arr[j+1];
    					 arr[j+1]=temp;					 
    					 flag=false;
    					
    				  }		
    			  }
    			 
    			 if(flag){
    				 break;
    			    }
    			 
    			 System.out.println(Arrays.toString(arr));
    			 System.out.println("#####################");
    		}
    	}
    
    }