#mp001. 冒泡排序

冒泡排序

冒泡排序

题目描述

​ 给定 n 个整数 xix_i,请使用冒泡排序(Bubble Sort)的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 冒泡排序(Bubble Sort)是一种简单的交换排序算法。它重复地遍历待排序序列,每次比较相邻的两个元素,若它们的顺序错误(即前一个大于后一个)则交换。每轮遍历会将当前未排序部分中的最大元素“冒泡”到序列末尾,因此称为冒泡排序。

算法原理与步骤

  1. 外层循环:共进行 n-1 轮(n 为元素个数),每轮确定一个当前未排序部分的最大值,并将其放置到正确位置。
  2. 内层循环:在第 i 轮(i 从 1 开始),比较范围是前 n-i 个元素(因为最后 i-1 个已经排好),依次比较相邻元素 a[j] 与 a[j+1]。
  3. 比较与交换:若 a[j] > a[j+1],则交换两个元素,将较大值往后移动。
  4. 重复:直到所有轮次结束,序列完全有序。

输入格式

​ 第一行一个正整数 n,表示数字个数。 ​ 第二行 n 个整数,每个数在 int 范围内。

输出格式

​ 一行,输出排序后的 n 个整数,相邻数字用空格隔开。

输入输出样例

5
3 1 2 1 3
1 1 2 3 3

数据规模与约定

​ 1 ≤ n ≤ 5000

​ 数值范围:-10^9 ≤xi x_i ≤ 10^9

​ 时间限制:1 秒(冒泡排序最坏 O(n^2),但 n=5000 时约 2.5×10^7 次比较,配合优化通常可轻松通过)

提示

​ 代码提示:

// 1. 外层循环:共进行 n-1 轮
for (int i = 1; i <= ? ; i++) {
    bool flag = true;   // 标记本轮是否发生交换
    // 2. 内层循环:比较相邻元素,将最大值往后移
    // 每轮结束后,最后 i 个元素已经有序,无需再比较
    for (int j = 1; j <= ?; j++) {
        // TODO: 如果 a[j] > a[j+1],则交换
        // 提示:使用 swap(a[j], a[j+1]),并将 flag 置为 false
    }
    // 若本轮无交换,说明已经有序,提前退出
    if (flag) {
        break;
    }
}

​ 运用提示:

​ 冒泡排序的核心在于相邻比较和交换,每次内层循环都将未排序部分的最大值移到末尾。

​ 代码中使用了 flag 变量进行优化,若某轮无交换则提前结束,减少不必要的循环(尤其对接近有序的数据很有效)。

​ 注意数组下标从 1 开始,边界条件 j <= n - i 保证了不会越界。

​ 数组大小建议设为 n+5。