排序算法 (Sorting Algorithms)-Python示例

发布于:2025-07-29 ⋅ 阅读:(10) ⋅ 点赞:(0)

经典排序算法 Python 示例

1. 冒泡排序 (Bubble Sort)

def bubble_sort(arr):
    """
    冒泡排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    稳定性: 稳定
    """
    n = len(arr)
    # 创建数组副本以避免修改原数组
    result = arr.copy()
    
    for i in range(n - 1):
        swapped = False
        # 每轮将最大元素"冒泡"到末尾
        for j in range(n - i - 1):
            if result[j] > result[j + 1]:
                # 交换元素
                result[j], result[j + 1] = result[j + 1], result[j]
                swapped = True
        # 如果没有发生交换,说明数组已经有序
        if not swapped:
            break
    
    return result

# 示例使用
arr1 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr1)
print('冒泡排序结果:', bubble_sort(arr1))

2. 选择排序 (Selection Sort)

def selection_sort(arr):
    """
    选择排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    稳定性: 不稳定
    """
    n = len(arr)
    result = arr.copy()
    
    for i in range(n - 1):
        # 找到未排序部分的最小元素索引
        min_index = i
        for j in range(i + 1, n):
            if result[j] < result[min_index]:
                min_index = j
        # 将最小元素与未排序部分的第一个元素交换
        if min_index != i:
            result[i], result[min_index] = result[min_index], result[i]
    
    return result

# 示例使用
arr2 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr2)
print('选择排序结果:', selection_sort(arr2))

3. 插入排序 (Insertion Sort)

def insertion_sort(arr):
    """
    插入排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    稳定性: 稳定
    """
    result = arr.copy()
    
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        
        # 将大于key的元素向右移动
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    
    return result

# 示例使用
arr3 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr3)
print('插入排序结果:', insertion_sort(arr3))

4. 快速排序 (Quick Sort)

def quick_sort(arr):
    """
    快速排序算法
    时间复杂度: 平均 O(n log n),最坏 O(n²)
    空间复杂度: O(log n)
    稳定性: 不稳定
    """
    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
        arr = arr.copy()
    
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)
    
    return arr

def partition(arr, low, high):
    """
    分区函数
    """
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 示例使用
arr4 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr4)
print('快速排序结果:', quick_sort(arr4))

5. 归并排序 (Merge Sort)

def merge_sort(arr):
    """
    归并排序算法
    时间复杂度: O(n log n)
    空间复杂度: O(n)
    稳定性: 稳定
    """
    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 = []
    left_index = right_index = 0
    
    # 合并两个已排序的数组
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    # 添加剩余元素
    result.extend(left[left_index:])
    result.extend(right[right_index:])
    
    return result

# 示例使用
arr5 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr5)
print('归并排序结果:', merge_sort(arr5))

6. 堆排序 (Heap Sort)

def heap_sort(arr):
    """
    堆排序算法
    时间复杂度: O(n log n)
    空间复杂度: O(1)
    稳定性: 不稳定
    """
    result = arr.copy()
    n = len(result)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(result, n, i)
    
    # 逐个提取元素
    for i in range(n - 1, 0, -1):
        result[0], result[i] = result[i], result[0]  # 将当前最大元素移到末尾
        heapify(result, i, 0)  # 重新调整堆
    
    return result

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)

# 示例使用
arr6 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr6)
print('堆排序结果:', heap_sort(arr6))

7. 计数排序 (Counting Sort)

def counting_sort(arr):
    """
    计数排序算法(适用于范围较小的整数)
    时间复杂度: O(n + k),k为数据范围
    空间复杂度: O(k)
    稳定性: 稳定
    """
    if not arr:
        return 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
    
    # 重构排序后的数组
    result = []
    for i in range(len(count)):
        result.extend([i + min_val] * count[i])
    
    return result

# 示例使用
arr7 = [4, 2, 2, 8, 3, 3, 1]
print('原数组:', arr7)
print('计数排序结果:', counting_sort(arr7))

实际中的应用

1. 数据库系统

  • 索引构建:数据库索引通常需要排序来提高查询效率
  • 查询优化:ORDER BY 子句的实现依赖于排序算法
  • 连接操作:排序-合并连接算法用于表连接操作

2. 搜索引擎

  • 搜索结果排序:根据相关性对搜索结果进行排序
  • 网页排名:PageRank 等算法需要对网页进行排序
  • 倒排索引:构建搜索引擎的核心数据结构

3. 操作系统

  • 进程调度:根据优先级对进程进行排序
  • 内存管理:空闲内存块的管理需要排序
  • 文件系统:目录项的排序显示

4. 图形处理

  • 渲染管线:根据深度对图形元素进行排序(Z-buffer算法)
  • 可见性判断:画家算法需要对图元按深度排序
  • 动画处理:关键帧的排序和插值

5. 金融系统

  • 交易撮合:买卖订单按照价格和时间排序
  • 风险评估:对投资组合按风险等级排序
  • 报表生成:财务数据的排序展示

6. 电商系统

  • 商品推荐:根据用户偏好对商品进行排序
  • 价格比较:商品按价格排序展示
  • 库存管理:商品按库存量排序管理

7. 社交媒体

  • 信息流排序:根据时间、热度等对内容排序
  • 好友推荐:按相关性对推荐好友排序
  • 消息处理:聊天记录按时间排序

8. 科学计算

  • 数据分析:实验数据的排序和统计
  • 模拟计算:粒子按位置排序以优化计算
  • 生物信息学:基因序列的排序比对

9. 游戏开发

  • 排行榜:玩家得分排序
  • 碰撞检测:游戏对象按空间位置排序优化检测
  • AI决策:游戏AI根据评估函数对可能动作排序

10. 网络通信

  • 数据包排序:TCP协议中对数据包按序号排序
  • 负载均衡:根据服务器负载对请求排序分配
  • 路由选择:网络路由按成本排序选择最优路径

11. 机器学习

  • 特征排序:按重要性对特征进行排序
  • K近邻算法:需要对距离进行排序找到最近邻居
  • 聚类算法:某些聚类算法需要排序操作

12. 数据分析与可视化

  • 统计分析:对数据进行排序以便分析趋势
  • 图表绘制:柱状图、折线图等需要排序数据
  • 报表生成:按不同维度对数据进行排序展示

网站公告

今日签到

点亮在社区的每一天
去签到