位置: 编程技术 - 正文

基于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装饰器由浅入深

  • 纳税怎么理解
  • 农行公户怎么给公户转账
  • 外商投资企业国内上市最新政策
  • 个贷系统平账户
  • 以前年度损益调整科目怎么用
  • 防伪标识会有假的吗
  • 社保企业二次扣款怎么扣
  • 企业承担个人所得税的规定
  • 财产保险费发票税率
  • 机动车销售统一票据可以抵扣吗
  • 增值税税负低如何解释
  • 提供物业管理服务税率
  • 商业承兑汇票适用于
  • 分公司利润如何分红
  • 公司收到个人借款的现金流量
  • 库存现金进账单会计分录
  • 未确认收货可以评价吗
  • 缴纳海关进口增值税
  • 消费税什么时候用最高售价
  • 税务票开错了怎么办理退税
  • 出口发票上的汇率按哪个开?
  • 经营费用包括哪些内容
  • 公司员工结婚礼金规定
  • vmware15虚拟机
  • bios咋进入
  • cmd telnet命令大全
  • 如何更改应用商店
  • Laravle eloquent 多对多模型关联实例详解
  • vue组件相互引入
  • 电脑bios找不到vt
  • 代发工资如何合理避税
  • 农产品增值税进项税额
  • 增值税纳税义务人
  • 解决打呼噜只需一杯水
  • 低值易耗品报废时有残料价值收回的应冲减当月成本费用
  • 教你学python
  • cat 开源
  • 深究Python中的asyncio库-线程并发函数
  • 高价值配件用入固定资产吗
  • 注册资本实缴后可以减资吗
  • input和printf的区别
  • js中var的用法
  • 帝国cms适合建什么站
  • 所得税汇算清缴退税会计分录怎么做
  • 研发费用计入科目
  • 结转应交税金的分录
  • 限定性净资产是资产类科目吗
  • 一般纳税人怎么开3个点普票
  • 小规模纳税人免税额度是多少
  • 外购商品发放给员工 进项税额能不能抵扣
  • 防伪税控开票系统年费
  • 消费税在企业所得税前扣除吗
  • 其他综合收益和营业外收入的区别
  • 应付职工薪酬的含义
  • 租单位的房子怎么办营业执照
  • 不征税收入怎么申报增值税
  • 购买固定资产的运费计入什么科目
  • 结转收入及成本费用
  • 会计处理要求
  • 三包适用范围
  • 车辆使用费怎么算
  • 折扣的种类有哪几种
  • 硕士研究生个税专项扣除
  • 贷款的融资担保费
  • 酒店代金券是什么意思
  • 注册资本实缴后钱怎么出来
  • 报销单粘贴单
  • 营改增后建筑行业进项税能抵扣吗
  • mysql无法配置
  • windows 地址解析命令
  • win7系统如何隐藏桌面
  • linux 软件 安装
  • 苹果电脑dashboard什么意思
  • win8.1专业版是哪个
  • ubuntu系统怎么用
  • windows8开机启动项在哪里设置
  • 固定栏跑到了左边怎么弄
  • jquery中的css方法
  • 宁波国家税务局电子税务局
  • 开采砂石
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设