博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
算法之冒泡排序
阅读量：6979 次
发布时间：2019-06-27

本文共 7249 字，大约阅读时间需要 24 分钟。

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

冒泡排序的图解是：

总结一句话就是：连续比较相邻的元素，降序则呼唤。有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
    
     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
算法分析：

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

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

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

冒泡算法的改进：

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

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

BubbleImprovedSort.java

[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
    
     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

泛型冒泡排序:

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

BubbleGenericTypeSort .java

[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>  
public class BubbleGenericTypeSort {	//泛型冒泡排序，使用Comparable对元素进行排序		public static 
     
      > void bubbleGenericTypeSort(E[] list){			int n=list.length;			for(int i=1;i
      
       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

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

BubbleComparator.java

[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 
    
       void bubbleComparatorSort(List
     
       list,Comparator
       comparator){//
      是E的父类    	 int n=list.size(); 		for(int i=1;i
      
        list=new ArrayList
       
        ();        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
        
          {    	GeometricObjectComparator(){}     		@Override		public int compare(GeometricObject o1, GeometricObject o2) {			// TODO Auto-generated method stub			float area1=o1.getArea();			float area2=o2.getArea();			if(area1

你可能感兴趣的文章
Windows 7 开发新特性
查看>>
在客户端调用MOSS的搜索服务，实现更加灵活的搜索控制
查看>>
C++:STL标准入门汇总
查看>>
1001: 整数求和
查看>>
How to develop Silverlight 4 using Visual Studio Express 2010
查看>>
浏览器前进后退对下拉框数据的丢失（省市联动实现和例子）
查看>>
构建安全的 ASP.NET 应用程序
查看>>
从源代码编译里程碑的 ICS ROM
查看>>
Flex通信-Java服务端通信实例
查看>>
Nginx学习笔记（一） Nginx架构
查看>>
JavaScript sync and async（同步和异步）
查看>>
.Net Winform 开发笔记（四） 透过现象看本质
查看>>
Linux下显示硬盘空间的两个命令
查看>>
What’s new: Windows Phone 7 与 Windows Phone 6.5功能对比
查看>>
用Swift实现一款天气预报APP（三）
查看>>
HttpApplication事件&ASP.NET页面周期
查看>>
春天。
查看>>
MapReduce对交易日志进行排序的Demo(MR的二次排序)
查看>>
Android -- Fragment注意事项
查看>>
Android APP测试的日志文件抓取
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-05 00:39:21   当前IP: 18.217.47.171   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我