C语言堆排序

95 阅读 0 评论 63 点赞

我是靠谱客的博主爱听歌黄蜂，最近开发中收集的这篇文章主要介绍C语言堆排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

堆排序原理：
堆的结构类似于完全二叉树，头节点位于整个结构的最上方，每个父节点从左到右依次分岔，延申出两个子节点。
每层节点从左到右在数据中是依次排列的关系。
堆中某个结点的值总是不大于其父结点的值（大顶堆：头节点值最大）。

堆中某个结点的值总是不小于其父结点的值（小顶堆：头节点值最小）。

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

#include <stdio.h>
#define size 10

void Swap(int *num, int i, int j)
{
    int temp;
    temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

// 最大堆调整
void Heapify(int *num, int len, int k)
{
    if (k < len)
    {
        int root = k;           // 根结点
        int lchild = 2*k + 1;   // 左孩子结点
        int rchild = 2*k + 2;   // 右孩子结点
        // 查找左右孩子结点中的最大结点
        if (lchild < len && num[root] < num[lchild])
        {
            root = lchild; 
        }
        if (rchild < len && num[root] < num[rchild])
        {
            root = rchild;
        }
        
        // 交换最大结点到根结点
        if (root != k)
        {
            Swap(num, root, k);
            // 每次交换都可能影响到对应孩子结点子树的顺序
            // 所以需要对交换后的孩子结点子树进行最大堆调整
            Heapify(num, len, root);
        }
    }
}

// 创建最大堆
void CreateHeap(int *num, int len)
{
    int i;
    // 最后一个结点下标
    int last = len - 1;   
    // 最后一个结点的父结点下标      
    int parent = (last - 1) / 2;
    // 从最后一个结点的父结点到根结点，依次进行最大堆调整
    for (i = parent; i >= 0; i--)
    {
        Heapify(num, len, i);
    }
}

// 堆排序
void HeapSort(int *num, int len)
{
    // 创建最大堆并进行最大堆调整
    CreateHeap(num, len);
    printf("最大堆调整!n");
    int i;
    // 依次取出根结点（最大值）
    for (i = len - 1; i >= 0; i--)
    {
        // 将最大堆的根结点（最大值）换到最后一个结点
        Swap(num, i, 0);
        // 交换后二叉树的根结点发生了改变，故还需对根结点做最大堆调整（已交换的末尾结点不参与调整）
        // 而此时根结点小于所有父结点，因而在调整时只需考虑最大孩子的分支即可
        Heapify(num, i, 0); 
    }   
}

int main()
{
    int i, num[size] = {8, 4, 3, 1, 6, 9, 5, 7, 2, 0};
    HeapSort(num, size);

    for (i = 0; i < size; i++)
    {
        printf("%d ", num[i]);
    }
    printf("n");
    return 0;
}

解析

若数组为以下序列

一、数组转换二叉树，从上往下、从左往右对应数组下标，则对于任意结点下标k
父结点下标 =【（k - 1）/ 2】、左孩子下标 =【2k + 1】、右孩子下标 =【2k + 2】

二、最大堆调整（Heapify）
从左右孩子中选择最大的孩子结点，与父结点交换，并递归调整交换后的孩子结点
例如如下图，对结点【4】进行最大堆调整，选择最大孩子结点【6】进行交换，交换后递归调整孩子结点【4】往下继续查找最大孩子结点【7】并进行交换

三、创建最大堆（CreateHeap）
但我们发现单对一个结点进行最大堆调整并不能使得整个二叉树形成最大堆；
所以我们需要对末尾子结点的父结点到根节点依次向前进行最大堆调整，从而使得整个二叉树形成最大堆

四、堆排序（HeapSort）
（1）根结点为最大值，则接下来需要将根结点与末尾子结点交换，即可完成最大值【9】的排序
（2）对根结点进行最大堆调整（已交换的末尾结点不参与调整），使得根结点为下一个最大值
（3）最后通过不断的交换，缩小最大堆调整的范围到只剩下根结点后，即可完成整个序列的排序