堆排序

　　堆排序是另一种基于选择的排序方法。它是一种树形选择排序，利用了堆顶记录的关键字最大（或最小）这一特征，使得当前无序去中选取最大或（最小）关键字变得简单。

　　堆的定义：有n个元素组成的序列{k₀, k₁, k₂, k₃, ……, k_n-2, k_n-1 },当且仅当满足关系： k_i<= k_2i+1 且 k_i<= k_2i+2 （或者 k_i>= k_2i+1 且 k_i>= k_2i+2）其中i = 0,1,2,……，[(n/2]-1时，称之为堆。例如序列{47, 35, 27, 26, 18, 7, 13, 19} 就满足上面的条件，这个序列就是一个堆。

　　若将堆看成是一棵以k₀为根的完全二叉树，则，这棵完全二叉树的每个非终结点的值均不大于（或小于）其左、右孩子结点的值。由此可以看出，若一个完全二叉树是堆，则根节点一定是这n个结点中的最小值或最大值。

　　堆排序的基本思想是：首先将待排序的记录序列构造一个堆。此时选出了堆中所有记录的最大者（或最小者），然后将它从堆中移走，将剩余的记录再调整成堆，有找出次大者，以此类推，直到堆中只剩下一个元素，出堆的记录顺序就是一个有序序列。

　　堆排序涉及到建堆和出堆两个过程，我们可以把每个过程都看作是对堆的调整。我们假定当前要调整的结点的下角标为K（从零开始算），堆最后的一个结点下角标m，那我们的调整过程是指使得以结点K为根节点的子树满足堆的条件。如果每个结点都满足堆的条件，那么整个序列自然就是一个堆。因此我们可以把调整描述为：

　　（1）设置两个指针 i 和 j， i 指向当前的结点 i = K， j 指向当前节点的左孩子 j = 2* i + 1；

　　（2）选取当前结点的左右孩子的值，选取较大值（或较小值），并用 j 指向该孩子的结点；

　　　　　　if( j <= m && j+1 <= m && a[j] < a[j+1] ) j++;

　　（3）用当前结点的值比较j所指向的结点的值，根据比较的结果，结束调整（满足堆的条件）或交换结点内容（调整当前结点的值）并继续调整（子结点）

　　建堆的过程可以这样理解，选取序列的中间节点（假定结点个数为n，那么中间节点的索引为[n/2]-1 (从零开始)），那么这个节点之后的结点在堆中一定是作为他们的后续子节点的索引号超过 n。如果调整中间结点前的所有结点，那么整个序列将变成一个堆。

　　参考代码：

#include <stdio.h>

#define MAX_NUM 80

void sift(int* a, int k, int m)
{
    int i = k;
    int j = 2*i+1;
    
    
    while(j <=m)
    {
        int temp = a[i];
        if(j <= m && j+1 <= m && a[j] < a[j+1]) j++;
        if(a[i] > a[j]) break;
        else
        {
            a[i] = a[j];
            a[j] = temp;
            i = j;
            j = 2*i + 1;            
        }    
    }
    for(int i = 0; i <=m ;i++)
    {
        printf("%d ",a[i]);
    } 
    printf("
");
    
}

void heapsort(int* a, int n)
{
    int h = n/2;
    
    printf("建堆过程：
");
    for(int i = h-1; i >=0; i--)  //建初始堆，从最后一个非终结点至根节点 
        sift(a,i,n-1);
    
    printf("
");
    printf("堆调整过程
"); 
    for(int i = n-1; i > 0;i--)  // 重复执行移走堆顶节点及重新构建堆的操作 
    {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        sift(a,0,i-1);
    }
    
    printf("最后排序的结果：
");
    
    for(int i = 0; i < n ;i++)
    {
        printf("%d ",a[i]);
    } 
    printf("
");
    
}

int main(int argc,char* argv[])
{
    int a[MAX_NUM];
    int n;    

    printf("Input total numbers: ");
    scanf("%d",&n);

    if( n > MAX_NUM ) n = MAX_NUM;
    
    for(int i = 0; i < n;i++)
    {
        scanf("%d",&a[i]);
    } 
        
    heapsort(a,n);
    
    
    
    
    return 0;
}

View Code

　　以下列序列作为案例： 125 11 22 34 15 44 76 66 100 8 14 20 2 5 1 共15个元素

　　案例运行截图：

　　堆排序算法效率与稳定性分析
　　　　对于一个深度为K的堆，“筛选”所需要进行的比较次数之多为2（k-1）;

　　　　对于n个元素，简称深度为 h = （[logn]+1）的堆，所需要进行的比较次数之多为4n;

调整“堆顶”n-1次，总共进行的关键字比较的次数不超过 2[log(n-1)]+ [log(n-2)]+ …… + [log(2)] < 2n[log(n)]

因此堆排序的在最坏的情况下，时间复杂度为O(nlogn)，这是堆的最大优点。堆排序方法在记录较少的情况下并不提倡，但是对于记录较多的数据列表还是很有效的，因为运行时间主要耗费在建初始堆和调整新建堆时运行的反复调整中。在堆排序算法中只需要一个暂存调整记录内容的单元和两个变量，所以堆排序是一种速度快且省空间的排序算法。在堆的重建过程会根据堆的需求改变堆的位置，故堆排序是一种不稳定的排序算法。

　　　　注：主要参考彭军、向毅主编的《数据结构与算法》