算法思想

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动画演示：

实现

C++

void bubbleSort(vector<int> &array)
{
    int len = array.size();

    for (int i = len - 1; i>0; i--)
        for (int j = 0; j<i; j++)
            if (array[j] > array[j + 1])
                swap(array[j], array[j + 1]);
}

python

def BubbleSort(alist):
    leng = len(alist)
    #需要循环的次数：n-1
    for index in range(leng-1,0,-1):
        # 每次循环将当前的最大值放在合适的位置上
        for i in range(index):
            if alist[i] >  alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]

总结

稳定性：
在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

适用场景：
冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。
算法在数据基本有序的情况下，性能最好。

复杂度：
在数据完全有序的时候展现出最优时间复杂度为\(O(n)\)。其他情况下，几乎总是\(O\left(n^{2}\right)\)。

优化

增加一个的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出：

C++

void shortBubbleSort(vector<int> &array)
{
    bool exchanges = true;
    int len = array.size();

    for (int i = len - 1; i>0 && exchanges; i--)
    {
        exchanges = false;
        for (int j = 0; j<i; j++)
        if (array[j] > array[j + 1])
        {
            swap(array[j], array[j + 1]);
            exchanges = true;
        }
    }
}

python

def shortBubbleSort(alist):
    exchanges = True
    passnum = len(alist) - 1

    while passnum  > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                exchanges = True
                alist[i],alist[i+1] = alist[i+1],alist[i]
        passnum -= 1

冒泡排序

原文：https://www.cnblogs.com/chay/p/10672830.html