基本算法连载（5）－Bubble sort

冒泡排序基于交换的思想，简单，易于实现,时间复杂度为O(n^2)。它最多只能充当排序算法的一种演示，不会运用到实际开发中，因为它声名狼藉。看看算法界的泰 斗Donald Knuth是怎么说的，“The bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.”既然如此，冒泡排序的问题出在哪里呢？ “Large elements at the top of the list do not pose a problem, as they are quickly swapped downwards. Small elements at the bottom, however, move to the top extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.”
针对问题根源，人们找到了一些缓解方案。一个是bidirectional bubble sort，一个是comb sort。

• bidirectional bubble sort：一趟排序到达数列尾部时，从尾部开始遍历。到达头部后，接着又从头部向尾部遍历，如此反复，完成排序。此时时间复杂度仍然是O(n)。

• comb sort：进行排序时，每次比较交换的元素跨度将不局限于1。当turtle都移到头部时，元素跨度将变成1，完成最终的排序。元素跨度值的设置对排序性 能有重大影响，经验表明，跨度最先选择为数列长度除以1.3所获得的商值是最优的。此种算法的时间复杂度为O(nlgn)。代码示例如下：

private static int newGap(int gap){
gap = gap * 10 /13;
if(gap == 9 || gap == 10)
gap = 11;

if(gap < 1){
return 1;
}else{
return gap;
}

}

public static void sort(int a[]){
int gap = a.length;
boolean swapped;
do{
swapped = false;
gap = newGap(gap);

for(int i=0;i<a.length-gap;i++){
if(a[i] > a[i+gap]){
swapped = true;
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
}
}

}while(gap>1 || swapped);

}