《树形选择排序》PPT课件.ppt

《《树形选择排序》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树型选择排序(TreeSelectionSort)锦标赛排序(TournamentSort)它的思想与体育比赛时的淘汰赛类似。首先将n个对象的排序码进行两两比较,得到n/2个比较的优胜者(排序码小者),作为第一步比较的结果保留下来；然后对这n/2个对象再进行排序码的两两比较,…,如此重复,直到选出一个排序码最小的对象为止。在图例中,最下面是对象排列的初始状态,相当于一棵满二叉树的叶结点,它存放的是所有参加排序的对象的排序码。如果n不是2的k次幂，则让叶结点数补足到满足2k-1

2、点排序码两两比较的结果，最顶层是树的根。08Winner2108086325*2121254925*160863胜方树的概念每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，称这种比赛树为胜方树。位于最底层的叶结点叫做胜方树的外结点，非叶结点称为胜方树的内结点。每个结点除了存放对象的排序码key外，还存放了此对象是否要参选的标志Active和此对象在满二叉树中的序号index。胜方树最顶层是树的根，表示最后选择出来的具有最小排序码的对象。08Winner(胜者)2108086325*2121254925*160863tree

3、[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]tree[15]形成初始胜方树（最小排序码上升到根）a[1]排序码比较次数:7VS.VS.VS.VS.VS.VS.upup对手不参选VS.比较16Winner(胜者)2116166325*2121254925*1663输出冠军并调整胜方树后树的状态a[2]排序码比较次数:2VS.VS.upup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]tree[15]

4、21Winner(胜者)21636325*2121254925*63输出亚军并调整胜方树后树的状态a[3]排序码比较次数:1VS.upup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]tree[15]25Winner(胜者)25636325*25254925*63输出第三名并调整胜方树后树的状态a[4]排序码比较次数:2VS.VS.upup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]t

5、ree[14]tree[15]25*Winner(胜者)25*636325*4925*63输出第四名并调整胜方树后树的状态a[5]排序码比较次数:1VS.upup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]tree[15]49Winner(胜者)496363494963输出第五名并调整胜方树后树的状态a[6]排序码比较次数:1VS.upupup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[1

6、3]tree[14]tree[15]63Winner(胜者)636363全部比赛结果输出时树的状态a[7]排序码比较次数:0upup对手不参选VS.比较tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]tree[15]树形选择排序构成的胜方树是满二叉树,其深度为log2n,其中n为待排序元素个数。除第一次选择具有最小排序码的对象需要进行n-1次排序码比较外,重构胜方树选择具有次小、再次小排序码对象所需的排序码比较次数为O(log2n)。总排序码比较次数为O(nlog2n)

7、。对象的移动次数不超过排序码的比较次数，所以树形选择排序总时间复杂度为O(nlog2n)。这种排序方法减少了许多排序时间,但是使用了较多的附加存储。如果有n个对象，必须使用至少2n-1个结点来存放胜方树。最多需要找到满足2k-1