9.堆排序

#include <stdio.h>
#include <stdlib.h>

#define N 20
//   0
// 1   2
//3 4 5  6
//获取数组中最大的一个然后登顶(大数登顶)
void getmax(int *arr, int size)
{
    //遍历
    for (int i = size - 1; i > 0; i--)
    {
        //当前节点
        int child = i;
        //父节点
        int parent = (i-1)/2;

        //如果当前节点的值大于父节点，则往上移动
        if (arr[child] > arr[parent])
        {
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
        }
    }
}

//堆排序
void heapsort(int *arr, int size)
{
    //依次登顶各个位置
    for (int i = 0; i < size; i++)
    {
        getmax(arr + i, size - i);
    }
}

//显示数据
void show(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%4d", arr[i]);
    }
    printf("\n");
}


void main()
{
    //初始化数据
    int arr[N];
    for (int i = 0; i < N; i++)
    {
        arr[i] = rand() % 100;
    }
    show(arr, N);
    //调用堆排序
    heapsort(arr, N);
    //显示
    show(arr, N);

    system("pause");
}