这样的冒泡程序是否还可以优化呢？答案是肯定的。试想一下，如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将i=2到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了，如图9-3-5所示。
    image.png
    当i=2时，我们已经对9与8，8与7，……，3与2作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag来实现这一算法的改进。

    1. /* 对顺序表L作改进冒泡算法 */
    2. void BubbleSort2(SqList *L){
    4.     int i, j;
    6.     /* flag用来作为标记 */
    7.     Status flag = TRUE;
    9.     /* 若flag为true说明有过数据交换，否则停止循环 */
    10.     for (i = 1; i < L->length && flag; i++){
    12.         /* 初始为false */
    13.         flag = FALSE;
    15.         for (j = L->length - 1; j >= i; j--){
    17.             if (L->r[j] > L->r[j + 1]){
    19.                 /* 交换L->r[j]与L->r[j+1]的值 */
    20.                 swap(L, j, j + 1);
    22.                 /* 如果有数据交换，则flag为true */
    23.                 flag = TRUE;
    24.             } 
    25.         } 
    26.     }
    27. }

    代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。