大话数据结构-9.7 堆排序 - 高飞网

9.7 堆排序

2017-01-23 14:43:07.0

    堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆(图9-7-2左图示);或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆(图9-7-2右图示)。

9.7.1 堆排序算法

    堆排序(Heap Sort)就是利用堆进行排序的方法。基本思想是:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次小值。如此反复,便能得到一个有序序列了。

    如图9-7-4所示,图①是一个大顶堆,90为最大值,将90与20(末尾元素)互换,如图②所示,此时90就成了整个堆序列的最后一个元素,将20经过调整,使得除90之外的结点继续满足大顶堆定义(所有结点都大于等于其子孩子),见图③,然后再考虑将30与80互换……


    实现堆排序还需要解决两个问题:

  1. 如何由一个无序序列建成一个堆
  2. 在输出堆顶元素后,如何调整剩余元素成为一个新的堆
/* 对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
        int i;
        for(i=L->length/2;i>0;i--)
        {//把L中的r构成一个大顶堆
                HeapAdjust(L,i,L->length);
        }
        
        for(i=L->length;i>1;i--)
        {
                swap(L,1,i);//将堆顶记录和当前未经排序子序列的最后一个记录交换
                HeapAdjust(L,1,i-1);//将L->r[1..i-1]重新调整为大顶堆
        }
}


/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义 */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(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->r[j+1])
                {
                        ++j;/*j为关键字中较大的记录的下标*/
                }
                if(temp>=L->r[j])
                {
                        break;
                }
                L->r[s]=L->r[j];
                s=j;
        }
        L->r[s]=temp;
}


9.7.2 堆排序复杂度分析

    总体来讲,堆排序的时间复杂度为O(nlogn)。这在性能上远远好过冒泡、简单选择、直接插入的O(n2)。
    另外,由于初始构建堆所需的比较次数较多,因此,它并不适合待排序序列个数较少的情况。

上一篇:9.6 希尔排序 389
下一篇:9.8 归并排序 406