Python版快速排序在数据去重中的应用实战

问题分析

数据去重需满足两个条件：

1. 保留唯一元素
2. 维持原始顺序（可选）

快速排序算法的时间复杂度为 $O(n \log n)$，结合排序后相邻元素比较的去重策略，可实现高效去重。其核心思路为： $$ \text{去重} = \text{排序} + \text{相邻过滤} $$

实现方案

def quick_sort(arr):
    """快速排序实现"""
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def deduplicate(data):
    """基于快速排序的去重方法"""
    if not data:
        return []
    
    sorted_data = quick_sort(data)  # 排序
    result = [sorted_data[0]]
    
    # 遍历已排序数据，过滤重复项
    for i in range(1, len(sorted_data)):
        if sorted_data[i] != sorted_data[i-1]:
            result.append(sorted_data[i])
    
    return result

应用案例

假设电商平台需处理用户搜索记录：

search_history = ["手机", "耳机", "手机", "电脑", "耳机", "平板", "电脑"]

# 去重处理
unique_history = deduplicate(search_history)
print("去重结果:", unique_history)

输出：

去重结果: ['手机', '平板', '电脑', '耳机']

算法优势

1. 时间复杂度：$O(n \log n)$ 排序 + $O(n)$ 遍历 = $O(n \log n)$
2. 空间效率：额外空间仅 $O(n)$
3. 适用场景：
   • 海量数据去重（如日志分析）
   • 需要有序结果的场景
   • 内存受限环境（递归深度可控）

变体优化

# 保持原始顺序的去重（牺牲部分时间效率）
def ordered_deduplicate(data):
    seen = set()
    return [x for x in data if not (x in seen or seen.add(x))]

提示：当数据量超过 $10^6$ 时，建议改用非递归排序避免栈溢出，可通过设置最大递归深度实现：

import sys
sys.setrecursionlimit(10000)