难度：进阶。题目原型为 AOJ ALDS1_2_C Stable Sort。本题考察排序的稳定性：冒泡排序稳定，选择排序不稳定，并把两者对同一输入的排序结果并列输出。

目标

完成本题后，你应该能够：

• 解释「稳定排序」的含义：关键字相同的元素，排序后相对顺序不变；
• 用结构体表示「花色 + 数字」的牌，并按数字这一关键字排序；
• 对比冒泡排序与选择排序的输出，判断选择排序在给定输入下是否稳定。

前置知识

• 10.2 选择排序、10.3 冒泡排序的实现；
• 结构体、字符与整数。

题目

读入 n 和 n 张牌，每张牌由一个花色（S、H、C、D 之一）和一个数字（1..9）组成。分别用冒泡排序和选择排序按数字从小到大排序，并输出：

1. 冒泡排序的结果（一行），下一行输出 Stable；
2. 选择排序的结果（一行），下一行输出 Stable 或 Not stable（取决于该输入下选择排序是否稳定）。

输入格式

• 第一行一个整数 n；
• 第二行 n 个「花色 + 数字」的牌，空格分隔，例如 H4 C9 S4 D2 C3。

输出格式

共 4 行：

• 第 1 行：冒泡排序结果（空格分隔）；
• 第 2 行：Stable；
• 第 3 行：选择排序结果（空格分隔）；
• 第 4 行：Stable 或 Not stable。

数据范围

项目	范围
牌数 n	1 ≤ n ≤ 36
花色	S / H / C / D
数字	1..9

样例

样例输入

5
H4 C9 S4 D2 C3

样例输出

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

样例解释

两张数字为 4 的牌 H4、S4 原本顺序是 H4 在前。冒泡排序保持了这个顺序（H4 S4），所以稳定；选择排序把它们交换成了 S4 H4，所以不稳定。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-08-stable-sort-check
pnpm lab:score -- labs/chapter-10/exercise/E-10-08-stable-sort-check

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 数字全不同（必稳定）、含相同数字（可能不稳定）两类输入都通过
• 能说出冒泡排序为什么一定稳定、选择排序为什么不保证稳定

思考题

1. 选择排序在什么情况下是稳定的？能不能举出一个「含相同数字但选择排序仍然稳定」的例子？
2. 如果判断稳定性的方法改成「比较选择排序与冒泡排序结果是否一致」，为什么是可行的？

题解

点击查看题解

思路

用结构体 Card { char suit; int value; } 保存每张牌，排序时只比较 value。

• 冒泡排序只在 value 严格更小时交换相邻元素，相等的元素不会跨越彼此，所以稳定。
• 选择排序每轮把最小值「跳」到当前位置，可能跨越关键字相同的元素，所以不稳定。

判断选择排序是否稳定的简洁办法：冒泡排序的结果就是唯一的稳定结果，把选择排序的结果与它逐张比较，完全相同则稳定，否则不稳定。

复杂度分析

• 时间复杂度：两种排序都是 O(n²)；
• 空间复杂度：O(n)（保存两份待排序的牌）。