如何原地重排数组：实现偶索引前置及反向的单循环高效方案

嘿，这个问题我之前在优化数组重排性能的时候碰到过，拆分合并虽然直观，但面对大数据量时内存开销确实不友好。要实现单循环、原地、无额外O(n)内存分配的方案，核心思路是利用索引映射环——每个元素最终的位置会和其他元素形成一个闭合的环，我们只需要遍历每个环，依次把元素交换到正确位置即可，全程只用一个临时变量，时间复杂度O(n)。

1. 偶数索引元素前置（原偶数索引→数组前半段） #

先理清楚索引映射规则：我们要把原数组中索引为0、2、4...的元素移到前半段，1、3、5...移到后半段。每个原索引k的最终位置可以用简单公式计算：

• 如果k是偶数：最终位置是k//2（对应前半段的第k/2个位置）
• 如果k是奇数：最终位置是m + k//2，其中m=(n+1)//2是前半段的长度（也就是原偶数索引元素的总数量）

下面是实现代码：

def even_indices_first(arr):
    n = len(arr)
    if n <= 1:
        return
    m = (n + 1) // 2  # 前半段长度：原偶数索引元素的数量
    
    def get_target(k):
        # 计算原索引k的元素最终要去的位置
        return k // 2 if k % 2 == 0 else m + k // 2
    
    for k in range(n):
        # 跳过已处理的元素：当目标位置<=当前索引时，说明该元素已被前面的环处理过
        if get_target(k) <= k:
            continue
        current = k
        temp = arr[current]  # 保存当前环的起始元素
        while True:
            next_pos = get_target(current)
            # 把当前元素放到目标位置，同时保存目标位置的原元素
            arr[next_pos], temp = temp, arr[next_pos]
            current = next_pos
            if current == k:  # 回到环的起点，结束当前环的处理
                break

举个实际例子：输入数组['a','b','c','d','e','f']，经过处理后会变成['a','c','e','b','d','f']，完全符合题目要求。

2. 奇数索引元素前置（原奇数索引→数组前半段） #

反向操作的思路完全一致，只是索引映射公式需要调整：

• 如果k是奇数：最终位置是k//2（对应前半段的第(k-1)/2个位置）
• 如果k是偶数：最终位置是m + k//2，其中m=n//2是前半段的长度（原奇数索引元素的总数量）

对应的实现代码：

def odd_indices_first(arr):
    n = len(arr)
    if n <= 1:
        return
    m = n // 2  # 前半段长度：原奇数索引元素的数量
    
    def get_target(k):
        # 计算原索引k的元素最终要去的位置
        return k // 2 if k % 2 == 1 else m + k // 2
    
    for k in range(n):
        if get_target(k) <= k:
            continue
        current = k
        temp = arr[current]
        while True:
            next_pos = get_target(current)
            arr[next_pos], temp = temp, arr[next_pos]
            current = next_pos
            if current == k:
                break

测试例子：输入['a','b','c','d','e','f']，处理后得到['b','d','f','a','c','e']，和题目要求的反向操作结果一致。

方案优势说明 #

• 性能高效：每个元素只会被处理一次，外层循环遍历所有索引，但内层while循环仅处理未被处理的环，总时间复杂度为O(n)。
• 原地操作：全程只使用一个临时变量temp，没有额外分配数组、集合等O(n)空间，完全符合“无需临时内存分配”的要求。
• 兼容性强：不管数组长度是奇数还是偶数都能正常工作，比如长度为5的数组['a','b','c','d','e']，偶数前置后会变成['a','c','e','b','d']，奇数前置后变成['b','d','a','c','e']。

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