Python中如何实现数组的“锯齿形”排序：array[0] < array[1] > array[2] < array[3] ...

def zigzag_sort(arr):
    """
    实现锯齿形排序：arr[0] < arr[1] > arr[2] < arr[3] ...
    思路：先排序，然后交换相邻元素（从第二个元素开始）
    """
    if not arr:
        return arr
    
    # 1. 先排序
    arr.sort()
    
    # 2. 从索引1开始，每隔一个元素与后一个元素交换
    for i in range(1, len(arr)-1, 2):
        arr[i], arr[i+1] = arr[i+1], arr[i]
    
    return arr

# 测试用例
def test_zigzag():
    # 测试1: 正常数组
    test1 = [3, 5, 2, 1, 6, 4]
    print(f"输入: {test1}")
    print(f"输出: {zigzag_sort(test1)}")  # 可能输出: [1, 3, 2, 5, 4, 6]
    print(f"验证: {test1[0] < test1[1] > test1[2] < test1[3] > test1[4] < test1[5]}")
    print()
    
    # 测试2: 已排序数组
    test2 = [1, 2, 3, 4, 5, 6]
    print(f"输入: {test2}")
    print(f"输出: {zigzag_sort(test2)}")  # 输出: [1, 3, 2, 5, 4, 6]
    print()
    
    # 测试3: 奇数长度数组
    test3 = [9, 8, 7, 6, 5]
    print(f"输入: {test3}")
    print(f"输出: {zigzag_sort(test3)}")  # 输出: [5, 7, 6, 9, 8]

if __name__ == "__main__":
    test_zigzag()

算法解释：

1. 先排序：确保数组有序，这样我们就有确定的元素顺序可以操作
2. 交换相邻元素：从索引1开始（第二个元素），每隔一个位置交换arr[i]和arr[i+1]
   • 交换后：arr[i-1] < arr[i] > arr[i+1] 成立
   • 因为原数组已排序，所以arr[i-1] ≤ arr[i+1]，交换后arr[i-1] < arr[i]通常成立

时间复杂度： O(n log n)（主要来自排序） 空间复杂度： O(1)（原地修改）

一句话总结： 先排序再间隔交换就能搞定锯齿形排序。