在使用冒泡算法排序时，什么时候最快，什么时候最慢呢？在2020年CSP-J初赛中，其中一道选择题还真考过这个问题。

很明显，当输入的数据已经是我们想要的序列–正序的时候，比较的次数最少（$n-1$次），所以时间最快（就是想问一下，都已经正序了，还要这排序有何用）；当输入的数据与上面序列完全相反–反序时，比较次数最多（$n(n-1)/2$次），所以冒泡算法的时间复杂度为$O(n^2)$。

改进一：设置标识变量

在算法之排序（1）：冒泡中，所使用的例子就是反序，要求的结果是从大到小排序，而输入的数据是从小到大排序，因此，比较的次数为4×5÷2 =10次。但在实际中，大多数情况下，输入的数据是杂乱的，所以，排序完成时，比较次数应该$≤ n(n-1)/2$。

还是拿算法之排序（1）：冒泡中的五个数字举例，输入顺序变为$2、87、93、32、8$。利用冒泡算法，第一趟排序后，数字顺序是$87、93、32、8、2$；第二趟排序后，数字顺序是$93、87、32、8、2$。此时，排序结束，程序也应该终止，但从程序代码可以看出，不管输入数字的顺序什么样，都是执行$4×5÷2=10$次比较。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

int main(){
    int a[100], n;
    cin >> n; 
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    for(int i = 0; i < n - 1; ++i){ //不管什么情况下，程序都要运行n-1趟
        for(int j = 0; j < n - 1 - i; ++j){
            if (a[j]<a[j+1]) // 不管什么情况下，比较次数为n(n-1)/2次
                swap(a[j], a[j+1]);
        }
    }
    
    for(int i = 0; i < n; ++i){
        cout << a[i] << " ";
    }
}

为了解决这个问题，稍微优化一下算法，我们引入一个标识变量isChanged，来判断比较过程中，是否有数字发生了交换。如果没有发生交换，说明序列已经按照我们的要求排序完成，程序不必继续进行下去了。

优化后的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<iostream>
using namespace std;

int main(){
    int a[100], n;
  	bool isChanged = 1; //设置变量isChanged，表示中某一趟的排序中，是否有数字交换过。
    cin >> n; 
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    for(int i = 0; i < n - 1 && isChanged = 1; ++i){ 
      	isChanged = 0;//初始化为0
        for(int j = 0; j < n - 1 - i; ++j){
            if (a[j]<a[j+1]) {
              swap(a[j], a[j+1]);
              isChanged = 1;//如果发生了交换，isChanged = 1
            }		
        }
    }
    
    for(int i = 0; i < n; ++i){//输出结果
        cout << a[i] << " ";
    }
}

改进二：来回排序

来回排序是冒泡排序的一种变形，又称为定向冒泡排序，还有人起了一个好听的名字“鸡尾酒排序”。这种算法和一般的冒泡排序的区别在于排序时，左右双向进行比较。

以序列$[2,3,4,5,1]$为例，来回排序结合标识变量，只需要从左到右、从右到左两趟比较就可以完成排序，但如果使用一般的冒泡排序则需要进行四趟比较才能完成排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<iostream>
using namespace std;

int main(){
    int a[100], n, left, right;
  	bool isChanged = 1; //设置变量isChanged，表示中某一趟的排序中，是否有数字交换过。
    cin >> n; 
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    left = 0;
    right = n - 1;
    while(left < right && isChanged =1){
        isChanged = 0;
        for (int i = left; i <right; ++i){//从左向右进行比较
            if (a[i] < a[i+1]){
                swap(a[i], a[i+1]);
                isChanged = 1;
            }
        }
        -- right;
        
        for (int i = right; i > left && isChanged = 1; --i){//从右向左进行比较
            if (a[i] < a[i+1]){
                swap(a[i-1], a[i]);
                isChanged = 1;
            }
        }
        ++ left;
    }

    for(int i = 0; i < n; ++i){//输出结果
        cout << a[i] << " ";
    }
}

无论是回来排序还是冒泡排序的效率都非常低。若在程序设计竞赛中采用上述算法，容易引起超时。但是，冒泡排序是排序算法中经典的一种算法，往往在选择题中对大家进行考察。

image