一，概念

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

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

二，算法思想：

堆排序的基本思想是：1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了

三，代码：

#include<stdio.h>
#include<stdlib.h>
//堆排序用于查找最大值 或者 最小值
void show(int *p, int n)
{
    for (int i = 0; i < n;i++)
    {
        printf("%4d", p[i]);
    }
    printf("\n");
}
void findmax(int *arr, int size)
{
    for (int j = size - 1; j>0; j--)//从尾部循环到头部
    {
        int parent = j / 2;//定义
        int child = j;//记录当前下标
        if (j < size - 1 && arr[j]< arr[j + 1])//该行的j<size-1 可以避免数组越界
        {
                child++;
        }
        if (arr[child]>arr[parent])
        {
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
        }
    }
}
void heapsort(int *arr, int size)
{
    for (int j = size; j > 0; j--)
    {
        findmax(arr, j);
        int temp = arr[0];
        arr[0] = arr[j - 1];
        arr[j - 1] = temp;
    }
}
void heapsort1(int *arr, int size)
{
    
    for (int i = 0; i < size; i++)
    {
        findmax(arr + i, size-i);
    }
}
void main()
{

    int a[11] = { 10, 13, 99, 12, 30, 14, 50, 19, 60, 29 };
    int b[6] = { 2, 5, 66, 25, 8, 99 };
    //printf("%d\n", a[10]);
    //int *pp = a;
    //printf("%d", pp[10]);
    //show(b, 6);
    //findmax(a, 11);
    //show(a, 11);
    //heapsort(a, 11);
    heapsort1(a, 10);
    show(a, 11);

}


void findmax1(int *arr1, int size1)
{
    int *arr = arr1;
    int size = size1;
    for (int i = 0; i < size1; i++)
    {
        arr = arr1;
        arr = arr + i; 
        size = size1 - i;
        for (int j = size-1; j > 0; j--)//从尾部循环到头部
        {
            int parent = j / 2;//定义
            int child = j;//记录当前下标
            if (j < size - 1 && arr[j]< arr[j + 1])//该行的j<size-1 可以避免数组越界
            {
                child++;
            }
            if (arr[child]>arr[parent])//最大值攀顶
            {
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
            }
        }
    }
}