C语言排序——冒泡排序

原理

通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端。

设数组的长度为 𝑛 ：

首先，对 𝑛 个元素执行“冒泡”，将数组的最大元素交换至正确位置，
接下来，对剩余 𝑛 − 1 个元素执行“冒泡”，将第二大元素交换至正确位置。
以此类推，经过 𝑛 − 1 轮“冒泡”后，前 𝑛 − 1 大的元素都被交换至正确位置。
仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。

示例

“4 1 3 1 5 2”

第一轮：

比较第一个元素“4”和第二个元素“1”，因为 4>1，所以交换它们的位置，序列变为“1 4 3 1 5 2”。
接着比较第二个元素“4”和第三个元素“3”，4>3，交换位置，序列变为“1 3 4 1 5 2”。
再比较第三个元素“4”和第四个元素“1”，4>1，交换位置，序列变为“1 3 1 4 5 2”。
继续比较第四个元素“4”和第五个元素“5”，4<5，不交换。
最后比较第五个元素“5”和第六个元素“2”，5>2，交换位置，序列变为“1 3 1 4 2 5”。

第二轮：

比较第一个元素“1”和第二个元素“3”，1<3，不交换。
比较第二个元素“3”和第三个元素“1”，3>1，交换位置，序列变为“1 1 3 4 2 5”。
比较第三个元素“3”和第四个元素“4”，3<4，不交换。
比较第四个元素“4”和第五个元素“2”，4>2，交换位置，序列变为“1 1 3 2 4 5”。

第三轮：

比较第一个元素“1”和第二个元素“1”，不交换。
比较第二个元素“1”和第三个元素“3”，1<3，不交换。
比较第三个元素“3”和第四个元素“2”，3>2，交换位置，序列变为“1 1 2 3 4 5”。

第四轮：

比较第一个元素“1”和第二个元素“1”，不交换。
比较第二个元素“1”和第三个元素“2”，1<2，不交换。
比较第三个元素“2”和第四个元素“3”，2<3，不交换。

第五轮：

比较第一个元素“1”和第二个元素“1”，不交换。
比较第二个元素“1”和第三个元素“2”，1<2，不交换。

序列为“1 1 2 3 4 5”。

代码（C）

/* 冒泡排序 */
void bubbleSort(int nums[], int size) {
    // 外循环：未排序区间为 [0, i]
    for (int i = 0; i < size - 1; i++) {
        // 外循环控制排序的轮数。每一轮会将当前未排序区间中的最大元素“冒泡”到未排序区间的最右端，
        // 所以每一轮结束后，未排序区间的范围会缩小。
        // 当 i = 0 时，未排序区间为整个数组 [0, size - 1]；当 i = 1 时，未排序区间变为 [0, size - 2]，以此类推。
        // 总共需要进行 size - 1 轮循环，因为当进行到第 size - 1 轮时，最后一个元素已经在正确的位置上了。

        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < size - 1 - i; j++) {
            // 内循环在每一轮中遍历未排序区间，比较相邻的元素，如果前一个元素大于后一个元素，就交换它们的位置。
            // 通过不断地比较和交换，每一轮都会将未排序区间中的最大元素移动到未排序区间的最右端。
            // j < size - 1 - i 的原因是，随着外循环的进行，每一轮结束后，未排序区间的范围会缩小，
            // 已经排好序的元素不需要再参与比较和交换。

            if (nums[j] > nums[j + 1]) {
                // 如果当前元素大于下一个元素，则进行交换。
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

复杂度

时间复杂度：最差情况为 $O(n^2)$

空间复杂度：为 $O(1)$

效率优化版冒泡

如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。

/* 冒泡排序（标志优化） */
void bubbleSortWithFlag(int nums[], int size) {
    // 外循环：未排序区间为 [0, i]
    for (int i = 0; i < size - 1; i++) {
        bool flag = false;
        // flag 标志变量用于判断在本轮内循环中是否发生了交换。初始化为 false，表示假定本轮没有交换发生。

        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < size - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                flag = true;
                // 如果当前元素大于下一个元素，则进行交换，并将 flag 设置为 true，表示发生了交换。
            }
        }

        if (!flag)
            break;
        // 如果在本轮内循环中没有发生交换（即 flag 为 false），说明数组已经有序，直接退出外循环。
    }
}