冒泡排序

本文将用图例介绍冒泡排序的过程，和经典的优化板子

算法思想

从后往前（或从前往后），两两比较相邻元素的值，若为逆序（q[i - 1] > q[i]），则交换它们，直到序列比较完。

一个简单的例子：

算法特性

时间复杂度：

最好情况：O(n)
平均情况：O(n²)
最坏情况：O(n²)

空间复杂度：O(1)

稳定性：稳定

算法模板

void bubble_sort(){
    // n个元素，比 n - 1 趟
    for(int i = 0 ; i < n - 1 ; i++){
        // 优化，这样可以当元素有序时，一趟就退出
        // 有没有交换过
        bool has_swap = false;
        // 从后往前枚举，由于比较的是相邻元素，j到 i + 1 就行
        for(int j = n - 1 ; j > i ; j--){
            // 逆序
            if(q[j - 1] > q[j]){
                swap(q[j - 1], q[j]);
                has_swap = true;
            }
        }
        // 如果没有交换过，代表整个序列在第一趟检测出有序，直接退出排序
        if(!has_swap) break;
    }
}