冒泡排序

冒泡排序是大多数人第一个学习的算法。因为最大值会像泡泡一样冒到数组的末尾而得名。

思路

算法思路也很简单，我们以升序为例，每次比较前后两值的大小，如果不满足 \(a[i - 1] \le a[i]\) 就，互换位置，这样在一轮遍历后，最大值就会被移动到数组末尾。这样我们循环 \(n - 1\) 遍，数组就会变得有序。

优化

我们发现其实每次循环可将一个值放到数组的末尾，所以每次循环不必遍历整个数组，而是 \(n - i\) ，\(i\) 是已经循环的次数。而且如果在一次循环中，没有元素需要交换，那么就说明整个数组已经有序了，结束算法即可。

void Bubble_Sort(vector<int>& a)
{
    int n = a.size();
    for(int i = 0;i < n - 1;++i)
    {
        bool is_ordered = true;
        for(int j = 1;j < n - i;++j)
        {
            if(a[j - 1] > a[j])
            {
                swap(a[j - 1],a[j]);
                is_ordered = false;
            }
        }
        if(is_ordered) break;
    }
}

性能

稳定性

冒泡排序不会交换值相同元素的位置，所以是稳定的排序。

时间复杂度

最坏情况下，数组中每两个元素都要交换一次，就是 \(\frac{n(n - 1)}{2}\) 次交换，所以复杂度为 \(O(n^2)\)。

空间复杂度

只有常数个变量，所以空间复杂度是 \(O(1)\)。