冒泡排序

时间复杂度

O(n^2)

如果是优化版的冒泡排序：最好的时间复杂度为O(n)，即已经有序的情况下。

C++代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n,q[N];

void bubble_sort()
{
    for(int i = 0 ; i < n ; i ++)
    {
        for(int j = n-1; j > i ; j--)
        {
            if(q[j] < q[j-1]) swap(q[j],q[j-1]);
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0 ; i < n;i++) cin >> q[i]; //读取

    bubble_sort();

    for(int i = 0 ; i < n;i++) cout <<  q[i] <<' ';

    return 0;
}

冒泡排序优化思路：

对于第二层循环的任何一趟排序，如果某一趟排序没有发生置换，就证明之后的序列都是已经有序的了，
而由于冒泡排序的特性，这一趟排序前的那几位也是已经拍好序的了，因此整个序列已经有序，所以可以直接中断排序
时间复杂度： O(n^2)
最好的时间复杂度情况：O(n)

void better_bubbleSort(){
    for(int i = 0 ; i < n; i ++){

        bool flag = false;  // 有无置换过的标志
        for(int j = n-1; j > i; j --){
            if(q[j] < q[j-1]){
                swap(q[j],q[j-1]);
                flag = true;
            }
        }
        if(!flag) break;
    }
}