计算机程序设计艺术-----冒泡排序

冒泡排序：一种最简单的排序算法。
基本思想：依次比较两数，保证小数在前，大数在后。
有两种方案：一、在每趟选出最小数，二、每趟选出最大数。
每趟选出最大数的实现思想是：在第一趟，比较第一个数和第二个数，如果第一个数大于第二个数，交换这两个数，比较第二个数和第三个数，如果第二个数大于第三个数，交换这两个数，依次类推，比较倒数第二个数和最后一个数，如果倒数第二数大于最后一个数，交换这两个数，最后一个数就是最大数；第二趟，比较第一个数和第二个数，如果第一个数大于第二个数，交换这两个数，依次类推，直到比较倒数第三数和倒数第二数，如果倒数第三数比倒数第二数大，交换这两数，这样倒数第二数就是第二大数，依次类推，直到排好序。


算法实现：
   for(int i=n;i>1;i--){
   for(int j=1;j<i;j++){
   if(a[j]>a[j+1]){
   swap(a[j],a[j+1]);
   }
   }
}
冒泡排序的改进（鸡尾混合排序）：
基本思想：依次比较两数，保证小数在前，大数在后。
方案：交替选出最大数，最小数。
实现：在第一趟，比较第一个数和第二个数，如果第一个数大于第二个数，交换这两个数，比较第二个数和第三个数，如果第二个数大于第三个数，交换这两个数，依次类推，比较倒数第二个数和最后一个数，如果倒数第二数大于最后一个数，交换这两个数，最后一个数就是最大数；第二趟，比较倒数第二个数和倒数第三个数，当倒数第三个数大于倒数第二个数时，交换这两个数，依次类推直到比较第一个数和第二个数，如果第一个大于第二个数，交换这两个数，这样第一个数就是最小数，依次类推，直到排好序。

代码： int start=1;
int end=n;
int r=1;
boolean orientationFlat=true;//如果为true，则r++，否则r--
while(start<end){
if(a[r]>a[r+1]){//判断
swap(a[r],a[r+1]);
}
if(r==end-1){
end--;
orientationFlat=false;
}
if(r==start){
start++;
orientationFlat=true;
}
if(orientationFlat){
r++;
}
else{
r--;
}
}