前言

一种将无序数组进行排序的方法。

堆排序，wiki参考：
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

堆排序，主要思想：将一维数组构造成堆结构，再对堆结构进行排序。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>


// 父节点i的左子节点在位置 2i + 1 ;
// 父节点i的右子节点在位置 2i + 2 ;

// 堆排序， 类似于满二叉树。
// 1. 构建大顶堆结构
// 2. 通过大顶堆结构排序


void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}


// 构建大顶堆， 从小到大排序，父节点大于子节点。
void _max_heap_sort(int source_array[], int start, int end)
{
    // 父节点
    int dad = start;

    // 子节点中最大的节点，默认为左子节点。
    int son = dad * 2 + 1;

    while (son <= end)
    {
        // 找出子节点中最大的
        if (son + 1 <= end && source_array[son + 1] > source_array[son])
        {
            // 如果右子节点大于左子节点，则son 指向右子节点
            son++;
        }

        // 已经找到最大的子节点，开始调整父节点与子节点满足大顶堆。
        if (source_array[son] > source_array[dad])
        {
            swap(&source_array[son], &source_array[dad]);
        }
        dad = son;
        son = dad * 2 + 1;
    }

}


void max_heap_sort_normal(int source_array[], int source_array_length)
{
    int i;
    // 1. 构造大顶堆结构
    // 遍历每一个父节点。大顶堆要求父节点大于子节点，因此采用逆序的方式。
    for (i = source_array_length / 2 - 1; i >= 0; i--)
    {
        _max_heap_sort(source_array, i, source_array_length - 1);
    }

    // 2. 通过大顶堆结构进行排序。
    // 每次都让列表的第一个值最大，然后将最大值移到最后，有点选择排序的意味。
    for (i = source_array_length - 1; i > 0; i--)
    {
        // 将最大值移到末尾
        swap(&source_array[0], &source_array[i]);
        // 将打乱的大顶堆，重新构造。
        _max_heap_sort(source_array, 0, i - 1);
    }
}


int main()
{
    // 生成随机测试列表
    int test_list[20];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 普通堆排序
    max_heap_sort_normal(test_list, test_list_length);
    printf("普通堆排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    return 0;
}

执行结果参考：

image.png