c - 对整数圆形数组进行排序，交换元素之间的元素为 1

Question

给定一个整数循环数组 v，其中 n > 0 个数字，并且只有一个可能的移动“m”是将一个元素与前面 2 后面的元素交换。
我必须打印一系列对 v 进行排序的 Action ，或者说这是不可能的(用 c 语言)

示例:
初始值:v = [8, 0, 5, 9, -1, 5]
将 m 应用于 v[4] 后: v = [-1, 0, 5, 9, 8, 5]
将 m 应用于 v[3] 后:v = [-1, 0, 5, 5, 8, 9]
现在从 0 位置开始排序。输出将为“4 3”

到目前为止我所知道的:
- 如果元素数量为奇数，则可以将任意元素移动到任意位置。 (但这足以保证可以排序吗？)
- 对于偶数个元素，并不总是可以对其进行排序，因为您无法在奇数位置和偶数位置之间移动元素(例如:v = [-1, -2, 1, 7]，不可能，因为 -2 in是奇数位置，但应该是偶数位置)。

我一直在思考这个问题:
- 使用辅助数组“aux”将数字与其真实的邻居放在一起，例如:
v = [8, 0, 5, 9, -1, 5, 6] -> aux = [8, 5, -1, 6, 0, 9, 5]
现在在 aux 中我可以与相邻数字执行简单的交换。
- aux 中位置“i”的最终配置是:
v = [8, 0, 5, 9, -1, 5, 6] -> aux = [8, 5, -1, 6, 0, 9, 5] -> i = [0, 2, 4, 6 , 1, 3, 5]
- 如果n是偶数，就会有2个aux，因为要对v进行排序，你不能在奇数和偶数位置之间移动数字，所以有2个子问题。例如:
v = [8, 0, 5, 9, -1, 5]
aux-偶数 = [8, 5, -1] -> i-偶数 = [0, 2, 4]
aux-odd = [0, 9, 5] -> i-even = [1, 3, 5](用 v 来思考)

我不确定从这里该去哪里，或者这是否是一条很好的运行路径。

欢迎任何想法或帮助。

编辑

我正在尝试模拟 AlexD 针对奇怪情况提出的算法:
v = [8, 0, 5, 9, -1, 5, 6]
v 排序 = [-1, 0, 5, 5, 6, 8, 9]

为它们分配键 (-1, 1), (0, 5), (5, 2), (5, 6 ), (6, 3), (8, 7), (9, 4)。

回到原来的顺序:
(8, 7) (0, 5) (5, 2) (9, 4) (-1, 1) (5, 6) (6, 3)

对中间有 1 的键使用冒泡排序。
(8, 7) (0, 5) (5, 2) (9, 4) (-1, 1) (5, 6) (6, 3)
(5, 2) (0, 5) (8, 7) (9, 4) (-1, 1) (5, 6) (6, 3)
(5, 2) (0, 5) (-1, 1) (9, 4) (8, 7) (5, 6) (6, 3)
(5, 2) (0, 5) (-1, 1) (9, 4) (6, 3) (5, 6) (8, 7)
(-1, 1) (0, 5) (5, 2) (9, 4) (6, 3) (5, 6) (8, 7)
(-1, 1) (9, 4) (5, 2) (0, 5) (6, 3) (5, 6) (8, 7)
(-1, 1) (9, 4) (5, 2) (0, 5) (6, 3) (5, 6) (8, 7)
但数字没有排序。我错过了什么？

Answer 1

为简单起见，让我通过具体案例来说明这个想法，这些案例很容易概括。

偶数情况

假设我们有 8 个元素。然后我们使用步骤 2 中的冒泡排序分别对两个子数组(具有奇数和偶数索引)进行排序，并得到

a1    a2    a3    a4
   b1    b2    b3    b4

如果结果数组a1 b1 a2 b2 a3 b3 a4 b4碰巧已经排序了，我们就完成了。否则无解。

奇怪的情况

假设您有 7 个元素。用您最喜欢的方法对它们进行排序。假设排序后它们是

a5 a4 a1 a7 a3 a2 a6

为每个元素分配键，如下所示:

a5 a4 a1 a7 a3 a2 a6
 1  5  2  6  3  7  4

然后回到原来的顺序:

a1 a2 a3 a4 a5 a6 a7
 2  7  3  5  1  4  6

然后使用冒泡排序并每次跳过一个元素，按新键 ( 1 - 7 ) 对这些对进行排序。一旦您对 key 进行排序，您的 a1 ... a7值取其目标位置。

让我们用数组来说明

5 1 5 9 0

排序后的数组和相应的键将是

0 1 5 5 9
1 4 2 5 3

现在让我们按键对对进行排序(我们每一步都比较其键的对位于 <> 中)

<5 2> (1 4) <5 5> (9 3) (0 1) // starting the first loop
(5 2) (1 4) <5 5> (9 3) <0 1>
(5 2) <1 4> (0 1) (9 3) <5 5>
(5 2) <5 5> (0 1) <9 3> (1 4)
<5 2> (9 3) <0 1> (5 5) (1 4) // (5 5) is in its final position, starting the second loop
(0 1) (9 3) <5 2> (5 5) <1 4>
(0 1) <9 3> (5 2) (5 5) <1 4>
<0 1> (1 4) <5 2> (5 5) (9 3) // (1 4) in its final position, starting the third loop
(0 1) (1 4) <5 2> (5 5) <9 3>
<0 1> (1 4) <5 2> (5 5) (9 3) // (9 3) in the final position
(0 1) (1 4) (5 2) (5 5) (9 3) // (0 1) and (5 2) are in final positions