冒泡排序算法（图文并茂，Java实现）

冒泡排序的基本思想：从第一个元素开始，依次比较两个相邻的元素，若两个元素逆序，则进行交换，即若 L.data[i].key>L.data[i+1].key，则交换 L.data[i] 与 L.data[i+1]。

假设元素序列中有 n 个待比较的元素：

• 在第一趟排序结束后，会将元素序列中关键字最大的元素移到序列的末尾，即第 n 个位置；
• 在第二趟排序结束后，会将关键字次大的元素移动到第 n-1 个位置。

以此类推，经过 n-1 趟排序后，元素序列构成一个有序序列。这样的排序类似于气泡慢慢向上浮动，因此称为冒泡排序。

例如，一组元素序列的关键字为 (56,22,67,32,59,12,89,26,48,37)，对该关键字序列进行冒泡排序，第一趟排序过程如下图所示：


从图 1 可以看出，第一趟排序结束后，关键字最大的元素被移动到序列的末尾。

按照这种方法，冒泡排序的全过程如下图所示。


从图 2 可以看出，在第五趟排序结束后，其实该元素序列已经有序，第六趟和第七趟排序就不需要进行比较了。因此，在设计算法时，可以设置一个标志为 flag，若在某一趟循环中，所有元素已经有序，则令 flag=true，表示该序列已经有序，不需要再进行后面的比较了。

冒泡排序的算法实现如下：

public void BubbleSort(int n)
// 冒泡排序
{
    boolean flag = true;
    for (int i = 0; i < n - 1; i++) {
        if (flag)  // 需要进行 n-1 趟排序
        {
            flag = false;
            for (int j = 0; j < length - i - 1; j++) // 每一趟排序需要比较 n-i 次
            {
                if (data[j] > data[j + 1]) {
                    int t = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = t;
                    flag = true;
                }
            }
            DisplList2(count);
            count++;
        }
    }
}

可以发现，冒泡排序的空间复杂度为 O(1)。在进行冒泡排序的过程中，假设待排序的元素序列为 n 个，则需要进行 n-1 趟排序，每一趟需要进行 n-i 次比较，其中 i=1,2,…,n-1。因此，整个冒泡排序过程需要比较的次数为：


移动次数为：


冒泡排序的时间复杂度为 O(n^2)。冒泡排序是一种稳定的排序算法。