Python 选择排序中的树形选择排序
作者:李欣容 发布时间:2023-06-10 04:33:32
1、引言
选择排序里面主要讲了三个排序,分别是简单选择排序、树形选择排序、堆排序。今天这篇文章主要讲树形选择排序,树形选择排序也被称为锦标赛排序,树形选择排序运用了锦标赛的思想进行排序,树形选择排序是指首先对n个记录的关键字进行两两比较,然后在n/2
个较小者之间再进行两两比较,如此重复,直至选出最小的记录为止。
2、问题描述
给定一个序列,我们将如何用树形选择排序来将它排序呢,下面将结合图形和文字一起讲述。
示例1:对数据表A=(73,45,79,90,81,75,94,97)进行排序
输出:45 73 75 79 81 90 94 97
3、解决方案
数据表A是乱序的,现在需要将它按照从小到大的顺序排序好,根据树形选择排序的思想首先需要将比较的记录全部作为叶子,然后按照从左到右的顺序,两两进行比较,选出最小的那个,然后将比较后的n/2个元素又按照从左到右的顺序两两进行比较,选出最小的,一直重复这样操作后,会从底向上形成一个完全二叉树。可能读完这段文字还是不好理解,下面我将用图示来具体描述。
1.构建二叉树:图1是数据表A构成的二叉树,首先直接将数据表A的数据直接放在最下面,也就是二叉树的叶子;然后从左到右两两进行比较,例如73和45比较后选出最小的45,79和90比较后选出最小的79,将选出的45和79比较选出最小的45,一直这样重复操作,直到构成一个完整的二叉树。
2. 如何输出正确顺序:根据图1可以知道根节点是45,也就是最小的。图2就是把第一遍找出来的45用无穷符号代替,然后又两两比较,直到根节点变为最小的,通过图1和图2对比可以看出第一遍找到的最小的是45,第二遍是73,,现在又将找出来的73用无穷符号代替,又重复上面的操作,直到对所有数据排完序。如下图所示
4、结语
树形选择排序还是比较好理解,图和文字结合就比较容易结合。
猜你喜欢
- 一、下载安装包http://www.php.net/downloads.php获取下载地址wgethttp://hk1.php.net/di
- 大名鼎鼎的FCKeditor终于在最近发布新版本了,与增加版本号不同,这次完全把它改名了,更名为CKeditor。这应该是和它的开发公司CK
- 对于刚刚学习编程的同学来说对编程是非常陌生的,对很多的代码也是非常陌生,高中忙于学习的我们甚至可以说是对编程是一无所知,进入大学进入到这个专
- 本文实例讲述了php版银联支付接口开发的方法。分享给大家供大家参考,具体如下:支付接口现在有第三方的支付接口也有银行的支付接口。这里就来介绍
- <% dim result,result1 str="ad_asp之家_nzlkjlkfjoj
- 在运维场景下,我们经常需要在服务器上用正则表达式来匹配IP地址。shell和其它编程语言一样,也可以使用正则分组捕获,不过不能使用 $1或\
- 如果没有设置分页,django-rest-framework 会将所有资源类表序列化后返回,如果资源很多,就会对网站性能造成影响。为此,我们
- 为什么页面出现乱码?为什么数据库里出现乱码?为什么这些乱码的出现几率飘忽不定了?诸如此类的乱码问题困扰了很多WEB开发人员。假如不将这背后的
- 前言上一次简单了解了协程的工作原理 前文链接最后提到了几个使用协程时会遇到的问题,其中一个就是主线程不会等待子线程结束,在这里记录两种比较简
- 本文实例讲述了python复制文件的方法。分享给大家供大家参考。具体分析如下:这里涉及Python复制文件在实际操作方案中的实际应用以及Py
- 脚本内容代码如下:from mitmproxy import http, ctxfrom multiprocessing import Lo
- 本文实例实现的功能是监控一个文件或目录的变化,如果有变化,把文件上传备份至备份主机,并且要监控上传过程是否有问题等,具体内容如下#!/usr
- 无论是公司的同事还是外界的程序员朋友们,大部分人对JavaScript的高级应用不甚了解,已有的知识架构里会认为JavaScript仅仅是一
- 图片的宽度和高度是未知的,没有一个固定的尺寸,在这个前提下要使图片在一个固定了宽度和高度的容器中垂直居中,想想感觉还是挺麻烦的,由于最近的项
- 如代码1所示: // 代码 1 // 外观层类 class LWordHomePage { // 添加留言 public function
- 由于日期存在不同位数的月份或天数,出现参差不齐,既不美观也在日期比较时不好操作。如使用本涵数就会排列整齐:'================
- 人们对于那些抄袭模仿的网站有诸多抱怨,但在这篇文章中,却没有冷嘲热讽的意思。但正如他们所说,“模仿是最为忠诚的奉承形式”。“如果你确实需要借
- 前些日子有网友问:将ASP纪录集输出成n列的的表格形式显示的方法?现在写了一个,方便大家使用。'定义变量 Dim cn,r
- 本文实例讲述了PHP cookie,session的使用与用户自动登录功能实现方法。分享给大家供大家参考,具体如下:cookie的使用//生
- 本文是关于人物角色的一些简单介绍,感谢瑶芝同学提供的大力帮助! 人物角色(Personas)作为一种技术