当前位置: 首页 > article >正文

Python实现快速排序的三种经典写法及算法解析

今天想熟悉一下python的基础写法,那就从最经典的快速排序来开始吧:

1、经典分治写法(原地排序)
时间复杂度:平均O(nlogn),最坏O(n²)
空间复杂度:O(logn)递归栈空间
特点:通过左右指针交换实现原地排序

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

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

2、Pythonic简洁写法(非原地)
特点:利用列表推导式,代码更简洁但需要额外空间

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)

 

3、尾递归优化写法
特点:减少递归深度,避免栈溢出风险

quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    while low < high:
        pi = partition(arr, low, high)
        if pi - low < high - pi:
            quick_sort(arr, low, pi-1)
            low = pi + 1
        else:
            quick_sort(arr, pi+1, high)
            high = pi - 1
    return arr

算法核心思想:分治法+基准值选取。第一种实现最接近传统快速排序定义,第二种适合教学演示,第三种适合处理大数据集。实际使用时建议添加随机化基准值选择来避免最坏情况。

http://www.lryc.cn/news/2403075.html

相关文章:

  • 【递归、搜索与回溯】综合练习(四)
  • 强化学习入门:Gym实现CartPole随机智能体
  • STM32:CAN总线精髓:特性、电路、帧格式与波形分析详解
  • 贝叶斯深度学习!华科大《Nat. Commun.》发表BNN重大突破!
  • 【大模型LLM学习】Flash-Attention的学习记录
  • 三、元器件的选型
  • 精益数据分析(95/126):Socialight的定价转型启示——B2B商业模式的价格策略与利润优化
  • stm32_DMA
  • 物联网数据归档之数据存储方案选择分析
  • 【自动驾驶避障开发】如何让障碍物在 RViz 中‘显形’?呈现感知数据转 Polygon 全流程
  • 【C语言】C语言经典小游戏:贪吃蛇(上)
  • usbutils工具的使用帮助
  • vue2中使用jspdf插件实现页面自定义块pdf下载
  • 如何防止服务器被用于僵尸网络(Botnet)攻击 ?
  • 基于cornerstone3D的dicom影像浏览器 第二十九章 自定义菜单组件
  • 【Block总结】DBlock,结合膨胀空间注意模块(Di-SpAM)和频域模块Gated-FFN|即插即用|CVPR2025
  • 【学习笔记】单例类模板
  • 字符串加密(华为OD)
  • 口罩佩戴检测算法AI智能分析网关V4工厂/工业等多场景守护公共卫生安全
  • Double/Debiased Machine Learning
  • HarmonyOS Next 弹窗系列教程(4)
  • 【C】-递归
  • 飞马LiDAR500雷达数据预处理
  • Kerberos面试内容整理-在 Linux/Windows 中的 Kerberos 实践
  • 在 Allegro PCB Editor 中取消(解除或删除)已创建的 **Module** 的操作指南
  • 基于springboot的校园社团信息系统的设计与实现
  • nodejs里面的http模块介绍和使用
  • mamba架构和transformer区别
  • 嵌入式鸿蒙开发环境搭建操作方法与实现
  • 在 Spring Boot 中使用 WebFilter:实现请求拦截、日志记录、跨域处理等通用逻辑!