冒泡排序是我们最容易写出来的排序算法，就算没有学过算法，也能自己轻松写出来如下排序代码：

void bubbleSort0 (int arr[], int len) 
{
    int i, j, temp;
    for (i = 0; i < len; i++) {
        for (j = i + 1; j < len; j++) {
            if (arr[i] > arr[j]) { 
                // 用当前待排序索引和剩余所有未排序位进行比较 如果大于当前字符，就交互。
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

上边的代码，基本思想是，从数组第一个元素开始，拿出该元素和剩余所有元素比较，只要当前元素大于剩余元素中的任何一个，就互换位置；这样一轮排序下来，就能找出当前所有待排序元素的最小元素，直到最后一个元素。

上述代码虽然实现了排序，但严格来讲，不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”。冒泡排序的基本思想是：两两比较相邻记录关键字，如果反序则交互，直到没有反序记录为止。 下面来看看比较正宗的冒泡排序算法：

void bubbleSort1 (int arr[], int len) 
{

    int i, j, temp;

    for (i = 0; i < len; i++) {
        for (j = len - 1; j > i; j--) { // 从后往前循环
            if (arr[j - 1] > arr[j]) { 
                // 这里比较是 j - 1 和 j 相邻的两个元素，和上边代码中比较 i 和 j 是有区别的。
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

这次的代码依然是两两比较，但是是从后往前两两进行比较。每一轮比较结束后，除了将最小元素找出，还能将较小的数字提升到比较靠前的位置，显然这种写法是有进步的。较小的数字如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法。

冒泡排序优化

假设有一待排序的序列是 {2, 1, 3, 4, 5, 6}，那么用上述冒泡排序算法，只需要一轮交换，就得到了正常的序列。但是算法依然会不依不饶的从 i = 2 循环到 6，但每次都是无效循环。代码改进的关键是增加一个 flag ，来记录每轮排序后，是否已经得到了正常的序列：

void bubbleSort1 (int arr[], int len) 
{
    int i, j, temp;
    _Bool flag = TRUE;

    for (i = 0; i < len && flag; i++) { // 循环条件改为 i < len && flag 
        flag = FALSE; // 假设已经排好序
        for (j = len - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = FALSE; // 还需要交互，无法判断是否已经排好序，进行下一轮排序
            }
        }
    }
}

上述代码增加一个 bool 型的 flag，就可以避免因已经排好序的情况下的无意义的循环判断。

复杂度分析

我们用改进后的代码来分析算法的时间复杂度；当情况是最好的，也就是序列本身已经有序了，那么代码只需要执行 n – 1 次比较操作，不需要进行数据交换，时间复杂度为 O(n)。

最坏的情况，待排序的序列是逆序，那么依次需要比较 (n – 1) + (n -2) + …+ 3 + 2 + 1 = $\frac{n(n-1)}{2}$ 次，并做等量的数据交换，总的时间复杂度为 O($n^2$ )。

(完)