基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序 - 图1

Java实现1

  1. public class BubbleSort {
  2.     public static void main(String[] args) {
  3.         int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
  4.         System.out.println("排序之前：");
  5.         for (int i = 0; i < a.length; i++) {
  6.             System.out.print(a[i]+" ");
  7.         }
  8.         //冒泡排序
  9.         for (int i = 0; i < a.length; i++) {
  10.             for(int j = 0; j<a.length-i-1; j++){
  11.                 //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
  12.                 if(a[j]>a[j+1]){
  13.                     int temp = a[j];
  14.                     a[j] = a[j+1];
  15.                     a[j+1] = temp;
  16.                 }
  17.             }
  18.         }
  19.         System.out.println();
  20.         System.out.println("排序之后：");
  21.         for (int i = 0; i < a.length; i++) {
  22.             System.out.print(a[i]+" ");
  23.         }
  24.     }
  25. }

Java实现2

  1. /**  
  2.  * 冒泡法排序<br/>  
  3.  * <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>  
  4.  * <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>  
  5.  * <li>针对所有的元素重复以上的步骤，除了最后一个。</li>  
  6.  * <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>  
  7.  *   
  8.  * @param numbers  需要排序的整型数组  
  9.  */  
  10. public static void bubbleSort(int[] numbers) {   
  11.     int temp; // 记录临时中间值   
  12.     int size = numbers.length; // 数组大小   
  13.     for (int i = 0; i < size - 1; i++) {   
  14.         for (int j = i + 1; j < size; j++) {   
  15.             if (numbers[i] < numbers[j]) { // 交换两数的位置   
  16.                 temp = numbers[i];   
  17.                 numbers[i] = numbers[j];   
  18.                 numbers[j] = temp;   
  19.             }   
  20.         }   
  21.     }   
  22. }

Java实现3

  1. public class BubbleSort<T extends Comparable<T>> {
  2.     private BubbleSort() { }
  3.     public static <T extends Comparable<T>> T[] sort(T[] unsorted) {
  4.         boolean swapped = true;
  5.         int length = unsorted.length;
  6.         while (swapped) {
  7.             swapped = false;
  8.             for (int i = 1; i < length; i++) {
  9.                 if (unsorted[i].compareTo(unsorted[i - 1]) < 0) {
  10.                     swap(i, i - 1, unsorted);
  11.                     swapped = true;
  12.                 }
  13.             }
  14.             length--;
  15.         }
  16.         return unsorted;
  17.     }
  18.     private static <T extends Comparable<T>> void swap(int index1, int index2, T[] unsorted) {
  19.         T value = unsorted[index1];
  20.         unsorted[index1] = unsorted[index2];
  21.         unsorted[index2] = value;
  22.     }
  23. }

总结

冒泡排序是一种稳定的排序方法。　

  • 若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
  • 若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值 O(n^2)
  • 起泡排序平均时间复杂度为O(n^2)