排序算法讨论与讲解1.2：冒泡排序的优化

Deep欠揍 | 深度欠揍

2026-07-25 05:42:56

发布于：浙江

18阅读

0回复

0点赞

1.1我们学了冒泡排序，但懂行的人都知道O(n^2)的时间复杂度在排序界是很慢的，我们今天就要来优化一下他。

我们知道：在冒泡排序的遍历当中，如果没有发生交换，肯定是数组已经有序的了
我们可以通过一个bool变量flag，实时监测一轮遍历中有没有发生交换，如果没有可以直接break
代码实现：

#include <bits/stdc++.h>
using namespace std;
void BubbleSort(int a[],int n){
    bool flag=true;
    for(int i=0;i<n;i++){
        flag=false;
        for(int j=0;j<n-i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        if(!flag)break;
    }
}
int main(){
    int a[10]={5,1,9,8,3,6,2,4,7};
    BubbleSort(a,10);
    for(int i:a)cout<<a[i]<<" ";
}

这次各属性稍有更新
时间复杂度：
最好（已经有序）：O(n)
平均：O(n^2)
最坏：O(n^2)

空间复杂度：
同普通冒泡

稳定性：
同普通冒泡

代码实现难度：简单

刚刚那个仅仅只是最简单的优化，效率提升也只有一点点，接下来是算法本质的提升。
我们知道正向冒泡可以每次确定最后一位，那么肯定也能推算出反向冒泡可以每次确定第一位
那正反向冒泡同时进行，就可以同时确定第一位和最后一位，这肯定是有性能提升的，而且这个排序还是有正式名字的：鸡尾酒排序，所以：说干就干！
代码实现：

#include <bits/stdc++.h>
using namespace std;
void CocktailSort(int a[],int n){
    bool flag=true;
    int l=1,r=n;
    for(int i=0;i<n;i++){
        flag=false;
        for(int j=l-1;j<r;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        if(!flag)break;
        r--;
        flag=false;
        for(int j=r-1;j>=l;j--){
            if(a[j]<a[j-1]){
                swap(a[j],a[j-1]);
                flag=true;
            }
        }
        if(!flag)break;
        l++;
    }
}
int main(){
    int a[10]={5,1,9,8,3,6,2,4,7};
    CocktailSort(a,10);
    for(int i:a)cout<<a[i]<<" ";
}