初学C++:冒泡排序的写法

　　今天看《C++编程金典》数组这一章，后面有个习题：4-11
4-11：图4-16中的冒泡排序并不适合大型数组，。执行以下简单修改提高冒泡排序方法的性能：
A）：第一遍排序后，大型数字总会成为数组中编号最大的元素；第二遍排序后，就有两个编号最大的数字，依此类推。这样一来，就不是第次进行9次比较，而是第二遍比较8次，第3遍比交7次，依此类推。
B）：数组中的数据可能已经按正确或接近于正确的顺序进行排列，所以如果比较次数较少也能达到理想的效果时，为什么一定要比较9次呢？修改排序方法，查看每次比较后是否数据有无交换，如果没有，那么数据肯定已经采用了正确的排序。如果有交换，则说明至少还需要一次排序。
　　4-16的冒泡排序如下

for(int i=0;i＜len-1;i++)
{

for(int a=0;a＜len-1;a++)
{
 if(array[a]＞array[a+1])
 {
  hold=array[a];
  array[a]=array[a+1];
  array[a+1]=hold;
 }
}
}

这个算法，不管怎么样都要执行(len-1)*(len-1)次。

如果按A的算法优化一下就要执行(len-1)*(len-1-(1+len-2)/2)=(len-1)*(len-1)/2次，也就相当于少执行了一半。

如果再按B的算法优化下，如果本来就是一个有序数组的话，仅需执行len-1次，整个降低了一个数量级。当然如果是最糟情况将执行(len-1)*(len-1)次。

A的算法在内循环完成一次就把内循环的记数条件减1就能做到。

增加一个全局变量比如：b=len-1;

然后在外循环中循环条件增加一个b--；

把内循环的执行条件改为j＜b;

B的算法，只要内循环中的if 语句条件一次也没有执行就跳出循环便可做到。
增加一个全局变量比如：c=0;
然后把 if语句改成if-else 语句，IF条件没有执行也就相当于else语句执行了b次；
在else语句中加入c++;
然后在外循环处比较c ==b;
如不等则继续循环。如相等就退出循环排序完成。