排序--冒泡排序

原理：
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止

实现：

 private static void swap(int[] array, int i, int j)
 {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
  }

 public static void bubbleSort(int[] array)
 {
  int n = array.length;
  boolean swaped = false;

  for(int i = n - 1; i > 0; i--)
  {
   swaped = false;
   for(int j = 0 ; j < i; j++)
    if( array[j] > array[j + 1] )
    {
     swap(array, j, j + 1);
     swaped = true;
    }

   if (!swaped)
    break;
  }
 }

算法复杂度分析：

初始文件状态	正序	反序	无序
第i趟比较次数	n – i	n - i	n - i
总关键字比较次数	n -1	n2 /2	n2 /2
第i趟移动次数	0	n - i	(n – i) / 2
总关键字移动次数	0	n2 /2	n2 /4
时间复杂度	O(n)	O(n2)	O(n2)

空间复杂O(1)

稳定性：
冒泡排序为稳定排序

算法改进：
增加一个lastExchanged标识位，标记一趟排序后最后一个发生交换的位置，则该位置往后都有序，不用在冒泡

 public static void bubbleSort(int[] array)
 {
  int n = array.length;
  boolean swaped = false;
  int lastExchanged = n - 1;
  int i = n - 1;
  int count = 0;

  while( i > 0 )
  {
   swaped = false;
   for(int j = 0 ; j < i; j++)
   {
    if( array[j] > array[j + 1] )
    {
     swap(array, j, j + 1);
     lastExchanged = j;
     swaped = true;
    }
    count++;
   }
   if (!swaped)
    break;
   i = lastExchanged;
  }
  System.out.println(count);
 }

实验结果，需要移动比较次数明显减少