讲师中心 微信公众号

工具推荐

视频效率加速
立刻MV
立刻MV

低成本歌曲 MV、视频生成

updream

一键生成高质量推广成片

Laper
Laper

剧本策划到成片协作

SoundView
SoundView

字幕擦除翻译、配音口型同步

分享Python常用的排序实例

冬伟同学_6456

冬伟同学_6456

发布时间:2017-06-21 16:40:36

|

1559人浏览过

|

来源于php中文网

原创

  • 排序算法的稳定性及意义

  • 冒泡排序

    • 复杂度与稳定性

  • 选择排序

  • 插入排序

    立即学习“Python免费学习笔记(深入)”;

  • 希尔排序

  • 快速排序

  • 常见排序算法效率比较

排序算法的稳定性及意义

在待排序的序列中,存在具有相同关键字的记录,在排序后这些记录的相对次序保持不变,则排序算法是稳定的。

不稳定排序无法完成多个关键字的排序。例如整数排序,位数越高的数字优先级越高,从高位数到低位数一次排序。那么每一位的排序都需要稳定算法,否则无法得到正确的结果。

即,当要对多个关键词多次排序时,必须使用稳定算法

冒泡排序

Screen Shot 2017-06-11 at 10.23.12 A

def bubble_sort(alist):
    """
    冒泡排序
    """
    if len(alist) <= 1:
        return alist

    for j in range(len(alist)-1,0,-1):
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

    return alist

复杂度与稳定性

  • 最优时间复杂度:\(O(n)\) 遍历没有发现任何可以交换的元素,排序结束

  • 最坏时间复杂度:\(O(n^2)\)

  • 稳定性:稳定

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

插入排序

插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

Biopython
Biopython

全面的分子生物学工具集。适用于序列操作、文件解析(FASTA/GenBank/PDB)、系统发育分析,以及通过 Bio.Entrez 以编程方式访问 NCBI/

下载

Screen Shot 2017-06-12 at 7.07.03 P

def insert_sort(alist):
    """
    插入排序
    """
    n = len(alist)
    if n <= 1:
        return alist

    # 从第二个位置,即下表为1的元素开始向前插入
    for i in range(1, n):
        j = i
        # 向前向前比较,如果小于前一个元素,交换两个元素
        while alist[j] < alist[j-1] and j > 0:
            alist[j], alist[j-1] = alist[j-1], alist[j]
            j-=1
    return alist

复杂度与稳定性

  • 最优时间复杂度:O(\(n\)) (升序排列,序列已经处于升序状态)

  • 最坏时间复杂度:O(\(n^2\))

  • 稳定性:稳定

希尔排序

希尔排序(Shell Sort)是插入排序的改进, 排序非稳定。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

def shell_sort(alist):
    
    n = len(alist)
    gap = n//2
    
    # gap 变化到0之前,插入算法之行的次数
    while gap > 0:
        
        # 希尔排序, 与普通的插入算法的区别就是gap步长
        for i in range(gap,n):
            j = i
            while alist[j] < alist[j-gap] and j > 0:
                alist[j], alist[j-gap] = alist[j-gap], alist[j]
                j-=gap
    
        gap = gap//2

    return alist

复杂度与稳定性

  • 最优时间复杂度:\(O(n^{1.3})\) (不要求本身有序)

  • 最坏时间复杂度:\(O(n^2)\)

  • 稳定性:不稳定

快速排序

快速排序(Quicksort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

步骤为:

  1. 从数列中挑出一个元素,称为"基准"(pivot)

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

常见排序算法效率比较



相关文章

python速学教程(入门到精通)
python速学教程(入门到精通)

python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
创客贴AI

创客贴AI是一款AI图像与设计工具,AI辅助的智能在线设计工具。

讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

二狗PPT
二狗PPT Hot

一款AI演示文稿工具,主要用于专为中式职场打造的AI PPT生成工具,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

花生AI
花生AI Hot

一款AI视频创作工具,主要用于B站推出的AI视频创作工具,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

0

2026.11.17

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

0

2026.11.17

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

0

2026.11.17

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

0

2026.11.17

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

0

2026.11.17

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

0

2026.11.17

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

160

2026.11.12

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

120

2026.11.12

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

100

2026.11.12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn