冒泡排序变体：三相邻元素交换问题（Code Jam 2018资格赛第2题）

变体三元反转排序的核心分析（Google Code Jam 2018资格赛题） #

咱们先拆解这个问题里的核心操作：遍历数组时，对每一组三个相邻元素[a, b, c]，如果a > c，就把这组反转成[c, b, a]。下面从几个关键维度分析：

这个算法的局限性很明显——它只能处理那些元素初始位置奇偶性和有序数组中位置奇偶性一致的数组。原因在于：

• 每次反转操作只会交换最左和最右的元素（中间元素b位置不变），这两个元素的位置差是2，所以它们的位置奇偶性（奇数/偶数）不会改变。
• 换句话说，初始在偶数位置的元素，永远只能移动到其他偶数位置；奇数位置的元素同理。

举个直观的反例：数组[2, 3, 1]，它的有序状态是[1, 2, 3]。其中元素2初始在位置0（偶数），但有序位置是1（奇数）——奇偶性不匹配，所以这个算法永远无法把2放到正确位置。实际运行时：

• 第一轮检查整个数组，2 > 1，反转得到[1, 3, 2]
• 之后再没有能触发反转的三元组（1 < 2），数组停在[1, 3, 2]，无法完成排序。

如果数组满足奇偶性条件，那这个算法是可以完成排序的。比如逆序数组[5,4,3,2,1]，所有元素的初始位置和有序位置奇偶性一致，经过两轮遍历就能排好序。

虽然这个变体的元素移动效率比标准冒泡排序高（每次操作能让元素跳2个位置），但最坏情况下的时间复杂度依然是平方级的：

• 每一轮遍历数组的时间是O(n)，因为需要检查n-2组三元元素。
• 最坏情况下，需要O(n)轮遍历。比如逆序且奇偶性匹配的数组，最大的元素需要从位置0移动到位置n-1（假设n为奇数），每轮最多移动2个位置，需要(n-1)/2轮；而较小的元素也需要类似的移动次数，整体轮数还是线性的。

对比标准冒泡排序：冒泡排序每轮元素最多移动1个位置，需要O(n)轮，总时间也是O(n²)。这个变体在某些场景下会更快，但渐近复杂度和冒泡排序一致。

• 稳定性：这个算法是稳定的。因为只有当arr[i] > arr[i+2]时才会触发反转，相等元素不会触发操作，所以相等元素的相对位置不会被改变。
• 置换性质：每次反转操作等价于交换位置差为2的两个元素，中间元素保持不动。这个算法能生成的置换群，仅包含那些不改变元素位置奇偶性的置换——这也是排序能力受限的根本原因。

内容的提问来源于stack exchange，提问作者hsnsd