堆排序算法的具体分析和实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了堆排序算法的具体分析和实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2998字，纯文字阅读大概需要5分钟。

内容图文

定义

堆就是完全二叉树的数据结构，堆排序是利用二叉树的孩子与双亲节点的比较来实现的排序方法。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

这里使用的是大顶堆。

基本思想

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

代码

/**
 * 总结
 * 堆排序就是通过一个完全二叉树, 把数据按照1开始的顺序编排
 * 然后, 进行一个算法, 找出初始堆, 发现一个确定的最大值, 并抹除输出
 * 接着在进行该算法, 找出第二个最大的数字
 * 
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 200
typedef int KeyType;
typedef int InfoType;
typedef struct SS
{
    KeyType key;   //关键字项
    InfoType data; //其他数据项
} RecType;         //排序的元素的类型

//交换函数
void swap(RecType &a, RecType &b)
{
    RecType c;
    c = a;
    a = b;
    b = c;
}

RecType *Init(int* a, int n)
//就是将数组存入对应的关键字的结构体中
{
    int i;
    RecType * R;

    R = (RecType *)malloc(sizeof(RecType)*MAX);
//注意这是一个偷懒的办法，浪费了空间，虽然提高了速度
//正常应该在创建的时候，即下面的for循环中一个个的开辟空间
    for (i = 1; i <= n; i++)
    {
        R[i].key = a[i-1];
    }
    return R;
}

void sift(RecType R[], int low, int high)
//建立初始堆
//就是从low开始的位置，把low看成根节点的，并且把比low大的孩子节点
//和low替换，实现效果就是low节点和其子树都满足大根堆的条件。
{
    int i = low, j = 2 * i;
    RecType temp = R[i];
    while (j <= high)
    {
        if (j < high && R[j].key < R[j + 1].key)//j指向左右子树中大的那个，为了下面的替换
            j++;
        
        if(temp.key < R[j].key)  //如果根节点比子树小，就替换
        {
            R[i] = R[j];
            i = j;	//i指向j的左孩子，因为可能根节点实在太low特别小，
           			// 可能会比孙子还小，所以要找找有没有大的孙子
            j = 2*i;
        }
        else
        	 break;  //如果根节点都比孩子大，那么它的位置保住了，退出
    }

    R[i] = temp; //这一句是为了照顾第二个if情况的，如果比孙子辈小的话
    			//那前面已经根节点替换成了孙子， 而孙子的位置需要它来顶替
    			//当然如果没有比较小的话，这一句话也没有影响，R[i]本来就是temp
}

void HeapSort(RecType R[], int n)
{
    int i;

    for(i = n/2; i >= 1; i--)
        sift(R, i, n);       //这个地方只要一半就好，因为子树作为2*(n/2) == n
        					//就是建立初始堆，此时并没有完成排序
        					//但是初始堆代表着树的根节点是最大值

    for (i = n; i >= 2; i--){    //接下来就是去掉最大值，每次跑一遍
        swap(R[1], R[i]);     //最大值被最后一个值交换掉，并且不再进行运算
        sift(R, 1, i - 1);    //接着继续通过刚才的函数找最大值
    }
}

int main ()
{
    int a[10] = {6, 32, 12, 34, 25, 76, 34, 1, 9, 98};
    RecType *R;
    R = Init(a, 10);

    HeapSort(R, 10);

    int  i;
    for(i = 1; i <= 10; i++)
    {
        printf("%d ", R[i].key);
    }
    system("pause");
    return 0;
}

复杂度分析

因为堆排序无关乎初始序列是否已经排序已经排序的状态，始终有两部分过程，构建初始的大顶堆的过程时间复杂度为O(n)，交换及重建大顶堆的过程中，需要交换n-1次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn)，空间复杂度O(1)。

Luky

内容总结

以上是互联网集市为您收集整理的堆排序算法的具体分析和实现全部内容，希望文章能够帮你解决堆排序算法的具体分析和实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---