堆排序

1、堆定义：堆就是左右孩子小于或者大于父节点  

2、排序思想：

堆排序使用一种称为“筛”的运算进行节点数据的调整，直到使节点最后满足堆的条件。

已调整A[i]

1) q

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

• 父节点i的左子节点在位置 (2*i+1);
• 父节点i的右子节点在位置 (2*i+2);
• 子节点i的父节点在位置 floor((i-1)/2);

  

   

    

     

    
    

     

      #include <cstdlib>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       0 1 2 3 4 5 6
     
    
   

    

     

    
    

     

       子树的索引 j = 2*i+1 
     
    
   

    

     

    
    

     

       0
     
    
   

    

     

    
    

     

       1___|____2
     
    
   

    

     

    
    

     

       3_|_4 5_|_6
     
    
   

    

     

    
    

     

      */ 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      void HeapAdjust(int a[],int s,int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      int j ,t;
     
    
   

    

     

    
    

     

      while(2*s+1<n){//第s个节点有左子树 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //让 j 指向子树中较大的一个 
     
    
   

    

     

    
    

     

       j= 2*s+1;
     
    
   

    

     

    
    

     
 if((j+1)<n){//有右子树 
     
    
   

    

     

    
    

     
 if(a[j]<a[j+1])//右子树比较大
     
    
   

    

     

    
    

     

       j++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //交换 
     
    
   

    

     

    
    

     
 if(a[s]<a[j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       t = a[s];
     
    
   

    

     

    
    

     

       a[s] = a[j];
     
    
   

    

     

    
    

     

       a[j] = t;
     
    
   

    

     

    
    

     

       s = j; 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else//不需要调整了 
     
    
   

    

     

    
    

     
 break; 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void HeapSort(int a[],int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int t,i,j;
     
    
   

    

     

    
    

     
 for(i = n/2-1;i>=0;i--)//从最末级开始调整 
     
    
   

    

     

    
    

     

       HeapAdjust(a,i,n);//建堆
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for(i = n-1;i>=0;i--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       t = a[0];
     
    
   

    

     

    
    

     

       a[0] = a[i];
     
    
   

    

     

    
    

     

       a[i] = t;
     
    
   

    

     

    
    

     

       HeapAdjust(a,0,i); 
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     

      int main(int argc, char *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int a[] = {1,6,2,77,4,99,5};
     
    
   

    

     

    
    

     

       HeapSort(a,7);
     
    
   

    

     

    
    

     
 for(int i =0;i<7;i++){
     
    
   

    

     

    
    

     
 cout<<a[i]<<" ";
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     
 cout<<endl;
     
    
   

    

     

    
    

     

       system("PAUSE");
     
    
   

    

     

    
    

     
 return EXIT_SUCCESS;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: gamwatcher.blog.csdn.net，作者：香菜聊游戏，版权归原作者所有，如需转载，请联系作者。

原文链接：gamwatcher.blog.csdn.net/article/details/9323109