树形选择排序

来自计算思维百科
跳转至: 导航搜索
树形选择排序1.png

如果我们希望对很多数据按照从小到大或是从大到小的顺序重新放置,这就是排序。树形选择排序又称锦标赛排序,是一种按照锦标赛的思想进行选择排序的方法。

基本概念

树形选择排序首先对N个数据进行两两比较,然后在其中(N/2)个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可以用一棵用N个叶子结点的完全二叉树表示。

应用范围

所有需要进行排序的应用领域都可以使用树形选择排序。

使用方法及步骤

  1. 把N个数据分成N/2个较小的数据和N/2个较大的数据;
  2. 在N/2个较小的数据中重复步骤2;
  3. 直至最小的数据选出来;
  4. 在剩下的数据中重复上述过程。

应用案例

应用1- 锦标赛

案例:下图中最低层的叶子结点中8个选手之间经过第一轮的4场比赛之后选拔出4个优胜者“CHA” ”BAO”  “DIAO”  “WANG” ,然后经过两场半决赛和一次决赛之后,选拔出冠军“BAO”, 显然,按照锦标赛的传递关系,亚军只能产生于分别在决赛,半决赛和第一轮比赛中输给冠军的选手中,由此,在经过”CHA”,和”LIU”,  ”CHA”和”DIAO”的两场比赛之后,选拔出亚军“CHA”,同理,选拔殿军的比赛只要在”ZHAO“ ”LIU”和“DIAO” 3个选手之间进行即可。按照这种锦标赛的思想可导出树形选择结构。

树形选择排序2.png

a)选拔冠军的比赛程序

树形选择排序3.png

b)选拔亚军的两场比赛

树形选择排序3.png

c)选拔季军的两场比赛

可以体现的计算思维

树形选择排序将数据分成较小和较大两部分,在每个部分重复这个过程,体现了计算思维的递归思想。