堆排序算法的实现

最新推荐文章于 2025-05-30 10:00:00 发布

preciousboy

最新推荐文章于 2025-05-30 10:00:00 发布

阅读量687

点赞数

文章标签：算法数据结构存储

本文详细介绍了堆排序算法的原理及实现过程，包括构建最小堆、调整堆结构等关键步骤，并给出了具体的C语言实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

http://blog.chinaunix.net/u1/59254/showart_1002632.html

网上摘了一些描述:

堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。
      堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。
      二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。
      堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。
堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。
      堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。
      二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。
      堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。

根据要求实现了下：

#include <stdio.h>

void push_heap(int *array, int pos, int value)
{
    int i;
    for(i=pos; i/2>0 && array[i/2]>value; i/=2) {
        array[i] = array[i/2];
    }
    array[i] = value;
}

void make_heap(int *data, int *array, int len)
{
    for(int i=0; i<len; ++i) {
        push_heap(array, i+1, data[i]);
    }
}

int pop_heap(int *array, int last)
{
    int value = array[1];
    array[1] = array[last];
    int i=1;
    while(2*i < last) {
        int min = array[2*i] < array[2*i+1] ? array[2*i] : array[2*i+1];
        int pos = array[2*i] < array[2*i+1] ? (2*i) : (2*i+1);
        if(array[i] > min) {
            int tmp = array[i];
            array[i] = min;
            array[pos] = tmp;
            i = pos;
        }
    }
    return value;
}

void sort_heap(int *data, int *array, int len)
{
    for(int i=0; i<len; ++i) {
        data[i] = pop_heap(array, len-i);
    }
}

int main()
{
    int data[] = {12, 34, 23, 3, 1, 45, 87, 99};
    int array[10];
    make_heap(data, array, 8);
    for(int i=1; i<=8; ++i) {
        printf("%d ", array[i]);
    }
    printf("/n");
    sort_heap(data, array, 8);
    for(int i=0; i<8; ++i) {
        printf("%d ", data[i]);
    }
    printf("/n");
    return 0;
}

堆排序的空间复杂度要求O(1)，上面程序使用了辅助数组，所以其空间复杂度为O(n)，不符合要求，所以又写了一个,如下：

/*
* 2008/06/24 By YaoJianming
* */
#include <stdio.h>

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

void adjust(int *array, int i, int n)
{
        int min, pos;
        while(1) {
                if((2*i+2) < n) {
                        min = array[2*i+1] < array[2*i+2] ? array[2*i+1] : array[2*i+2];
                        pos = array[2*i+1] < array[2*i+2] ? (2*i+1) : (2*i+2);
                        if(array[i] < min) { break; }
                        swap(&array[i], &array[pos]);
                        i = pos;
                } else if((2*i+2) == n) {
                        min = array[2*i+1];
                        pos = 2*i+1;
                        if(array[i] < min) { break; }
                        swap(&array[i], &array[pos]);
                        i = pos;
                } else {
                        break;
                }
        }
}

void heap_sort(int *array, int n)
{

//构建最小堆
        for(int j=(n-1)/2; j>=0; --j) {
                adjust(array, j, n);
        }

//降序排列
        for(int i=n; i>1; --i) {
                swap(&array[0], &array[i-1]);
                adjust(array, 0, --n);
        }
}

int main()
{
        int data[] = {12, 34, 23, 3, 1, 45, 87, 99};
        heap_sort(data, 8);
        for(int i=0; i<8; ++i) {
                printf("%d ", data[i]);
        }
        printf("/n");
        return 0;
}