C / C++ / 系统课时

用冒泡排序调整数组顺序

用冒泡排序调整数组顺序

冒泡排序通过反复比较相邻元素并在顺序错误时交换它们,让较大的值逐轮移动到数组右侧。本节用升序排序程序拆解循环边界、交换条件和提前结束优化,并说明这种算法适合什么规模的数据。

学习目标

  • 能解释一轮冒泡后为什么会有一个元素到达最终位置
  • 能写出正确的双层循环和相邻元素交换逻辑
  • 能分析冒泡排序的时间复杂度、稳定性和适用边界

冒泡排序如何推进

以 {5, 2, 4, 1} 为例,第一轮从左到右比较相邻元素。5 与 2 顺序错误就交换,之后继续让 5 与右侧元素比较。第一轮结束时,当前最大值 5 已经移动到最右端,不必在下一轮再次参与比较。

冒泡排序每一轮把较大元素推向右侧

因此,第 i 轮结束后,右侧已经至少有 i + 1 个元素处于最终位置。内层循环可以逐轮缩短,而不是每次都扫描到数组末尾。

编写完整排序程序

下面的实现按升序排序,并增加 swapped 标记。如果某一整轮没有发生任何交换,说明数组已经有序,可以提前结束。

c
#include <stdio.h>

void bubble_sort(int values[], int length) {
    for (int i = 0; i < length - 1; ++i) {
        int swapped = 0;

        for (int j = 0; j < length - 1 - i; ++j) {
            if (values[j] > values[j + 1]) {
                int temp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = temp;
                swapped = 1;
            }
        }

        if (!swapped) {
            break;  // 本轮无交换,说明剩余部分也已经有序
        }
    }
}

int main(void) {
    int numbers[] = {5, 2, 4, 1};
    int length = (int)(sizeof(numbers) / sizeof(numbers[0]));

    bubble_sort(numbers, length);

    for (int i = 0; i < length; ++i) {
        printf("%d%s", numbers[i], i == length - 1 ? "\n" : " ");
    }

    return 0;
}

预期输出

text
1 2 4 5

交换条件使用 values[j] > values[j + 1]。只有左侧元素更大时才交换;相等元素不会互换,因此这个版本保持相等元素的原有相对顺序。

理解两层循环的边界

外层最多执行 length - 1 轮,因为当其余元素都已经放到正确位置后,最后一个元素自然也确定。内层条件是 j < length - 1 - i,其中 -1 用来保证 j + 1 不越界,-i 用来跳过右侧已经排好的区域。

如果把内层误写成 j < length,表达式 values[j + 1] 会在最后一次迭代访问数组边界之外的内存。这类错误在 C 中未必立刻报错,因此循环上界必须根据实际访问的最大索引推导,而不是凭感觉填写。

复杂度与使用边界

普通冒泡排序的平均和最坏时间复杂度都是 O(n2)O(n^2),因为需要进行多轮相邻比较;交换只使用一个临时变量,所以额外空间复杂度是 O(1)O(1)。加入 swapped 后,已经有序的数组只需扫描一轮,最好情况可降到 O(n)O(n)。

冒泡排序的优势是逻辑直观、易于观察交换过程,适合学习循环、数组索引和排序基本思想。面对较大数据时,它通常不是合适的通用排序方案;实际项目更常使用标准库或复杂度更优的排序算法。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用冒泡排序调整数组顺序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通