Python 选择排序中的树形选择排序

目录
  • 1、引言
  • 2、问题描述
  • 3、解决方案
  • 4、结语

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、结语

树形选择排序还是比较好理解，图和文字结合就比较容易结合。

到此这篇关于Python 选择排序中的树形选择排序的文章就介绍到这了,更多相关Python 树形选择排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python tkinter 树形列表控件(Treeview)的使用方法

    Python tkinter 树形列表控件(Treeview)的使用方法

    1.方法 方法 描述 bbox(item, column=None) 返回指定item的框选范围,或者单元格的框选范围 column( cid, option=None, **kw) 设置或者查询某一列的属性 delete(*items) 删除指定行或者节点(含子节点) vdetach(*items) 与delete类似,不过不是真正删除,而是隐藏了相关内容.可以用move方法重新显示v exists(item) 判断指定的item是否存在 focus(item=None) 获得选定item的i

  • Python 实现选择排序的算法步骤

    选择排序算法步骤: 找到数组中最小的那个元素中, 将它和数组的第一个元素交换位置, 在剩下的元素中找到最小的元素,将它和数组的第二个元素交换位置, 如此往复,知道将整个数组排序. 逐步分析: 假设一个数组有 6 个元素, [5, 1, 4, 3, 2, 6] 第 1 个元素为 5,与剩余 5 个元素相比,1 是最小的元素,所以 5 和 1 交换位置, [1, 5, 4, 3, 2, 6] 第 2 个元素为 5,与剩余 4 个元素相比, 2 是最小的元素,所以 5 和 2 交换位置, [1, 2,

  • Python如何生成树形图案

    Python如何生成树形图案

    本文实例为大家分享了Python生成树形图案的具体代码,供大家参考,具体内容如下 先看一下效果,见下图. 上面这颗大树是使用Python + Tkinter绘制的,主要原理为使用分形画树干.树枝,最终叶节点上画上绿色圆圈代表树叶.当然,为了看起来更真实,绘制过程中也加入了一些随机变化,比如树枝会稍微有些扭曲而不是一条直线,分叉的角度.长短等都会随机地作一些偏移等. 以下是完整源代码: # -*- coding: utf-8 -*- import Tkinter import sys, rando

  • Python排序算法之选择排序定义与用法示例

    Python排序算法之选择排序定义与用法示例

    本文实例讲述了Python排序算法之选择排序定义与用法.分享给大家供大家参考,具体如下: 选择排序 选择排序比较好理解,好像是在一堆大小不一的球中进行选择(以从小到大,先选最小球为例): 1. 选择一个基准球 2. 将基准球和余下的球进行一一比较,如果比基准球小,则进行交换 3. 第一轮过后获得最小的球 4. 在挑一个基准球,执行相同的动作得到次小的球 5. 继续执行4,直到排序好 时间复杂度:O(n^2).  需要进行的比较次数为第一轮 n-1,n-2....1, 总的比较次数为 n*(n-1

  • Python实现插入排序和选择排序的方法

    话不多说,让我们从最基本的排序算法开始吧 插入排序 如下图所示,插入排序的实现思路顾名思义,就是 不断地在一个已经是有序的数组中,寻找合适位置并插入新元素 . 具体实现步骤为: 首先我们把整个数组拆分为有序区间和未排序区间,有序区间在插入排序一开始只有一个元素,就是数组的第一个元素. 接在有序区间之后的一个元素就是准备插入的元素,在图中就是标为绿色的元素,在有序区间内寻找位置并插入. 其寻找逻辑为:从后往前依次进行比较,如果待插入元素大于当前元素,则将待插入元素插入到当前元素的后一位,如果待插入

  • Python排序搜索基本算法之选择排序实例分析

    Python排序搜索基本算法之选择排序实例分析

    本文实例讲述了Python排序搜索基本算法之选择排序.分享给大家供大家参考,具体如下: 选择排序就是第n次把序列中最小的元素排在第n的位置上,一旦排好就是该元素的绝对位置.代码如下: # coding:utf-8 def selectionSort(seq): length=len(seq) for i in range(length): mini=min(seq[i:]) if seq[i]>mini: j=seq.index(mini,i) seq[i],seq[j]=seq[j],seq[

  • python GUI库图形界面开发之PyQt5树形结构控件QTreeWidget详细使用方法与实例

    PyQt5树形结构控件QTreeWidget简介 QTreeWidget 类根据预设的模型提供树形显示控件. QTreeWidget 使用类似于 QListView 类的方式提供一种典型的基于 item 的树形交互方法类,该类基于QT的"模型/视图"结构,提供了默认的模型来支撑 item 的显示,这些 item 类为 QTreeWidgetItem 类. 如果不需要灵活的"模型/视图"框架,可以使用QTreeWidget 来创建有层级关系的树形结构.当把标准 ite

  • Python实现的插入排序，冒泡排序，快速排序，选择排序算法示例

    本文实例讲述了Python实现的插入排序,冒泡排序,快速排序,选择排序算法.分享给大家供大家参考,具体如下: #!/usr/bin/python # coding:utf-8 #直接插入排序 def insert_sort(list): for i in range(len(list)): Key = list [i] #待插入元素 j = i - 1 while(Key < list[j] and j >= 0): list[j+1] = list[j] #后移元素 list[j] = Ke

  • 一行python实现树形结构的方法

    定义 使用内置的defaultdict 我们可以很容易的定义一个树形数据结构 def tree(): return defaultdict(tree) example: json风格 users = tree() users['harold']['username'] = 'bell' users['handler']['username'] = 'master' 我们可以使用print(json.dumps(users))以json的形式输出,于是我们看到 {'harold': {'usern

  • python实现树形打印目录结构

    本文实例为大家分享了python树形打印目录结构的具体代码,供大家参考,具体内容如下 前言 这两天整理数据文件的时候发现,一层层的点击文件夹查看很繁琐,于是想写一个工具来递归打印出文件目录的树形结构,网上找了一些资料几乎都是使用的os.walk, 调试了以后发现返回的貌似的是一个"生成器",只需要for循环即可,可是这样得到的好像是BFS的结构,并不是我想要的树形结构,最后终于发现了os.listdir这个函数,可是使用它来写一个深度优先搜索,只要递归调用就能解决我的问题. 代码 #!

随机推荐