9.3.2 冒泡排序算法

我们来看看正宗的冒泡算法，有没有什么改进的地方。

/* 对顺序表L作冒泡排序 */  
void BubbleSort（SqList *L）  
{  
int i,j;  
for（i=1;i<L->length;i++）  
{  
for（j=L->length-1;j>=i;j--） /* 注意j是从后往前循环 */  
{  
if（L->r[j]>L->r[j+1]） /* 若前者大于后者（注意这里与上一算法差异）*/  
{  
swap（L,j,j+1）; /* 交换L->r[j]与L->r[j+1]的值 */  
}  
}  
}  
} 

依然假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}，当i=1时，变量j由8反向循环到1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第1的位置。如图9‐5‐3所示，当i=1、j=8时，我们发现6>2，因此交换了它们的位置，j=7时，4>2，所以交换……直到j=2时，因为1<2，所在不交换。j=1时，9>1，交换，最终得到最小值1放置第一的位置。事实上，在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字2从第九位置提到到了第三的位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法。

（点击查看大图）图9-3-3

当i=2时，变量j由8反向循环到2，逐个比较，在将关键字2交换到第二位置的同时，也将关键字4和3有所提升。

图9-3-4

后面的数字变换很简单，这里就不在赘述了。