算法之冒泡排序

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

冒泡排序的图解是：

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

BubbleSort.Java

[java] view plain copy print ? 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]+" ");          }      }  }   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

[java] view plain copy print ? 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]+" ");              }          }    }   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

[java] view plain copy print ? <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]+" ");          }      }  }    </span>   <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]+" "); } } } </span>

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

BubbleComparator.java

[java] view plain copy print ? 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;          }                }  }   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; } } }