IT虾米网

算法之冒泡排序详解

wyy 2018年07月09日 程序员 408 0

冒泡排序算法需要遍历几次数组。每次遍历都要比较连续相邻的元素,如果某一对相邻元素是降序,则互换它们的值,否则,保持不变。由于较小的值像“气泡”一样逐渐浮想顶部,而较大的值沉向底部,所以叫冒泡排序。

冒泡排序的图解是:


总结一句话就是:连续比较相邻的元素,降序则呼唤。有n个数,共需要比较n-1趟,第i趟,需要比较n-i次。

BubbleSort.Java

  1. public class BubbleSort {//时间复杂度O(n^2)  
  2.       
  3.     public static void display(int[] array){  
  4.         for(int i=0;i<array.length;i++){    
  5.              System.out.print(array[i]+"\t");    
  6.          }    
  7.          System.out.println();   
  8.     }  
  9.     //冒泡排序  
  10.     public static void bubbleSort(int[] list){  
  11.         int n=list.length;  
  12.         for(int i=1;i<n;i++){//总共比较n-1趟  
  13.             for(int j=0;j<n-i;j++){//第i趟比较n-i次  
  14.                 if(list[j]>list[j+1]){  
  15.                     int temp;  
  16.                     temp=list[j];  
  17.                     list[j]=list[j+1];  
  18.                     list[j+1]=temp;               
  19.                 }  
  20.             }  
  21.               
  22.             System.out.print("第"+(i)+"轮排序结果:");    
  23.             display(list);  
  24.         }  
  25.           
  26.     }  
  27.     public static void main(String args[]){  
  28.         int[] list={25,6,56,24,9,12,55};     
  29.         System.out.println("冒泡排序前的list是:");  
  30.         for(int i=0;i<list.length;i++){  
  31.             System.out.print(list[i]+" ");  
  32.         }  
  33.         System.out.println();  
  34.         bubbleSort(list);//进行冒泡排序  
  35.         System.out.println();  
  36.         System.out.println("冒泡排序后的list是:");  
  37.         for(int i=0;i<list.length;i++){  
  38.             System.out.print(list[i]+" ");  
  39.         }  
  40.     }  
  41. }  
public class BubbleSort {//时间复杂度O(n^2) 
	 
	public static void display(int[] array){ 
		for(int i=0;i<array.length;i++){   
	         System.out.print(array[i]+"\t");   
	     }   
	     System.out.println();  
	} 
	//冒泡排序 
	public static void bubbleSort(int[] list){ 
		int n=list.length; 
		for(int i=1;i<n;i++){//总共比较n-1趟 
			for(int j=0;j<n-i;j++){//第i趟比较n-i次 
				if(list[j]>list[j+1]){ 
					int temp; 
					temp=list[j]; 
					list[j]=list[j+1]; 
					list[j+1]=temp;				 
				} 
			} 
			 
			System.out.print("第"+(i)+"轮排序结果:");   
	        display(list); 
		} 
		 
	} 
    public static void main(String args[]){ 
    	int[] list={25,6,56,24,9,12,55};    
    	System.out.println("冒泡排序前的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	} 
    	System.out.println(); 
    	bubbleSort(list);//进行冒泡排序 
    	System.out.println(); 
    	System.out.println("冒泡排序后的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	} 
    } 
} 

算法分析:

最差的情况下,冒泡排序算法需要进行n-1次遍历。第一次遍历需要n-1次比较,第二次遍历需要n-2次比较,依次进行;因此比较总数为:

(n-1)+(n-2)+...+2+1=n(n-1)/2=O(n2)

冒泡排序的时间复杂度为O(n2)


冒泡算法的改进:

冒泡排序的效率比较低,所以我们要通过各种方法改进。在上例中,第四轮排序之后实际上整个数组已经是有序的了,最后两轮的比较没必要进行。

注意:如果某次遍历中没有发生交换,那么就不必进行下一次遍历,因为所有元素已经排好了。

BubbleImprovedSort.java

  1. public class BubbleImprovedSort {  
  2.     public static void display(int[] array){  
  3.         for(int i=0;i<array.length;i++){    
  4.              System.out.print(array[i]+"\t");    
  5.          }    
  6.          System.out.println();   
  7.     }  
  8.     //冒泡排序  
  9.     public static void bubbleSort(int[] list){  
  10.             int n=list.length;  
  11.             boolean NeedNextPass=true;  
  12.             for(int i=1;i<n&&NeedNextPass;i++){//总共比较n-1趟,如果某趟遍历中没有交换,那么不需要下次遍历,因为元素以排好  
  13.                 NeedNextPass=false;  
  14.                 for(int j=0;j<n-i;j++){//第i趟比较n-i次  
  15.                     if(list[j]>list[j+1]){  
  16.                         int temp;  
  17.                         temp=list[j];  
  18.                         list[j]=list[j+1];  
  19.                         list[j+1]=temp;       
  20.                         NeedNextPass=true;  
  21.                     }  
  22.                 }  
  23.                 System.out.print("第"+(i)+"轮排序结果:");    
  24.                 display(list);  
  25.             }  
  26.         }  
  27.         public static void main(String args[]){  
  28.             int[] list={25,6,56,24,9,12,55};   
  29.             System.out.println("改进的冒泡排序:");  
  30.             System.out.println("排序前的list是:");  
  31.             for(int i=0;i<list.length;i++){  
  32.                 System.out.print(list[i]+" ");  
  33.             }  
  34.             System.out.println();  
  35.             bubbleSort(list);//进行冒泡排序  
  36.             System.out.println();  
  37.             System.out.println("排序后的list是:");  
  38.             for(int i=0;i<list.length;i++){  
  39.                 System.out.print(list[i]+" ");  
  40.             }  
  41.         }  
  42.   
  43. }  
public class BubbleImprovedSort { 
	public static void display(int[] array){ 
		for(int i=0;i<array.length;i++){   
	         System.out.print(array[i]+"\t");   
	     }   
	     System.out.println();  
	} 
	//冒泡排序 
    public static void bubbleSort(int[] list){ 
			int n=list.length; 
			boolean NeedNextPass=true; 
			for(int i=1;i<n&&NeedNextPass;i++){//总共比较n-1趟,如果某趟遍历中没有交换,那么不需要下次遍历,因为元素以排好 
				NeedNextPass=false; 
				for(int j=0;j<n-i;j++){//第i趟比较n-i次 
					if(list[j]>list[j+1]){ 
						int temp; 
						temp=list[j]; 
						list[j]=list[j+1]; 
						list[j+1]=temp;		 
						NeedNextPass=true; 
					} 
				} 
				System.out.print("第"+(i)+"轮排序结果:");   
		        display(list); 
			} 
		} 
	    public static void main(String args[]){ 
	    	int[] list={25,6,56,24,9,12,55};  
	    	System.out.println("改进的冒泡排序:"); 
	    	System.out.println("排序前的list是:"); 
	    	for(int i=0;i<list.length;i++){ 
	    		System.out.print(list[i]+" "); 
	    	} 
	    	System.out.println(); 
	    	bubbleSort(list);//进行冒泡排序 
	    	System.out.println(); 
	    	System.out.println("排序后的list是:"); 
	    	for(int i=0;i<list.length;i++){ 
	    		System.out.print(list[i]+" "); 
	    	} 
	    } 
 
} 


泛型冒泡排序:

例1:元素实现comparable接口。排序是字符串string,string实现了comparable接口

BubbleGenericTypeSort .java

  1. <span style="font-size:24px;">public class BubbleGenericTypeSort {  
  2.     //泛型冒泡排序,使用Comparable对元素进行排序  
  3.         public static <E extends Comparable<E>> void bubbleGenericTypeSort(E[] list){  
  4.             int n=list.length;  
  5.             for(int i=1;i<n;i++){//总共比较n-1趟  
  6.                 for(int j=0;j<n-i;j++){//第i趟比较n-i次  
  7.                     if(list[j].compareTo(list[j+1])>0){  
  8.                         E temp;  
  9.                         temp=list[j];  
  10.                         list[j]=list[j+1];  
  11.                         list[j+1]=temp;               
  12.                     }  
  13.                 }  
  14.             }  
  15.         }  
  16.           
  17.     public static void main(String[] args) {  
  18.         // TODO Auto-generated method stub  
  19.         /*Integer[] list={2,1,56,34,9,6,55,20,37,22}; //泛型的Integer ,包装类都实现了Comparable接口 
  20.         System.out.println("冒泡排序前的list是:"); 
  21.         for(int i=0;i<list.length;i++){ 
  22.             System.out.print(list[i]+" "); 
  23.         } 
  24.         bubbleGenericTypeSort(list);//进行冒泡排序 
  25.         System.out.println(); 
  26.         System.out.println("冒泡排序后的list是:"); 
  27.         for(int i=0;i<list.length;i++){ 
  28.             System.out.print(list[i]+" "); 
  29.         }*/  
  30.         String[] list={"John","Mike","Jack","Bob","Zoo","Meache","Abrow","Richer"}; //泛型的String ,包装类都实现了Comparable接口  
  31.         System.out.println("冒泡排序前的list是:");  
  32.         for(int i=0;i<list.length;i++){  
  33.             System.out.print(list[i]+" ");  
  34.         }  
  35.         bubbleGenericTypeSort(list);//进行冒泡排序  
  36.         System.out.println();  
  37.         System.out.println("冒泡排序后的list是:");  
  38.         for(int i=0;i<list.length;i++){  
  39.             System.out.print(list[i]+" ");  
  40.         }  
  41.     }  
  42. }  
  43.   
  44.   
<span style="font-size:24px;">public class BubbleGenericTypeSort { 
	//泛型冒泡排序,使用Comparable对元素进行排序 
		public static <E extends Comparable<E>> void bubbleGenericTypeSort(E[] list){ 
			int n=list.length; 
			for(int i=1;i<n;i++){//总共比较n-1趟 
				for(int j=0;j<n-i;j++){//第i趟比较n-i次 
					if(list[j].compareTo(list[j+1])>0){ 
						E temp; 
						temp=list[j]; 
						list[j]=list[j+1]; 
						list[j+1]=temp;				 
					} 
				} 
			} 
		} 
		 
	public static void main(String[] args) { 
		// TODO Auto-generated method stub 
		/*Integer[] list={2,1,56,34,9,6,55,20,37,22}; //泛型的Integer ,包装类都实现了Comparable接口 
    	System.out.println("冒泡排序前的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	} 
    	bubbleGenericTypeSort(list);//进行冒泡排序 
    	System.out.println(); 
    	System.out.println("冒泡排序后的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	}*/ 
		String[] list={"John","Mike","Jack","Bob","Zoo","Meache","Abrow","Richer"}; //泛型的String ,包装类都实现了Comparable接口 
    	System.out.println("冒泡排序前的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	} 
    	bubbleGenericTypeSort(list);//进行冒泡排序 
    	System.out.println(); 
    	System.out.println("冒泡排序后的list是:"); 
    	for(int i=0;i<list.length;i++){ 
    		System.out.print(list[i]+" "); 
    	} 
    } 
} 
 


例2.元素实现自定义的Comparator比较器接口


BubbleComparator.java

  1. import java.util.ArrayList;  
  2. import java.util.Comparator;  
  3. import java.util.List;  
  4.   
  5. public class BubbleComparator {  
  6.      public static <E>  void bubbleComparatorSort(List<E> list,Comparator<? super E> comparator){//<? super E>是E的父类  
  7.          int n=list.size();  
  8.         for(int i=1;i<n;i++){//总共比较n-1趟  
  9.             for(int j=0;j<n-i;j++){//第i趟比较n-i次  
  10.                 if(comparator.compare(list.get(j), list.get(j+1))==1){  
  11.                     E temp;  
  12.                     temp=list.get(j);  
  13.                     list.set(j, list.get(j+1));  
  14.                     list.set(j+1, temp);                          
  15.                 }  
  16.             }  
  17.         }  
  18.      }  
  19.           
  20.     public static void main(String[] args) {  
  21.         // TODO Auto-generated method stub        
  22.         List<GeometricObject> list=new ArrayList<GeometricObject>();  
  23.         list.add(new Rectangle(4,5,"矩形4,5"));  
  24.         list.add(new Circle(3,"圆3"));  
  25.         list.add(new Square(3,"正方形3"));  
  26.         list.add(new Rectangle(2,6,"矩形2,6"));  
  27.         list.add(new Circle(4,"圆4"));  
  28.           
  29.         System.out.println("冒泡排序前的list是:");  
  30.         for(int i=0;i<list.size();i++){  
  31.             System.out.print(list.get(i).getName()+":"+list.get(i).getArea()+"  ");  
  32.         }  
  33.         bubbleComparatorSort(list, new GeometricObjectComparator());//进行冒泡排序  
  34.         System.out.println();  
  35.         System.out.println("冒泡排序后的list是:");  
  36.         for(int i=0;i<list.size();i++){  
  37.             System.out.print(list.get(i).getName()+":"+list.get(i).getArea()+"  ");  
  38.         }  
  39.           
  40.     }  
  41.     
  42.     public static class GeometricObjectComparator implements Comparator<GeometricObject> {  
  43.         GeometricObjectComparator(){}  
  44.        
  45.         @Override  
  46.         public int compare(GeometricObject o1, GeometricObject o2) {  
  47.             // TODO Auto-generated method stub  
  48.             float area1=o1.getArea();  
  49.             float area2=o2.getArea();  
  50.             if(area1<area2){  
  51.                 return -1;  
  52.             }  
  53.             else if(area1==area2)  
  54.                 return 0;  
  55.             else   
  56.                 return 1;  
  57.         }  
  58.           
  59.     }  
  60. }  
import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.List; 
 
public class BubbleComparator { 
     public static <E>  void bubbleComparatorSort(List<E> list,Comparator<? super E> comparator){//<? super E>是E的父类 
    	 int n=list.size(); 
 		for(int i=1;i<n;i++){//总共比较n-1趟 
 			for(int j=0;j<n-i;j++){//第i趟比较n-i次 
 				if(comparator.compare(list.get(j), list.get(j+1))==1){ 
 				    E temp; 
 					temp=list.get(j); 
 					list.set(j, list.get(j+1)); 
 					list.set(j+1, temp);						 
 				} 
 			} 
 		} 
     } 
		 
	public static void main(String[] args) { 
		// TODO Auto-generated method stub       
        List<GeometricObject> list=new ArrayList<GeometricObject>(); 
        list.add(new Rectangle(4,5,"矩形4,5")); 
        list.add(new Circle(3,"圆3")); 
        list.add(new Square(3,"正方形3")); 
        list.add(new Rectangle(2,6,"矩形2,6")); 
        list.add(new Circle(4,"圆4")); 
         
        System.out.println("冒泡排序前的list是:"); 
    	for(int i=0;i<list.size();i++){ 
    		System.out.print(list.get(i).getName()+":"+list.get(i).getArea()+"  "); 
    	} 
    	bubbleComparatorSort(list, new GeometricObjectComparator());//进行冒泡排序 
    	System.out.println(); 
    	System.out.println("冒泡排序后的list是:"); 
    	for(int i=0;i<list.size();i++){ 
    		System.out.print(list.get(i).getName()+":"+list.get(i).getArea()+"  "); 
    	} 
         
	} 
   
    public static class GeometricObjectComparator implements Comparator<GeometricObject> { 
    	GeometricObjectComparator(){} 
      
		@Override 
		public int compare(GeometricObject o1, GeometricObject o2) { 
			// TODO Auto-generated method stub 
			float area1=o1.getArea(); 
			float area2=o2.getArea(); 
			if(area1<area2){ 
				return -1; 
			} 
			else if(area1==area2) 
				return 0; 
			else  
				return 1; 
		} 
    	 
    } 
} 

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数据结构之链表详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。