堆排序简介

╰+攻爆jí腚メ 2022-11-21 09:55 120阅读 0赞

**1.基本思想：**  
堆排序（Head sort）就是利用堆（假设利用大顶堆）进行排序的方法。他的基本思想如下：  
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点，将他移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1 个序列重新够造成一个堆，这样就会得到n个元素中的值，如此反复便会得到一个有序序列。

**问题：  
1、如何由一个无序序列构建一个大顶堆？  
2、如果在输出堆顶元素后，调整剩余元素成为一个新的堆。**  
![在这里插入图片描述][20201031163551125.gif_pic_center]  
**2、代码演示**

/*对顺序表L进行堆排序*/
    void HeadSort(SqList *L)
    {
        
              int i;
              for(i=L->length/2;i>0;i--)//把L中的r构建成一个大顶堆
               HeadAdjust(L,i,L->length);
               for(i=L->length;i>1;i--)
               {
        
                  swap(L,1,i)//将堆顶记录和当前未经排序子序列的最后一个记录交换
                  HeadAjust(L,1,i-1);//将L->r[1...i-1]重新调整为大顶堆
    
    
             }
    }
    
    解释：
     第一个for 循环 构建一个大顶堆
     第二个for循环 逐步将每个最大值的根节点与末尾元素交换，并且再调整其为大顶堆

堆调整L->r\[s\]的关键字，使L->r\[s…m\]成为一个大顶堆

void HeadAdjust(SqList *L,int s,int m)
     {
        
        int temp,j;
        temp=L->r[s];
        for(j=2*s;j<=m;j*=2)//沿关键字较大的孩子结点向下筛选
        {
        
         if(j<m&& L->r[j]<L->[j+1])
         ++j;//j为关键字中较大的记录的下标
          if(temp>=L->r[j])
           break;// rc应插入在位置s上
         L->r[s]=L->r[j];
         s=j;  
    }
    
    L->r[s]=temp; //交换 s j
    
    
      }

**3.效率分析**  
运行时间主要消耗在初始构建堆和在重建堆时的反复筛选上。

构建整个堆的时间复杂度为O(n)  
重建整个堆的时间复杂度为O(nLogn)  
总体来说：堆排序时间复杂度为O(nLogn)

[20201031163551125.gif_pic_center]: /images/20221120/91782cc63f6942da87e9cd74dfc17d01.png