ordering4.txt

堆排序:思想: 用二叉树的结构来表示数组,及用数组来表示二叉树的结构,比如i为父节点其孩子为,2i,和2i+1.其中,大顶堆中 父节点大于其两个孩子 算法平均时间复杂度: O(nlogn)

bool slipdown(int *array,int cur,int  n)
{
for(int next=2*cur;next<=n;next=2*cur)    //next表示cur的左孩子
{
  if(next<n&&array[next]<array[next+1])   //取cur的两个孩子的大者
   next++;
  if(array[next]<array[cur])      
   break;
  int temp=array[cur];       //交换cur和他孩子中的大者
  array[cur]=array[next];
  array[next]=temp;
  cur=next;          //令当前需要调整的关键字的位置cur=next
}
return true; 
}
bool heapsort(int *array,int n)
{ 
int temp;
for(int i=n/2;i>0;i--)       //将数组调整为大顶堆
  slipdown(array,i,n);
for(int N=n;N>1;N--)       //选出堆中最大元,存于N位置,循环进行
{
  temp=array[N];
  array[N]=array[1];
  array[1]=temp;
  slipdown(array,1,N-1);
}
return true;
}