堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

这里说明下父节点与子节点之间的下标关系：

• 二叉树的K层的节点数量为：,
• 可以得到k层的第一个节点（下标，下同）：
• k层的第m()个节点 “i”：
• 
• 可以得到k层m节点对应的子节点左节点“j”：
• 我们可以得到公式：
  
  
  
  
  可以得到父节点与子节点左节点的关系： ，右节点只需左节点+1即可：

堆的最后一个非叶子节点若只有左孩子,得到左后一个非叶子节点下标p：

堆的最后一个非叶子节点有左右两个孩子,得到左后一个非叶子节点下标p：

算法步骤

• 创建一个堆 H[0……n-1]；

• 把堆首（最大值）和堆尾互换；

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

• 重复步骤 2，直到堆的尺寸为 1。

动图演示

image

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//堆排序
void heap_sort(int a[],int len){
    // 堆的最后一个非叶子节点
    int f= len%2==0?len/2-1:(len-1)/2-1;
    //第一次由下至上构建大堆
    for(int i=f;i>=0;i--){
        swap_heap(a,i,len);
    }
    //循环构建大堆
    for(int j=len-1;j>0;j--){
        //交换首尾元素
        swap(&a[0],&a[j]);
        //重新由上至下构建大堆
        swap_heap(a,0,j);
    }
}
//构建堆
void swap_heap(int a[],int i,int len){
    //左子节点
    int left = 2*i+1;
    //右子节点
    int right = 2*i+2;
    //父节点
    int k=i;
    //对比left和k和right和k找出最大值下标
    if(left<len&&a[left]>a[k]){
        k=left;
    }
    if(right<len&&a[right]>a[k]){
        k=right;
    }
    //如果父节点的值不是最大值
    if(k!=i){
        //最大值与父节点交换
        swap(&a[k],&a[i]);
        //位置发生变化需要重新校验子节点
        swap_heap(a,k,len);
        printf("父节点a[%d]=%d",i,a[i]);
        printArray("",a,len);
    }
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    heap_sort(arr,len);
    printArray("堆排序：",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

运行结果：

未排序前:126 26 120 74 101 32 15 141 39 63
父节点a[3]=141:126 26 120 141 101 32 15 74 39 63
父节点a[3]=74:126 141 120 74 101 32 15 26 39 63
父节点a[1]=141:126 141 120 74 101 32 15 26 39 63
父节点a[0]=141:141 126 120 74 101 32 15 26 39 63
父节点a[1]=101:126 101 120 74 63 32 15 26 39
父节点a[0]=126:126 101 120 74 63 32 15 26 39
父节点a[0]=120:120 101 39 74 63 32 15 26
父节点a[1]=74:101 74 39 26 63 32 15
父节点a[0]=101:101 74 39 26 63 32 15
父节点a[1]=63:74 63 39 26 15 32
父节点a[0]=74:74 63 39 26 15 32
父节点a[0]=63:63 32 39 26 15
父节点a[0]=39:39 32 15 26
父节点a[0]=32:32 26 15
父节点a[0]=26:26 15
堆排序：:15 26 32 39 63 74 101 120 126 141