c语言数据结构之 堆排序

算法：先生成随机数，赋值到数组，将数组第一个元素a[0]设置为哨兵，函数调用数组和随机数个数n，再设定n/2的根结点与孩子结点进行比较操作，若右孩子存在，则选出三个数里最小的数赋值给根节点，如果右孩子不存在，则只需比较左孩子与根节点大小，一直循环操作至a[1]，再从a[2]开始进行根结点与孩子结点进行比较操作，一直到n/2为止，最后，依次输出a[1],输出后将a[n]赋值给a[1]；再进行递归操作，重复以上步骤，直至数组为空

要点：画出二叉树是方便理解，并非数据的结构就是如同二叉树那般存储，存储形式还是一排

编译器：VS2013

代码

#include "stdafx.h"
#include<stdlib.h>

//函数声明
void HeapSort(int a[], int n); //堆排序（从小到大）
void HSort(int a[], int n);    //辅助堆排序
void Change(int &a, int &b);    //值互换

int main()
 {
    int i, n, a[100];

    printf("请输入需要排序元素的个数：");
    scanf_s("%d", &n);

    printf("随机生成的数组为：");
    for (i = 1; i <= n; i++)
    {
        a[i] = rand() % 100 + 1;
        printf("%d ", a[i]);
    }

    a[i] = '';

    printf("
");
    HeapSort(a, n);
 }

//堆排序（从小到大）
void HeapSort(int a[], int n)
{
    printf("
堆排序后的结果（从小到大）：");

    while (n)
    {
        HSort(a, n);

        printf("%d ", a[1]);
        a[1] = a[n];

        n--;
    }

    printf("

");
}



//辅助堆排序（从小到大）

void HSort(int a[], int n)
{
    int i = n / 2, k;

    while (i)
    {
        k = 2 * i;

        if (k<n&&a[k] >a[k + 1])
            k++;

        if (a[i] > a[k])
            Change(a[i], a[k]);

        i--;
    }

    for (i = 2; i <= n / 2; i++)
    {
        k = 2 * i;

        if (k<n&&a[k] > a[k + 1])
            k++;

        if (a[i] > a[k])
            Change(a[i], a[k]);

    }

}



//值互换
void Change(int &a, int &b)
{
    int t;

    t = a;
    a = b;
    b = t;
}

结果