冒泡排序

算法思想

它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名冒泡排序。

详细解释

每一轮从数组的开头找第一个数字作为基本数字，然后向后依次比较，如果比这个数字小，就将小的数向前一个位置挪，然后再和再下一个数比较
如果再下一个数字比这个数字大，但是还没有到数组的最末尾，就将这个数字放到当前位置，然后将这个大一点的数字作为基本数字再向后排序
直到找到了最后，这个时候最大的数字就移动到了最后
每一轮都是将第一个数字作为基本数字排序，只是要将遍历的末尾向前移动
当然，上面是先将大的数字放到末尾，同样也可以反向操作，将最小的数字放到前面，这样操作就和选择排序的思路一致了
在这种情况下，冒泡排序和选择排序的区别就是，选择排序是改变当前元素的位置到目标位置上去，其他位置的元素不移动，只是将最小元素和目标位置的元素交换
但是冒泡排序不仅会移动到目标位置，也会顺便将中间的元素移动位置(如果一开始选中的元素为第二小的元素，那在最小元素移动到位置上时，
它基本上也到了或者快到了它的目标位置了)
很明显，冒泡排序像是选择排序的一个升级版它的时间复杂度会比选择排序好

时空间复杂度

最坏情况的时间复杂度和选这排序相等为 $O(n^2)$（和顺序刚好相反）
最好情况的时间复杂度为 $O(n)$（本来就是有序的）（但要用加快算法）
==总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。==

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

冒泡排序就是把小的元素往前调或者把大的元素往后调。是相邻的两个元素的比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

优化

对冒泡排序常见的改进方法是加入标志性变量isswap，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。

源代码

未优化源代码

#include <iostream>
#include <vector>
 
using namespace std;

void swap(int &a, int &b) //交换值
{
    int tmp = a;
    a = b;
    b = tmp;
}

vector<int> bubbleSort(vector<int> list){
    vector<int> result;
    if (list.empty()){
        return result;
    }
 
    result = list;
    int temp;
    // 要遍历的次数
    for (int i = 0; i < result.size() - 1; ++i){
        // 从后向前依次的比较相邻两个数的大小
        for (int j = 0; j < result.size() - 1; j++){
            // 如果后面的元素小，则交换它们的位置
            if (result[j + 1] < result[j]){
                swap(result[j],result[j+1])
            }
        }
    }
    return result;
}

int main(){
    int arr[] = { 6, 4, 8, 1, 2, 3, 9 };
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前" << endl;
    for (int i = 0; i < test.size(); i++){
        cout << test[i] << " ";
    }
    cout << endl;
    vector<int> result;
    result = bubbleSort(test);
    cout << "排序后" << endl;
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
}

优化后源文件

#include <iostream>
#include <vector>
 
using namespace std;

void swap(int &a, int &b) //交换值
{
    int tmp = a;
    a = b;
    b = tmp;
}
void bubblesort()冒泡排序入口
{
    int a[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3}; //待排序数组

    int size = sizeof(a) / sizeof(int);
    bool isswap = false;           //使用加快，如果这一次没有交换，说明这个位置前面的数是已经拍好序了的，所以不需要再继续到前面的位置再寻找了
    for (int i = size; i > 1; i--) //从最后一个位置开始找
    {
        for (int j = 1; j < i; j++)
        {
            if (a[j - 1] > a[j])
            {
                swap(a[j - 1], a[j]);
                isswap = true;
            }
        }
        if (!isswap)
            break;
    }
    for (int i = 0; i < size; i++)
        cout << a[i] << " ";
}
int main()
{
    bubblesort();//调用冒泡排序
}