堆排序有关,主要是代码的理解

  1. 需要的基础知识:

    1. 大(小)顶堆(后面统一用大顶堆进行总结)是一棵完全二叉树,性质:每个结点的值都大于或等于其左右孩子节点的值。
    2. 完全二叉树,编号为i的结点,其左右孩子的编号为2i与2i+1
  2. 堆排序算法

    1. 思想:将待排序数组构造为大顶堆,然后移走最大的元素(根节点),剩下的再重新构造为大顶堆,反复执行(算法的优点:每次选择都充分利用前一趟选择的比较结果)
    2. 步骤:先将最开始的序列通过堆调整(HeapAdjust)使之成为大顶堆,然后每次将堆顶记录(最大)与堆底部(可能为最小)的 值进行交换,交换后再进行堆调整(HeapAdjust)
    3. 关键:从上的分析可以看出,算法的关键是HeapAdjust函数,值得注意的是HeapAdjust函数是对节点考虑往下筛选,其经过一步循环调整的基本结构为一个父亲结点以及他的左右儿子结点。如果需要交换,则一定是结点跟其左右儿子结点其中之一对换,所以只要再次考虑有进行操作交换的那个儿子结点,另一个儿子结点的结构并不会被破坏。
  3. HeapAdjust函数

    从i结点考虑,对2i结点和2i+1结点进行考虑,使其满足大顶堆,如果进行了交换操作,再对进行操作的儿子结点进行重新的结构调整,直到调整到叶子结点。

    void HeapAdjust(List *L,int s,int m)//L中的r[]为待排序序列,s为需要调整的结点编号,m为需要排序的数量//
    {
        int temp,j;//temp用来记录结点的值//
        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;//节点是最大的,那就不需要调整(他的下面的结构都已经调整完毕)
            L->r[s]=r[j];//如果节点不是最大的,那就将最大的值赋值给他,注意temp一直等于根节点//
            s=j;//接下来对这个  给父节点进行了赋值的结点   进行考虑//
        }
        L->r[s]=temp;//将根节点的值插入到合适的位置//
    }
    
  4. 进行根节点与末尾结点调整之后,对顶点进行HeapAdjust

  5. 堆排序的时间复杂度:O(nlog2N)最坏的情况下也为O(nlog2N)比较和交换是跳跃式进行,所以也是不稳定的排序。