编程学习网 > 编程语言 > Python > python树形教程(Python树形选择排序)
2023
07-14

python树形教程(Python树形选择排序)


选择排序里面主要讲了三个排序,分别是简单选择排序、树形选择排序、堆排序。今天这篇文章主要讲树形选择排序,树形选择排序也被称为锦标赛排序,树形选择排序运用了锦标赛的思想进行排序,树形选择排序是指首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进行两两比较,如此重复,直至选出最小的记录为止。

问题描述
给定一个序列,我们将如何用树形选择排序来将它排序呢,下面将结合图形和文字一起讲述。
示例1:对数据表A=(73,45,79,90,81,75,94,97)进行排序
输出:45 73 75 79 81 90 94 97
解决方案
数据表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用无穷符号代替,又重复上面的操作,直到对所有数据排完序。如下图所示

结语

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

以上就是python树形教程(Python树形选择排序)的详细内容,想要了解更多Python教程欢迎持续关注编程学习网。

扫码二维码 获取免费视频学习资料

Python编程学习

查 看2022高级编程视频教程免费获取