c语言堆排序

1.源码实现

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

/* 堆排序:
 * 将待排序的序列构成一个大顶堆。
 * 此时，整个序列的最大值就是堆顶的根节点。
 * 将它移走(即将其与堆数组的末尾元素交换，
 * 此时末尾元素就是最大值), 然后将剩余的
 * n-1个序列重新构造一个堆，这样就会得到
 * n个元素中的次小值。如此反复执行，便能
 * 得到一个有序序列了                      */

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

void max_heapify(int *arr, int start, int end)
{
    /*建立父节点指标和子节点指标*/
    int dad = start;
    int son = dad * 2 + 1;

    /*若子节点指标在范围内才做比较*/
    while(son <= end)
    {
        /*先比较两个子节点大小, 选择最大的*/
        if(son + 1 <= end && arr[son] < arr[son+1])
        {
            son++;
        }

        /*如果父节点大于子节点代表调整完毕*/
        if(arr[dad] > arr[son])
                return;

        /*否则交换父子结点内容*/
        swap(&arr[dad], &arr[son]);
        dad = son;
        son = dad * 2 + 1;
    }
}

void heap_sort(int *arr, int len)
{
    int i;

    /*初始化, i从最后一个父节点开始调整*/
    for(i=len/2; i>=0; i--)
    {
        max_heapify(arr, i, len-1);
    }

    /*先将第一个元素和已经排序的元素前一位做交换, 再重新调整, 直到排序完毕*/
    for(i=len-1; i>0; i--)
    {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i-1);
    }
}

int main()
{
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    int i;

    heap_sort(arr, len);

    for(i=0; i<len; i++)
    {
        printf("%d ", arr[i]);
    }

    printf("\n");

    return 0;
}

2.编译源码

$ gcc -o example example.c -std=c89

3.运行及其结果

$ ./example
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9