基础排序算法实

1. 快速排序（Quick Sort）

算法原理： 采用分治策略，选取基准值(pivot)将数组分为两部分，递归排序子数组

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 quick_sort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1 
    if low < high:
        # 分区操作 
        pivot_index = partition(arr, low, high)
        # 递归排序子数组 
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)
 
def partition(arr, low, high):
    """分区函数，返回基准位置"""
    pivot = arr[high]  # 选择最后一个元素作为基准 
    i = low 
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1 
    arr[i], arr[high] = arr[high], arr[i]
    return i 
 
测试用例 
nums = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(nums)
print("快速排序结果:", nums)  # 输出: [1, 1, 2, 3, 6, 8, 10]

性能特点：

• 平均时间复杂度：O(n log n)
• 最坏情况（已排序数组）：O(n^2)
• 空间复杂度：O(log n)（递归调用栈）

2. 归并排序（Merge Sort）

算法原理： 递归地将数组分成两半分别排序，然后合并两个有序数组

def merge_sort(arr):
    """归并排序实现"""
    if len(arr) <= 1:
        return arr 
    
    # 分割数组 
    mid = len(arr) // 2 
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 合并已排序数组 
    return merge(left, right)
 
def merge(left, right):
    """合并两个有序数组"""
    result = []
    i = j = 0 
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1 
        else:
            result.append(right[j])
            j += 1 
    
    # 添加剩余元素 
    result.extend(left[i:])
    result.extend(right[j:])
    return result 
 
测试用例 
nums = [12, 11, 13, 5, 6, 7]
print("归并排序结果:", merge_sort(nums))  # 输出: [5, 6, 7, 11, 12, 13]

性能特点：

• 时间复杂度：O(n log n)（所有情况）
• 空间复杂度：O(n)（需要临时数组）
• 稳定排序算法

高效实用排序算法

1. 堆排序（Heap Sort）

算法原理： 利用二叉堆的性质进行排序，分为建堆和不断提取最大/最小元素两个阶段

def heap_sort(arr):
    """堆排序实现"""
    n = len(arr)
    
    # 构建最大堆 
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个提取元素 
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换 
        heapify(arr, i, 0)
 
def heapify(arr, n, i):
    """堆调整函数"""
    largest = i  # 初始化最大元素为根 
    left = 2 * i + 1 
    right = 2 * i + 2 
    
    # 左子节点大于根 
    if left < n and arr[left] > arr[largest]:
        largest = left 
    
    # 右子节点大于当前最大值 
    if right < n and arr[right] > arr[largest]:
        largest = right 
    
    # 如果最大值不是根，交换并继续堆化 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
测试用例 
nums = [12, 11, 13, 5, 6, 7]
heap_sort(nums)
print("堆排序结果:", nums)  # 输出: [5, 6, 7, 11, 12, 13]

性能特点：

• 时间复杂度：O(n log n)（所有情况）
• 空间复杂度：O(1)（原地排序）
• 不稳定排序算法

2. 计数排序（Counting Sort）

适用场景： 整数排序，数据范围不大且密集的情况

def counting_sort(arr, max_val=None):
    """计数排序实现"""
    if max_val is None:
        max_val = max(arr)
    
    # 初始化计数数组 
    count = [0] * (max_val + 1)
    
    # 计算每个元素出现次数 
    for num in arr:
        count[num] += 1 
    
    # 重构排序后的数组 
    sorted_arr = []
    for num, cnt in enumerate(count):
        sorted_arr.extend([num] * cnt)
    
    return sorted_arr 
 
优化版本（处理任意范围）
def counting_sort_advanced(arr):
    min_val = min(arr)
    max_val = max(arr)
    
    # 计算偏移量并初始化计数数组 
    count = [0] * (max_val - min_val + 1)
    
    # 计数 
    for num in arr:
        count[num - min_val] += 1 
    
    # 重构数组 
    sorted_arr = []
    for i, cnt in enumerate(count):
        sorted_arr.extend([i + min_val] * cnt)
    
    return sorted_arr 
 
测试用例 
nums = [4, 2, 2, 8, 3, 3, 1]
print("计数排序结果:", counting_sort_advanced(nums))  # 输出: [1, 2, 2, 3, 3, 4, 8]

性能特点：

• 时间复杂度：O(n + k)（k是数据范围）
• 空间复杂度：O(n + k)
• 稳定排序（在优化实现中）

混合排序算法

1. Timsort算法（Python内置排序）

算法原理： 结合归并排序和插入排序的优点，是Python内置的sorted()和list.sort()使用的算法

Python实际上使用C实现的Timsort，这里展示类似逻辑 
def insertion_sort(arr, left=0, right=None):
    """插入排序，用于小规模数据"""
    if right is None:
        right = len(arr) - 1 
    
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1 
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1 
        arr[j + 1] = key 
 
def timsort(arr):
    """简化版Timsort实现"""
    min_run = 32 
    n = len(arr)
    
    # 对小片段进行插入排序 
    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))
    
    # 逐步合并排序好的片段 
    size = min_run 
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1 
            end = min((start + size * 2 - 1), (n - 1))
            
            # 合并两个相邻片段 
            merged = merge(arr[start:mid + 1], arr[mid + 1:end + 1])
            arr[start:start + len(merged)] = merged 
        size *= 2 
    
    return arr 
 
测试用例 
import random 
nums = [random.randint(1, 1000) for _ in range(100)]
sorted_nums = timsort(nums.copy())
print("Timsort前5个:", sorted_nums[:5])

性能特点：

• 时间复杂度： 最佳情况：O(n)（已排序数组） 平均情况：O(n log n) 最坏情况：O(n log n)
• 空间复杂度：O(n)
• 稳定排序

2. 桶排序（Bucket Sort）

适用场景： 数据均匀分布在某个范围内时效率最高

def bucket_sort(arr, bucket_size=5):
    """桶排序实现"""
    if len(arr) == 0:
        return arr 
    
    # 确定数据范围 
    min_val = min(arr)
    max_val = max(arr)
    
    # 初始化桶 
    bucket_count = (max_val - min_val) // bucket_size + 1 
    buckets = [[] for _ in range(bucket_count)]
    
    # 将元素分配到桶中 
    for num in arr:
        buckets[(num - min_val) // bucket_size].append(num)
    
    # 对每个桶排序并合并 
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))  # 这里可以使用任意排序算法 
    
    return sorted_arr 
 
测试用例 
nums = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
print("桶排序结果:", bucket_sort(nums))  # 输出: [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]

性能特点：

• 时间复杂度： 最佳情况：O(n + k)（k是桶的数量） 平均情况：O(n + n^2/k + k)（当使用O(n^2)排序算法时） 最坏情况：O(n^2)（所有元素在一个桶中）
• 空间复杂度：O(n + k)

特定场景排序算法

1. 基数排序（Radix Sort）

适用场景： 非负整数或固定长度字符串排序

def radix_sort(arr):
    """基数排序实现（LSD）"""
    # 获取最大位数 
    max_num = max(arr)
    max_digit = len(str(max_num))
    
    for digit in range(max_digit):
        # 每位数使用计数排序 
        buckets = [[] for _ in range(10)]
        
        for num in arr:
            # 获取当前位的数字 
            d = (num // (10  digit)) % 10 
            buckets[d].append(num)
        
        # 重新组合数组 
        arr = [num for bucket in buckets for num in bucket]
    
    return arr 
 
测试用例 
nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("基数排序结果:", radix_sort(nums))  # 输出: [2, 24, 45, 66, 75, 90, 170, 802]

性能特点：

• 时间复杂度：O(d(n + k))（d是最大位数，k是基数如10）
• 空间复杂度：O(n + k)
• 稳定排序

2. 拓扑排序（Topological Sort）

适用场景： 有向无环图(DAG)的任务排序

from collections import defaultdict, deque 
 
def topological_sort(graph):
    """拓扑排序实现"""
    # 计算入度 
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1 
    
    # 初始化队列（入度为0的节点）
    queue = deque([u for u in graph if in_degree[u] == 0])
    sorted_order = []
    
    while queue:
        u = queue.popleft()
        sorted_order.append(u)
        
        # 减少邻居的入度 
        for v in graph[u]:
            in_degree[v] -= 1 
            if in_degree[v] == 0:
                queue.append(v)
    
    # 检查是否存在环 
    if len(sorted_order) != len(graph):
        raise ValueError("图中存在环，无法进行拓扑排序")
    
    return sorted_order 
 
测试用例 
course_graph = {
    'C1': ['C3'],
    'C2': ['C3', 'C4'],
    'C3': ['C5'],
    'C4': ['C5', 'C6'],
    'C5': [],
    'C6': []
}
print("拓扑排序结果:", topological_sort(course_graph)) 
可能的输出: ['C1', 'C2', 'C3', 'C4', 'C5', 'C6']

性能特点：

• 时间复杂度：O(V + E)（顶点数加边数）
• 空间复杂度：O(V)

排序算法应用

1. 多条件排序

复杂对象排序

class Student:
    def __init__(self, name, grade, age):
        self.name = name 
        self.grade = grade 
        self.age = age 
    
    def __repr__(self):
        return f"{self.name}({self.grade}, {self.age})"
 
创建测试数据 
students = [
    Student('张三', 'B', 20),
    Student('李四', 'A', 22),
    Student('王五', 'B', 21),
    Student('赵六', 'A', 20)
]
 
按成绩升序，年龄降序排序 
students_sorted = sorted(students, key=lambda s: (s.grade, -s.age))
print("多条件排序结果:", students_sorted)
输出: [李四(A, 22), 赵六(A, 20), 王五(B, 21), 张三(B, 20)]

2. 处理大规模数据

外部排序技术

import tempfile 
import heapq 
 
def external_sort(input_file, output_file, chunk_size=1000):
    """外部排序实现"""
    # 第一步：分块排序 
    temp_files = []
    with open(input_file, 'r') as f:
        while True:
            chunk = []
            for _ in range(chunk_size):
                line = f.readline()
                if not line:
                    break 
                chunk.append(int(line))
            
            if not chunk:
                break 
            
            chunk.sort()
            
            # 写入临时文件 
            temp_file = tempfile.NamedTemporaryFile(delete=False)
            with open(temp_file.name, 'w') as tf:
                for num in chunk:
                    tf.write(f"{num}\n")
            temp_files.append(temp_file.name)
    
    # 第二步：多路归并 
    with open(output_file, 'w') as out_f:
        # 打开所有临时文件 
        files = [open(fname, 'r') for fname in temp_files]
        # 使用堆进行归并 
        heap = []
        for i, f in enumerate(files):
            line = f.readline()
            if line:
                heapq.heappush(heap, (int(line), i))
        
        while heap:
            num, file_idx = heapq.heappop(heap)
            out_f.write(f"{num}\n")
            
            # 从对应文件中读取下一行 
            line = files[file_idx].readline()
            if line:
                heapq.heappush(heap, (int(line), file_idx))
        
        # 关闭文件 
        for f in files:
            f.close()
    
    # 清理临时文件 
    for fname in temp_files:
        os.unlink(fname)
 
生成测试数据 
import random 
with open('large_input.txt', 'w') as f:
    for _ in range(10000):
        f.write(f"{random.randint(1, 1000000)}\n")
 
执行外部排序 
external_sort('large_input.txt', 'sorted_output.txt')

附录：排序算法性能对比表

表：常见排序算法性能对比

#编程# #python# #在头条记录我的2025# #春日生活打卡季#

持续更新Python编程相关学习日志，敬请关注！