选择排序（二）--树形选择排序

利用满二叉树的性质，思想:将输入的数据存放到满二叉树的叶节点，通过比较树中剩余可用节点（从底层的叶节点开始）的大小，每次选择最小的数值（比较复制到二叉树的顶端），并且把最小数值赋给排序数组的前端，把最小数值原来叶节点的位置设置为不可用；依次循环直至最后一个可用叶节点。

一、满二叉树和完全二叉树区别如图：

二、程序讲解：

template
class TreeNode{
public:
T data;
int index;
int active;
TreeNode & operator=(TreeNode & treenode)
{
this->data=treenode.data;
this->index=treenode.index;
this->active=treenode.active;
return *this;
}
};
树节点数据结构包括了data数值，index用来存放该数值在叶节点存放的位置（所有数据开始都是存放在叶节点），active表示激活没有，最后如果该数据移植树根部，则将active字段置0无效。

/*2)树形排序 */
template <class T>
void ChangeTree(TreeNode<T> * tree,int i)
{
	if(i%2==0)
		tree[(i-1)/2]=tree[i-1];
	else
		tree[(i-1)/2]=tree[i+1];
	i=(i-1)/2;
	int j;
	while(i)
	{
		if(i%2==0)
			j=i-1;
		else
			j=i+1;
		if(!tree[i].active || !tree[j].active)
			if(tree[i].active)
				tree[(i-1)/2]=tree[i];
			else
				tree[(i-1)/2]=tree[j];
		else
			if(tree[i].data<tree[j].data)
				tree[(i-1)/2]=tree[i];
			else
				tree[(i-1)/2]=tree[j];
		i=(i-1)/2;
	}
}
int Power(int n)
{
  int result=1;
  if(n>=1)
  {
	  for(int i=1;i<=n;i++)
		  result *=2;
	  return result;
  }
  else 
	  return 1;
}
int LeapNum(int n) //计算满足满二叉树的叶子节点数
{
	for(int i=1;i<100;i++)
		if(Power(i-1)<n && n<Power(i)) 
			return Power(i);  // i 为层数， Power(i) 为叶节点数
		else if(Power(i-1)==n)
			return Power(i-1);
}
int log(int n)
{
	for(int i=1;i<100;i++) 
		if(Power(i-1)==n)
			return i-1;
	return -1;
}
template<class T>
void DisplayTree(TreeNode<T> tree[],int size)
{
int temp=0,biggestGap,gap;
biggestGap=(size+1)/2-1;
	for(int i=0;i<size;i++)
	{
		if((log(i+1))!=-1)
		{	cout<<"/n";
			gap=biggestGap;
			for(int k=0;k<temp;k++)
			   gap=(gap-1)/2;
			for(int j=0;j<gap;j++)
			    cout<<"   ";
			temp++;
		}
		if(tree[i].active)
		  cout<<tree[i].data<<"   ";
		else
			cout<<"#  ";
	}
}
template<class T>
void TreeSort(T a[],int n)
{
	TreeNode<T> * tree;
	int bottsize=LeapNum(n); //满二叉树的底层叶子数，必须为 满二叉树
	int size=2*bottsize-1; //满二叉树中结点总数
	int externalIndex=bottsize-1; //开始进行比较的节点位置
	tree=new TreeNode<T> [size];
	assert(tree);
	int j=0;
	int i;
	for( i=externalIndex;i<size;i++)
	{
		tree[i].index=i;
		if(j<n)
		{
			tree[i].active=1;		//设置访问标志，1可以访问
			tree[i].data=a[j++];    //载入数据
		}
		else
			tree[i].active=0;  //额外设置的节点，不可访问
	}
	i=externalIndex;	//externalIndex用来指向树的叶节点的最左部分的位置，i每次往上一层的最左位置移动
	while(i)           //比较找到最小节点
	{
       j=i;
	   while(j<2*i)
	   {
		
		  if(!tree[j+1].active || tree[j].data <= tree[j+1].data)
		  {
		       if(!tree[j+1].active && !tree[j].active)
		       {
				   tree[(j-1)/2].active=0; //其孩子节点都是额外节点，不可访问
			   }
			   tree[(j-1)/2]=tree[j];  //较小节点赋值给其双亲节点
		  }
		  else
			  tree[(j-1)/2]=tree[j+1];
		  j+=2;
	   }
	   i=(i-1)/2;
	}
	for(i=0;i<n-1;i++)   //处理前面n-1个节点
	{
		DisplayTree(tree,size);//zhou add 
		a[i]=tree[0].data;          
		tree[tree[0].index].active=0;//不在参加比较
		ChangeTree(tree,tree[0].index);//修改树形结构，使得参加比较的最小的数据移到树根部
	}
	DisplayTree(tree,size);//zhou add 
	a[n-1]=tree[0].data;  //数值最大的节点
}
template <class T>
void Output(T a[],int n)
{
	for(int i=0;i<n;i++)
		cout<<a[i]<<"/t";
	cout<<"/n";
}

具体的程序每次交换的输出如下,

输入数据时：1541,54, 89,345 , 416,1

#表示叶节点处无效的位置，

一次排序后参加排序（有效的）的数据移到最顶端（树根）