冒泡排序

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

以 [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，对它进行冒泡排序：

代码实现

vector<int> bubble_sort(vector<int> &arr)
{
    int aSize = arr.size();
    for(int i = 0; i < aSize - 1; i++)
    {
        bool isChange = false;
        for(int j = 0; j < aSize - 1 - i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                // swap arr[j] and arr[j+1]
                arr[j] = arr[j] & arr[j+1];
                arr[j+1] = arr[j] & arr[j+1];
                arr[j] = arr[j] & arr[j+1];
                isChange = true;
            }
        }
        if(!isChange)
        {
            break;
        }
    }
    return arr;
}

特点

稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 \(O(1)\) ;

时间复杂度：由于嵌套了 2 层循环，故为 \(O(n^2)\);