//堆排序 

void swap(int& a,int &b)
{
 int tmp = a;
 a = b;
 b = tmp;
}
void siftAdjust(int elem[],int low,int high)
{
 for(int f=low,i=2*low+1;i<=high;i=2*i+1)
 { 
  if(i<high && elem[i]<elem[i+1])
  {
   i++;
  }
  if(elem[f]>elem[i])
  {
   break;
   } 
   swap(elem[f],elem[i]); 
   f = i;
 }
 } 
void heapSort(int elem[],int n)
{
 int i;
 for(i=(n-2)/2;i>=0;i--)
 {
 
  siftAdjust(elem,i,n-1);
 }
 for(int i=n-1;i>0;i--)
 {
  swap(elem[0],elem[i]);
   
  siftAdjust(elem,0,i-1);
  
  } 
}
 int main(void)
{
 int n = 10;
 int arr[10] = {0};
 for(int i=0;i<n;i++)
 {
  arr[i]=rand()%100;
 }
 for(int i=0;i<n;i++)
 {
  cout<<arr[i]<<" ";
 }
 cout<<endl; 
 heapSort(arr,n);
 for(int i=0;i<n;i++)
 {
  cout<<arr[i]<<" ";
 }
 return 0;
}
//复杂度说明： 其中构建初始堆经推导复杂度为o(n)，在交换并重建堆的过程中，需交换n-1次。而重建堆的过程中，根据完全二叉树的性质，交换次数为[log2(n-1),log2(n-2),...,1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是o(n*logn)。