波浪排序（Wave Sort）的进阶应用与边界条件处理

我将为您详细讲解波浪排序算法，包括其核心概念、实现步骤、边界条件处理以及进阶优化。

问题描述

波浪排序要求将数组重新排列，使得数组元素呈现"波浪形"：arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ... 的形式。

示例：

• 输入：[3, 2, 1, 4, 0]
• 输出：[2, 1, 4, 0, 3] 或 [3, 1, 4, 0, 2] 等有效波浪序列

基础算法实现

方法一：排序后交换法

这是最简单的实现方式：

def wave_sort_basic(arr):
    arr.sort()  # 先排序
    
    # 成对交换相邻元素
    for i in range(0, len(arr)-1, 2):
        arr[i], arr[i+1] = arr[i+1], arr[i]
    
    return arr

步骤分析：

1. 首先对数组进行排序
2. 从索引0开始，每两个元素为一组进行交换
3. 这样保证 arr[0] <= arr[1] >= arr[2] <= arr[3] >= ...

时间复杂度：O(n log n)，主要来自排序操作
空间复杂度：O(1) 或 O(n)，取决于排序算法

进阶优化：线性时间复杂度解法

方法二：一次遍历法

我们可以在O(n)时间内完成波浪排序：

def wave_sort_optimized(arr):
    n = len(arr)
    
    for i in range(0, n, 2):
        # 处理当前元素应该大于等于前一个元素
        if i > 0 and arr[i] < arr[i-1]:
            arr[i], arr[i-1] = arr[i-1], arr[i]
        
        # 处理当前元素应该大于等于后一个元素
        if i < n-1 and arr[i] < arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
    
    return arr

算法逻辑：

1. 遍历所有偶数索引位置（0, 2, 4, ...）
2. 对于每个位置，确保它大于等于相邻元素
3. 如果不符合条件，就进行交换

边界条件处理

1. 空数组和单元素数组

def wave_sort_robust(arr):
    if len(arr) <= 1:
        return arr  # 空数组或单元素数组已经满足波浪条件
    
    n = len(arr)
    for i in range(0, n, 2):
        # 处理左边界
        if i > 0 and arr[i] < arr[i-1]:
            arr[i], arr[i-1] = arr[i-1], arr[i]
        
        # 处理右边界  
        if i < n-1 and arr[i] < arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
    
    return arr

2. 重复元素处理

当数组包含重复元素时，需要特别注意：

def wave_sort_with_duplicates(arr):
    if len(arr) <= 1:
        return arr
    
    n = len(arr)
    
    # 统计元素频率
    from collections import Counter
    count = Counter(arr)
    
    # 获取排序后的唯一元素
    sorted_unique = sorted(count.keys())
    
    result = []
    left, right = 0, len(sorted_unique) - 1
    
    # 交替选择较大和较小元素
    while left <= right:
        if left == right:
            # 中间元素，添加所有重复
            result.extend([sorted_unique[left]] * count[sorted_unique[left]])
        else:
            # 先添加较大元素，再添加较小元素
            result.append(sorted_unique[right])
            result.append(sorted_unique[left])
            
            count[sorted_unique[right]] -= 1
            count[sorted_unique[left]] -= 1
            
            # 如果某个元素的计数变为0，移动指针
            if count[sorted_unique[right]] == 0:
                right -= 1
            if count[sorted_unique[left]] == 0:
                left += 1
    
    return result

验证算法正确性

验证函数

def is_valid_wave(arr):
    """验证数组是否满足波浪排序条件"""
    for i in range(len(arr)):
        if i % 2 == 0:  # 波峰位置
            if i > 0 and arr[i] < arr[i-1]:
                return False
            if i < len(arr)-1 and arr[i] < arr[i+1]:
                return False
        else:  # 波谷位置
            if i > 0 and arr[i] > arr[i-1]:
                return False
            if i < len(arr)-1 and arr[i] > arr[i+1]:
                return False
    return True

性能对比测试

让我们比较不同方法的性能：

import time
import random

def benchmark_wave_sort():
    sizes = [100, 1000, 10000]
    
    for size in sizes:
        arr = [random.randint(0, 1000) for _ in range(size)]
        
        # 测试基础方法
        arr1 = arr.copy()
        start = time.time()
        result1 = wave_sort_basic(arr1)
        time1 = time.time() - start
        
        # 测试优化方法
        arr2 = arr.copy()
        start = time.time()
        result2 = wave_sort_optimized(arr2)
        time2 = time.time() - start
        
        print(f"数组大小 {size}:")
        print(f"  基础方法: {time1:.6f}s, 验证: {is_valid_wave(result1)}")
        print(f"  优化方法: {time2:.6f}s, 验证: {is_valid_wave(result2)}")
        print()

实际应用场景

1. 信号处理：将信号数据排列成波浪形式便于分析
2. 数据可视化：创建波浪状的数据图表
3. 近似排序：当不需要完全排序但需要某种规律时
4. 算法竞赛：作为某些编程问题的预处理步骤

总结

波浪排序是一个有趣且实用的排序变种，它的关键点在于：

1. 核心思想：创建交替的波峰和波谷模式
2. 时间复杂度：从O(n log n)优化到O(n)
3. 边界处理：特别注意空数组、单元素数组和重复元素的情况
4. 验证重要性：实现后必须验证结果是否满足波浪条件

这种排序算法展示了如何根据特定需求调整标准排序策略，是理解算法灵活性的很好示例。