昨天面一个小厂，让在自己的ide里写冒泡排序。
太久没写过冒泡排序了，大脑宕机写成了选择排序😅，还加了不正确的优化，和面试官俩人一起找了很久bug……闹出很多乌龙
没想到我也变成了别人口中写不出冒泡排序的人😅

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int q[N]{2,1,3,5,4};
int n;

void selection_sort(int l, int r)
{
    for (int i = l; i <= r; i ++ )
    {
//        选择排序这种优化是错的！每次把最小的数放到i这个位置，必须枚举到最后，不能中途退出
//        bool flag = false;
        for (int j = i + 1; j <= r; j ++ )
        {
            if (q[i] > q[j])
            {
                swap(q[i], q[j]);
//              flag = true;
            }
        }
//        if (!flag) break;
    }
}

void bubble_sort(int l, int r) {
    for (int i = r; i > l; i -- ) {
        bool flag = false;
        for (int j = l; j + 1 <= i; j ++ )
            if (q[j] > q[j + 1]) {
                swap(q[j], q[j + 1]);
                flag = true;
            }
        if (!flag) break;
    }
}

void insert_sort() {
    for (int i = 1; i < n; i ++ ) {
        int t = q[i], j;
        for (j = i - 1; j >= 0; j -- )
            if (q[j] > t) {
                q[j + 1] = q[j];
            } else break;
        q[j + 1] = t;
    }
}

int main()
{
    cin >> n;

    bubble_sort(0, n - 1);
//    selection_sort(0, n - 1);
//    insert_sort();
    for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';

    return 0;
}