排序算法之：Brick Sort（砖排序）的边界条件处理与性能优化

题目描述：
给定一个整数数组，使用Brick Sort算法对其进行排序。Brick Sort是冒泡排序的一种变体，也称为奇偶排序(Odd-Even Sort)的另一种实现方式。算法通过比较和交换相邻元素来工作，但比较的相邻元素对取决于当前是奇数阶段还是偶数阶段。

解题过程：

1. 算法基本思想
   Brick Sort将排序过程分为两个交替阶段：

• 偶数阶段：比较所有偶数索引和其后继奇数索引的元素对(i, i+1)，其中i为偶数
• 奇数阶段：比较所有奇数索引和其后继偶数索引的元素对(i, i+1)，其中i为奇数

2. 算法步骤详解

步骤1：初始化

def brick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr  # 边界情况：空数组或单元素数组已排序
    
    is_sorted = False

步骤2：主循环控制
算法持续运行，直到数组完全有序

while not is_sorted:
    is_sorted = True
    
    # 偶数阶段
    for i in range(0, n-1, 2):  # 步长为2，处理偶数索引
        if arr[i] > arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            is_sorted = False
    
    # 奇数阶段  
    for i in range(1, n-1, 2):  # 步长为1，处理奇数索引
        if arr[i] > arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            is_sorted = False

3. 边界条件处理优化

步骤3：改进的边界检查

def optimized_brick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    is_sorted = False
    
    while not is_sorted:
        is_sorted = True
        
        # 偶数阶段：索引0, 2, 4...
        for i in range(0, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                is_sorted = False
        
        # 奇数阶段：索引1, 3, 5...
        for i in range(1, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                is_sorted = False
        
        # 添加提前终止条件
        if is_sorted:
            break

4. 性能优化策略

步骤4：跟踪最后一次交换位置

def advanced_brick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    last_swap = n - 1
    
    while last_swap > 0:
        new_last_swap = 0
        
        # 偶数阶段
        for i in range(0, last_swap, 2):
            if i + 1 <= last_swap and arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                new_last_swap = i
        
        # 奇数阶段
        for i in range(1, last_swap, 2):
            if i + 1 <= last_swap and arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                new_last_swap = i
        
        last_swap = new_last_swap

5. 算法复杂度分析

• 时间复杂度：

  • 最坏情况：O(n²) - 当数组完全逆序时
  • 平均情况：O(n²)
  • 最佳情况：O(n) - 当数组已排序时

• 空间复杂度：O(1) - 原地排序

6. 实际应用示例

示例：排序数组 [3, 2, 5, 1, 4]

第一次迭代（偶数阶段）：

• 比较(3,2) → 交换 → [2,3,5,1,4]
• 比较(5,1) → 交换 → [2,3,1,5,4]

第一次迭代（奇数阶段）：

• 比较(3,1) → 交换 → [2,1,3,5,4]
• 比较(5,4) → 交换 → [2,1,3,4,5]

继续迭代直到完全有序...

通过这种交替比较的方式，Brick Sort能够有效地将元素"冒泡"到正确位置，同时通过边界条件优化提高了实际运行效率。