GeeksForGeeks数组交替重排问题：Python代码触发IndexError求助

给定已排序的正整数数组arr和长度n，要求直接修改原数组，将元素交替重排为：最大值、最小值、第二大值、第二小值……即先大后小交替排列。

当前代码触发IndexError: list index out of range，代码及报错信息如下：

def rearrange(arr, n):
        arr1,arr2 = sorted(arr[:(n//2)]), sorted(arr[(n//2):],reverse=True)
        arr.clear()
        for i in range(n):
            arr.append(arr2[0]); arr2.pop(0)
            arr.append(arr1[0]); arr1.pop(0)

报错信息：

File "/home/4c7d0350d40e21b84be527508f21cb47.py", line 9, in rearrange
    arr.append(arr2[0]); arr2.pop(0)
IndexError: list index out of range

错误原因 #

• 数组拆分长度不匹配：当n是奇数时，n//2会把原数组拆成长度不等的两部分。比如n=5，arr[:2]长度为2，arr[2:]长度为3，导致arr1和arr2长度不一样。
• 循环逻辑错误：循环执行n次，每次从arr2和arr1各取一个元素，但两个数组长度不等，其中一个会先被取空，后续循环再访问arr[0]就会触发索引越界。另外，n次循环每次加2个元素，最终数组长度会变成2n，完全不符合要求。

修正方案 #

方案一：拆分后交替合并（直观易懂） #

原数组已经是排序好的，不需要再对拆分后的子数组排序，直接拆分后合并即可：

def rearrange(arr, n):
    # 处理奇数长度，让后半段（大值部分）长度>=前半段（小值部分）
    mid = (n + 1) // 2
    # 小值部分保留正序，大值部分逆序（从大到小）
    small_part = arr[:mid]
    large_part = arr[mid:][::-1]
    
    arr.clear()
    # 交替添加大值和小值，直到其中一个部分为空
    while small_part and large_part:
        arr.append(large_part.pop(0))
        arr.append(small_part.pop(0))
    # 处理剩余的元素（仅当n为奇数时，small_part会剩一个元素）
    if small_part:
        arr.append(small_part.pop(0))
    if large_part:
        arr.append(large_part.pop(0))

方案二：原地修改（无额外数组开销） #

如果想要完全原地修改，不创建额外数组，可以用标记法实现：

def rearrange(arr, n):
    max_index = n - 1
    min_index = 0
    # 取一个比数组最大值大的数作为标记，用来同时存储新旧值
    marker = arr[-1] + 1

    # 先把每个位置的元素替换为（新值 + 旧值 * marker），保留新旧信息
    for i in range(n):
        if i % 2 == 0:
            # 偶数位置放当前最大值
            arr[i] += (arr[max_index] % marker) * marker
            max_index -= 1
        else:
            # 奇数位置放当前最小值
            arr[i] += (arr[min_index] % marker) * marker
            min_index += 1
    
    # 还原数组，去掉标记
    for i in range(n):
        arr[i] = arr[i] // marker

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