冒泡排序

冒泡排序（bubble sort）又称起泡排序。它主要基于以下观察：

• 有序序列中，任意一对相邻元素顺序
• 无序序列中，总有一对相邻元素逆序

为此，要执行扫描交换，即依次比较每一对相邻元素，如有必要，交换之；若整趟扫描都没有进行交换，则排序完成；否则，再做一趟扫描交换。

Python 实现：

C 实现：

void bubblesort(int A[], int n)
{
    for(bool sorted = false; sorted = !sorted; n--)  // 逐趟扫描交换，直至完全有序
    {
        for(int i = 1; i < n; i++)  // 自左向右，逐对检查A[0, n)内各相邻元素
        {
            if(A[i-1] > A[i])  // 若逆序，则
            {
                swap(A[i-1], A[i]);  // 令其互换，同时
                sorted = false;  // 清除（全局）有序标志
            }
        }
    }
}

冒泡排序是稳定的排序，这是因为，在冒泡排序中，元素 a 和 b 的相对位置发生变化，只有一种可能：经分别与其他元素的交换，二者相互接近直至相邻，在接下来一轮扫描交换中，二者因逆序而交换位置。