冒泡排序

掌握排序算法中的冒泡排序的算法思想、排序步骤及代码实现。

冒泡排序重复扫描相邻元素：若前者大于后者就交换，每轮把当前最大值「冒」到末尾。外层控制轮数，内层比较 a[j] 与 a[j+1]。可设标志位，某一轮无交换则已有序，提前结束。

GESP 四级可能考：一轮后数组形态、比较/交换次数估算、是否稳定、最坏时间 O(n²)。手 trace 小规模数组（n=4 或 5）比背代码更可靠；编程题若要求写冒泡，注意循环边界 j < n-1-i。

void bubble(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool done = true;
        for (int j = 0; j < n - 1 - i; ++j)
            if (a[j] > a[j+1]) { swap(a[j], a[j+1]); done = false; }
        if (done) break;
    }
}

理解「相邻交换、大元素右移」这一图像，就能推出大部分考题答案。

冒泡排序的第一轮操作是从左到右遍历数组，通过两两比较相邻元素，将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2}，执行第一轮冒泡排序后数组 arr 中的内容为（）。

1, 4, 3, 1, 5, 2

1, 3, 1, 4, 2, 5

1, 4, 3, 1, 2, 5

4, 1, 3, 1, 5, 2

冒泡排序的平均时间复杂度为 $O(n^2)$ ，但最优情况下为 $O(n)$ 。

√（正确）

×（错误）

编程题

字符排序

C++时间 1 s内存 512 MB标准输入输出

小杨有 $n$ 个仅包含小写字母的字符串 $s_1,s_2,\ldots,s_n$ ，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 $t$ 。小杨希望最后构成的字符串 $t$ 满足：

假设 $t_i$ 为字符串 $t$ 的第 $i$ 个字符，对于所有的 $j\lt i$ 均有 $t_j\le t_i$ 。两个字符的大小关系与其在字母表中的顺序一致，例如 $\texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s}$ 。

小杨想知道是否存在满足条件的字符串排列顺序。

输入格式

第一行包含一个正整数 $T$ ，代表测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$ ，含义如题面所示。

之后 $n$ 行，每行包含一个字符串 $s_i$ 。

输出格式

对于每组测试数据，如果存在满足条件的排列顺序，输出（一行一个） $\texttt{1}$ ，否则输出（一行一个） $\texttt{0}$ 。

样例

输入 1

3
3
aa
ac
de
2
aac
bc
1
gesp

输出 1

1
0
0

样例解释

对于第一组测试数据，一种可行的排列顺序为 $\texttt{aa}+\texttt{ac}+\texttt{de}$ ，构成的字符串 $t$ 为 $\texttt{aaacde}$ ，满足条件。

数据范围

对于全部数据，保证有 $1\le T,n\le 100$ ，每个字符串的长度不超过 $10$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

对数组 arr[]={5, 3, 8, 1} 进行升序排序，执行第一轮冒泡排序后数组 arr 中的内容为（）。

3, 5, 1, 8

3, 1, 5, 8

3, 5, 8, 1

5, 3, 8, 1

为了提高冒泡排序的效率，如果某轮「冒泡」中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果，则两条横线上分别应该填写（）。

void bubbleSortWithFlag(vector<int> &nums) {
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag;
        ____________________ // 在此处填入代码

        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                ____________________ // 在此处填入代码
            }
        }
        if (!flag)
            break;
    }
}

flag = false;
flag = false;

flag = false;
flag = true;

flag = true;
flag = false;

flag = true;
flag = true;

编程题

排序

C++时间 1 s内存 512 MB标准输入输出

体育课上有 $n$ 名同学排成一队，从前往后数第 $i$ 位同学的身高为 $h_i$ ，体重为 $w_i$ 。目前排成的队伍看起来参差不齐，老师希望同学们能按照身高从高到低的顺序排队，如果身高相同则按照体重从重到轻排序。在调整队伍时，每次只能交换相邻两位同学的位置。老师想知道，最少需要多少次交换操作，才能将队伍调整成目标顺序。

输入格式

第一行，一个正整数 $n$ ，表示队伍人数。

接下来 $n$ 行，每行两个正整数 $h_i$ 和 $w_i$ ，分别表示第 $i$ 位同学的身高和体重。

输出格式

输出一行，一个整数，表示最少需要的交换次数。

样例

输入 1

输出 1

输入 2

输出 2

数据范围

对于所有测试点，保证 $1 \leq n \leq 3000$ ， $0 \leq h_i, w_i \leq 10^9$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

对整数数组 $\{4, 1, 3, 1, 5, 2\}$ 进行冒泡排序（将最大元素放到最后），执行一轮之后是 $\{4, 1, 3, 1, 2, 5\}$ 。

√（正确）

×（错误）

如果使用带 flag 的冒泡排序，且待排序数组一开始就是有序的，那么算法只需一轮扫描即可结束，时间复杂度为 $O(n)$ 。

√（正确）

×（错误）

编程题

身高体重指数

C++时间 1 s内存 512 MB标准输入输出

一个人的身高体重指数（BMI）等于其体重（千克为单位）除以其身高（米为单位）的平方。

例如，一个体重为 $50\text{ kg}$ ，身高为 $1.6\text{ m}$ 的人的身高体重指数为 $50\text{ kg}/1.6\text{ m}/1.6\text{ m} = 19.53125\text{ kg/m}^2$ 。

现在有 $n$ 个小朋友，第 $i$ 个小朋友的编号为 $i$ ，体重为 $w_i$ ，身高为 $h_i$ 。

请按照身高体重指数从高到低为小朋友们排序，数据保证不存在两个小朋友的身高体重指数完全相同。输出排序后小朋友的编号。

输入格式

输入 $3$ 行，

第一行为一个正整数 $n$ ，表示小朋友的个数；

第二行为 $n$ 个整数 $w_1, w_2, \cdots, w_n$ 表示小朋友们的体重，单位为 $\text{kg}$ ；

第三行为 $n$ 个浮点数 $h_1, h_2, \cdots, h_n$ 表示小朋友们的身高，单位为 $\text{m}$ 。

输出格式

输出一行 $n$ 个数，表示按照身高体重指数从高到低排序后的编号。

样例

输入 1

3
45 33 39
1.55 1.33 1.44

输出 1

3 1 2

三个小朋友（编号依次为 $1$ ， $2$ ， $3$ ）的身高体重指数分别为（保留两位小数的结果）： $18.73$ ， $18.66$ ， $18.81$ ，故排序后输出的编号为 $3\ 1\ 2$ 。

数据范围

$1 \le n \le 1000$ ， $10 \le w_i \le 100$ ， $0.8 \le h_i \le 1.9$ ， $h_i$ 均恰有两位小数。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB