基数排序处理 IP 地址排序

IP 地址本质上是 32 位无符号整数（IPv4），通常表示为点分十进制格式（如 192.168.1.1）。基数排序非常适合处理此类固定长度的整数序列，以下是 Python 实现：

算法原理

1. IP 地址转换：将点分十进制转换为 32 位整数 $$ \text{IP_int} = a \times 256^3 + b \times 256^2 + c \times 256 + d $$ 其中 $a.b.c.d$ 是 IP 的四段

2. 基数排序：从最低有效位到最高有效位（LSD）依次排序

   • 创建 256 个桶（对应 8 位二进制）
   • 按当前位数字分配到桶中
   • 按桶顺序收集元素
   • 重复处理所有 4 个字节（32 位）

Python 实现

def radix_sort_ips(ip_list):
    # 将IP转换为整数元组 (192, 168, 1, 1)
    ips = [tuple(map(int, ip.split('.'))) for ip in ip_list]
    
    # 从最低位（第4段）到最高位（第1段）排序
    for i in range(3, -1, -1):
        buckets = [[] for _ in range(256)]
        
        # 按当前字节分配到桶
        for ip in ips:
            buckets[ip[i]].append(ip)
        
        # 收集桶中元素
        ips = [ip for bucket in buckets for ip in bucket]
    
    # 转换回IP字符串
    return ['.'.join(map(str, ip)) for ip in ips]

# 测试示例
ip_addresses = ["192.168.1.5", "10.0.0.2", "172.16.0.1", "10.0.0.1"]
sorted_ips = radix_sort_ips(ip_addresses)
print(sorted_ips)  # 输出: ['10.0.0.1', '10.0.0.2', '172.16.0.1', '192.168.1.5']

算法分析

• 时间复杂度：$O(4n) = O(n)$
  • 4 轮排序（对应 4 个字节）
  • 每轮 $O(n)$ 的分配和收集操作
• 空间复杂度：$O(n)$（桶的临时存储）
• 稳定性：基数排序是稳定排序，保持相同前缀 IP 的顺序

优化方向

1. 整数优化：直接转换为 32 位整数处理

   ip_int = (a << 24) | (b << 16) | (c << 8) | d
   

2. 并行处理：对海量 IP 可使用多线程分桶
3. 内存优化：对超大数据集使用外部排序

基数排序在 IP 排序场景下效率显著优于 $O(n\log n)$ 的通用排序算法，特别适合网络设备日志分析、安全审计等需要处理海量 IP 的场景。