位置: 编程技术 - 正文

基于python的七种经典排序算法(推荐)(基于python的系统)

编辑:rootadmin

推荐整理分享基于python的七种经典排序算法(推荐)(基于python的系统),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:基于python的论文项目有哪些,基于python的系统,基于python的算法,基于python的应用,基于python的论文项目有哪些,基于python语言,基于python的论文项目有哪些,基于python的应用,内容如对您有帮助,希望把文章链接给更多的朋友!

一、排序的基本概念和分类

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。

排序的稳定性:

经过某种排序后,如果两个记录序号同等,且两者在原无序记录中的先后秩序依然保持不变,则称所使用的排序方法是稳定的,反之是不稳定的。

内排序和外排序

内排序:排序过程中,待排序的所有记录全部放在内存中

外排序:排序过程中,使用到了外部存储。

通常讨论的都是内排序。

影响内排序算法性能的三个因素:

时间复杂度:即时间性能,高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数 空间复杂度:主要是执行算法所需要的辅助空间,越少越好。 算法复杂性。主要是指代码的复杂性。

根据排序过程中借助的主要操作,可把内排序分为:

插入排序 交换排序 选择排序 归并排序

按照算法复杂度可分为两类:

简单算法:包括冒泡排序、简单选择排序和直接插入排序 改进算法:包括希尔排序、堆排序、归并排序和快速排序

以下的七种排序算法只是所有排序算法中最经典的几种,不代表全部。

二、 冒泡排序

冒泡排序(Bubble sort):时间复杂度O(n^2)

交换排序的一种。其核心思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序记录为止。

其实现细节可以不同,比如下面3种:

1.最简单排序实现:bubble_sort_simple

2.冒泡排序:bubble_sort

3.改进的冒泡排序:bubble_sort_advance

三、简单选择排序

简单选择排序(simple selection sort):时间复杂度O(n^2)

通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录进行交换。

通俗的说就是,对尚未完成排序的所有元素,从头到尾比一遍,记录下最小的那个元素的下标,也就是该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于,每一轮中比较了很多次,但只交换一次。因此虽然它的时间复杂度也是O(n^2),但比冒泡算法还是要好一点。

四、直接插入排序

直接插入排序(Straight Insertion Sort):时间复杂度O(n^2)

基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。

该算法需要一个记录的辅助空间。最好情况下,当原始数据就是有序的时候,只需要一轮对比,不需要移动记录,此时时间复杂度为O(n)。然而,这基本是幻想。

五、希尔排序

希尔排序(Shell Sort)是插入排序的改进版本,其核心思想是将原数据集合分割成若干个子序列,然后再对子序列分别进行直接插入排序,使子序列基本有序,最后再对全体记录进行一次直接插入排序。

这里最关键的是跳跃和分割的策略,也就是我们要怎么分割数据,间隔多大的问题。通常将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过:increment = int(increment/3)+1来确定“增量”的值。

希尔排序的时间复杂度为:O(n^(3/2))

六、堆排序

堆是具有下列性质的完全二叉树:

每个分支节点的值都大于或等于其左右孩子的值,称为大顶堆;

基于python的七种经典排序算法(推荐)(基于python的系统)

每个分支节点的值都小于或等于其做右孩子的值,称为小顶堆;

因此,其根节点一定是所有节点中最大(最小)的值。

如果按照层序遍历的方式(广度优先)给节点从1开始编号,则节点之间满足如下关系:

堆排序(Heap Sort)就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。(下面采用大顶堆的方式)

其核心思想是:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆的根节点。将它与堆数组的末尾元素交换,然后将剩余的n-1个序列重新构造成一个大顶堆。反复执行前面的操作,最后获得一个有序序列。

堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。

其初始构建堆时间复杂度为O(n)。

正式排序时,重建堆的时间复杂度为O(nlogn)。

所以堆排序的总体时间复杂度为O(nlogn)。

堆排序对原始记录的排序状态不敏感,因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。

空间复杂度上,只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的,因此,堆排序也是一种不稳定的排序方法。

此外,由于初始构建堆的比较次数较多,堆排序不适合序列个数较少的排序工作。

七、归并排序

归并排序(Merging Sort):建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序对原始序列元素分布情况不敏感,其时间复杂度为O(nlogn)。 归并排序在计算过程中需要使用一定的辅助空间,用于递归和存放结果,因此其空间复杂度为O(n+logn)。 归并排序中不存在跳跃,只有两两比较,因此是一种稳定排序。

总之,归并排序是一种比较占用内存,但效率高,并且稳定的算法。

八、快速排序

快速排序(Quick Sort)由图灵奖获得者Tony Hoare发明,被列为世纪十大算法之一。冒泡排序的升级版,交换排序的一种。快速排序的时间复杂度为O(nlog(n))。

快速排序算法的核心思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分继续进行排序,以达到整个记录集合的排序目的。

快速排序的时间性能取决于递归的深度。 当pivot_key恰好处于记录关键码的中间值时,大小两区的划分比较均衡,接近一个平衡二叉树,此时的时间复杂度为O(nlog(n))。 当原记录集合是一个正序或逆序的情况下,分区的结果就是一棵斜树,其深度为n-1,每一次执行大小分区,都要使用n-i次比较,其最终时间复杂度为O(n^2)。 在一般情况下,通过数学归纳法可证明,快速排序的时间复杂度为O(nlog(n))。 但是由于关键字的比较和交换是跳跃式的,因此,快速排序是一种不稳定排序。 同时由于采用的递归技术,该算法需要一定的辅助空间,其空间复杂度为O(logn)。

基本的快速排序还有可以优化的地方:

1. 优化选取的pivot_key

前面我们每次选取pivot_key的都是子序列的第一个元素,也就是lis[low],这就比较看运气。运气好时,该值处于整个序列的靠近中间值,则构造的树比较平衡,运气比较差,处于最大或最小位置附近则构造的树接近斜树。

为了保证pivot_key选取的尽可能适中,采取选取序列左中右三个特殊位置的值中,处于中间值的那个数为pivot_key,通常会比直接用lis[low]要好一点。在代码中,在原来的pivot_key = lis[low]这一行前面增加下面的代码:

如果觉得这样还不够好,还可以将整个序列先划分为3部分,每一部分求出个pivot_key,再对3个pivot_key再做一次上面的比较得出最终的pivot_key。这时的pivot_key应该很大概率是一个比较靠谱的值。

2. 减少不必要的交换

原来的代码中pivot_key这个记录总是再不断的交换中,其实这是没必要的,完全可以将它暂存在某个临时变量中,如下所示:

3. 优化小数组时的排序

快速排序算法的递归操作在进行大量数据排序时,其开销能被接受,速度较快。但进行小数组排序时则不如直接插入排序来得快,也就是杀鸡用牛刀,未必就比菜刀来得快。

因此,一种很朴素的做法就是根据数据的多少,做个使用哪种算法的选择而已,如下改写qsort方法:

4. 优化递归操作

可以采用尾递归的方式对整个算法的递归操作进行优化,改写qsort方法如下:

九、排序算法总结

排序算法的分类:

没有十全十美的算法,有有点就会有缺点,即使是快速排序算法,也只是整体性能上的优越,也存在排序不稳定,需要大量辅助空间,不适于少量数据排序等缺点。

七种排序算法性能对比

如果待排序列基本有序,请直接使用简单的算法,不要使用复杂的改进算法。 归并排序和快速排序虽然性能高,但是需要更多的辅助空间。其实就是用空间换时间。 待排序列的元素个数越少,就越适合用简单的排序方法;元素个数越多就越适合用改进的排序算法。 简单选择排序虽然在时间性能上不好,但它在空间利用上性能很高。特别适合,那些数据量不大,每条数据的信息量又比较多的一类元素的排序。

标签: 基于python的系统

本文链接地址:https://www.jiuchutong.com/biancheng/382426.html 转载请保留说明!

上一篇:Python序列操作之进阶篇(python序列结构总结)

下一篇:详解Python装饰器由浅入深

  • 企业所得税退税的会计分录怎么做
  • 科普一下发票知识
  • 电汇凭证的会计怎么做账
  • 调用系统服务出错核心征管后端
  • 增值税属于会计科目的什么
  • 支票撕碎了怎么办
  • 退休工资缴纳个人所得税税率表
  • 公益性捐赠税前扣除资格有效期
  • 劳务派遣公司税务
  • 营改增之前的房产出售税率
  • 财务费用利息收入借方为负数是什么意思
  • 实验用原材料的会计处理
  • 分公司单独做账吗
  • 广告制作费可以计入印刷费吗
  • 会计审计合同
  • 税审需要什么资料和材料
  • 以股权转让名义转让土地使用权
  • 委托加工代扣代缴的消费税如何计算
  • 汽车配件税收分类编码
  • 增值税发票专票有效期
  • 非居民企业租赁增值税
  • 年末商品库存属于什么指标
  • 主营业务成本与其他业务成本的区别
  • 软件开发行业的现状
  • 水利基金返还分录怎么写
  • 企业接受个人捐赠
  • win11更新22468
  • windows11怎么添加打印机驱动
  • rapapp.exe - rapapp是什么进程 有何作用
  • 做胃镜多少钱了
  • 缴纳公积金个人部分会计分录
  • 政府土地购买流程
  • 非居民所得税代扣代缴
  • 固定资产原值,净值,价值的区别
  • 子公司使用母公司授信
  • php session_start
  • 求源代码
  • 短期资金都是债务类资金
  • 两只小北极熊
  • 兼职人员需要
  • 现代服务印花税税率
  • 工程结算 增值税
  • 暂估入账会计科目
  • 代收代付业务
  • 招待费住宿费专票
  • 融资租赁业务应包括哪些
  • 金蝶k3如何设置现金流量表取数公式
  • 外聘专家机票能抵扣增值税吗
  • 外购固定资产对公司影响
  • 什么叫政府补贴学位生
  • 一般纳税人结转税额怎么做会计分录
  • 生产自己的产品
  • 应付账款借方余额负数表示什么
  • 货运代理的公司
  • 费用报销票据可以跨年吗
  • 农业公司土地租赁
  • 企业清算期间发生的各项费用应计入以下什么科目
  • 销售公司中的服务是什么
  • sql server 错误
  • windowsxp装机图片
  • xp系统如何加速
  • Winxp安装光盘修复
  • 电脑重装系统步奏
  • SmartFTP.exe - SmartFTP是什么进程
  • win10升级后无法进入系统一直重启
  • win10系统怎么关闭自动更新
  • linux 运行二进制文件
  • win10系统登录密码忘了怎么办
  • win10系统桌面图标有白色方框的解决方法图...
  • cocos2d-js教程
  • opencv是干嘛用的
  • perl中\s+
  • android获取位置信息
  • unity shooter
  • jQuery实现table中的tr上下移动并保持序号不变的实例代码
  • 终于实现的图片
  • bootstrap要学多久
  • android实现选择题模式
  • 税务检查工作方法有哪些
  • 进口柴油消费税是多少
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设