滴水逆向联盟

标题: VC++2012编程演练数据结构《34》树形选择排序 [打印本页]

---

作者: 大灰狼    时间: 2014-8-13 08:32
标题: VC++2012编程演练数据结构《34》树形选择排序
树形选择排序（Tree Selection Sort）
　　树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

　　这个过程可用一棵有n个叶子结点的完全二叉树表示。例如，图表2中的二叉树表示从8个数中选出最小数的过程。8个叶子结点到根接点中的关键字，每个非终端结点中的数均等于其左右孩子结点中较小的数值，则根结点中的数即为叶子结点的最小数。在输出最小数之后，割据关系的可传递性，欲选出次小数，仅需将叶子结点中的最小数（13）改为“最大值”，然后从该叶子接点开始，和其左（或右）兄弟的数值进行比较，修改从叶子结点到根的路径上各结点的数，则根结点的数值即为最小值。同理，可依次选出从小到大的所有数。由于含有n个子结点的完全二叉树的深度为log2n+1，则在树形选择排序中，除了最小数值之外，每选择一个次小数仅需要进行log2n次比较，因此，它的时间复杂度为O(nlogn)。但是，这种排序方法尚有辅助存储空间较多、和“最大值”进行多余比较等缺点。为了弥补，威洛姆斯（J. willioms）在1964年提出了另一种形式的选择排序——堆排序。

打开IDE

创建一个工程




声名如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
•   
• //锦标赛排序法  
• #include<iostream>  
• #include<iomanip>  
• #include<math.h>  
• //#include<math.h>  
• #include<stdlib.h>  
• #include<time.h>  
•   
• using namespace std;  
• class DataNode //胜者树结点的类定义  
• {public:  
• int data;//数据值  
• int index;//树中的结点号  
• int active;//参选标志  
• };  
• //锦标赛排序中的调整算法;i是表中当前  
• //最小元素的下标,即胜者.从它开始向上调整  
• void UpdataTree(DataNode *tree,int i)  
• {int j;  
• if(i%2==0) //i为偶数,对手为左结点  
• tree[(i-1)/2]=tree[i-1];//i为奇数,对手为右结点  
• else  
• tree[(i-1)/2]=tree[i+1];  
• i=(i-1)/2; //i上升到双亲结点位置  
• while(i)  
• {if(i%2==0) j=i-1;//确定i的对手为左结点还是右结点  
• else j=i+1;  
• if(!tree.active||!tree[j].active)//比赛对手中间有一个空  
• if(tree.active) tree[(i-1)/2]=tree;  
• else tree[(i-1)/2]=tree[j]; //非空者上升到双亲结点  
• else                         //比赛对手都不为空  
• if(tree.data<tree[j].data) tree[(i-1)/2]=tree;  
• else tree[(i-1)/2]=tree[j];//胜者上升到双亲结点  
• i=(i-1)/2; //i上升到双亲结点  
• }}  
• //建立树的顺序存储数组tree,将数组a[]中的元素复制到胜者树中,  
• //对它们进行排序,并把结果返回数组中,n是待排序元素个数  
• void TournmentSort(int a[],int n)  
• {DataNode *tree; //胜者树结点数组  
• DataNode item;  
• int m,i,j=0;  
• for(int k=0;k<n;k++)//计算满足>=n的2的最小次幂的数  
• {  
•     m=(int)pow((double) 2,(double)k);  
•     if(m>=n)  
•         break;  
• }  
• int bottomRowSize=m;  
• int TreeSize=2*bottomRowSize-1;//计算胜者树的大小:内结点+外结点数  
• int loadindex=bottomRowSize-1;//外结点开始位置  
• tree=new DataNode[TreeSize];  //动态分配胜者树结点数组空间  
• for(i=loadindex;i<TreeSize;i++)//复制数组数据到树的外结点中  
• {tree.index=i;//下标  
• if(j<n) {tree.active=1;tree.data=a[j++];}//复制数据  
• else tree.active=0; //后面的结点为空的外结点  
• }  
• i=loadindex;           //进行初始比较寻找最小的项  
• while(i)  
• {j=i;  
• while(j<2*i)          //处理各对比赛者  
• {if(!tree[j+1].active||tree[j].data<tree[j+1].data)  
• tree[(j-1)/2]=tree[j];  
• else tree[(j-1)/2]=tree[j+1];//胜者送入双亲  
• j+=2; //下一对参加比较的项  
• }  
• i=(i-1)/2;//i退到双亲,直到i=0为止  
• }  
• for(i=0;i<n-1;i++)//处理其他n-1个元素  
• {a=tree[0].data;//当前最小元素送数组a  
• tree[tree[0].index].active=0;//该元素相应外结点不再比赛  
• UpdataTree(tree,tree[0].index);//从该处向上修改  
• }  
• a[n-1]=tree[0].data;  
• }  
  

调用如下
[cpp] view plaincopy

• //锦标赛排序法的测试  
• void main()  
• {cout<<"运行结果:\n";  
• int n,b[100],i;  
• srand(time(0));  
• cout<<"输入待排序元素个数n:";cin>>n;  
• for(i=0;i<n;i++) b=rand()%100;  
• cout<<"排序前数组:\n";  
• for(i=0;i<n;i++)  
• cout<<setw(4)<<b;  
• cout<<endl;  
• TournmentSort(b,n);  
• cout<<"排序后数组:\n";  
• for(i=0;i<n;i++)  
• cout<<setw(4)<<b;  
• cout<<endl;  
• cin.get();cin.get();  
• }  
•    
  

运行如下

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2