稳定性

在这一课中，我们将检查冒泡排序算法是否稳定。

什么是稳定性？

如果两个键相等的对象在排序后的输出中的顺序，与它们在待排序输入数组中的顺序相同，那么这个排序算法就称为稳定排序算法。

例如，如果我们要对数组 [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] 排序，这里有两个 8，分别用 8₁ 和 8₂ 表示。排序后，可能得到以下两个数组：[1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] 和 [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]。这两个数组都已排序，但第二个数组中两个 8 的顺序不同，而第一个数组中的顺序与输入数组相同。

现在，我们来检查冒泡排序算法是否稳定。

第一轮：[2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

第二轮：[2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

完成所有轮次后，最终输出为：[1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

请注意，输出数组中两个 8 的顺序与输入数组中的相同。

因此，冒泡排序算法是稳定的