首页 / 算法 / 算法-一步步教你如何用c语言实现堆排序（非递归）

算法-一步步教你如何用c语言实现堆排序（非递归）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法-一步步教你如何用c语言实现堆排序（非递归），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3226字，纯文字阅读大概需要5分钟。

内容图文

看了左神的堆排序，觉得思路很清晰，比常见的递归的堆排序要更容易理解，所以自己整理了一下笔记，带大家一步步实现堆排序算法

首先介绍什么是大根堆：每一个子树的最大值都是子树的头结点，即根结点是所有结点的最大值

堆排序是基于数组和二叉树思想实现的（二叉树是脑补结构，实际是数组）

算法-一步步教你如何用c语言实现堆排序（非递归） - 文章图片

堆排序过程

1、数组建成大根堆，首先，遍历所有结点，当前结点index和父结点（index-1）/ 2 比较 （当前数组的下标是index，此结点的父结点的下标就是（index-1）/ 2  ），如果比父结点大，交换，变成父结点的位置再和上一层的父结点比较，直到满足大根堆条件

int swap(int source[], int a, int b)
{
    int temp = source[a];
    source[a] = source[b];
    source[b] = temp;
}
int heapsort(int source[], int len)
{
    for (int i = 0; i <len; i++)
    {
        heapInsert(source, i);
    }
}
int heapInsert(int source[], int index)
{
    while (source[index] > source[(index - 1) / 2])
    {
        swap(source, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

2、让根结点和最后一个结点交换位置，也就是数组的第一个数和最后一个数交换位置，接下来最后一个数不用考虑了，比如一个数组有5个数，定义一个变量size=5，大根堆的根结点放到最后一个数后，--size

int size = len;
swap(source, 0, --size);

3、让交换后的头结点经历一个向下的调整，让结点和自己的两个孩子比较，如果孩子的值比头结点大，交换，交换到孩子结点位置，继续和下面的两个孩子比较，直到满足大根堆条件

int heapify(int source[], int index, int size)//index表示要和它两个孩子比较的结点
{
    int left = index * 2 + 1;  //找到index左孩子结点的数组下标
    while (left < size)
    {
        int largest = left + 1 < size && source[left + 1] > source[left] ? source[left + 1] : source[left];//如果有右孩子且右孩子比左孩子大，令largest=右孩子的值，也就是把两个孩子中最大的一个数赋给largest
        if (source[index] < source[largest])
        {
            swap(source, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
        else break;
    }

}

4、重复第2步，第3步，直到size = 0 ，整个数组排序过程结束

while (size > 0)
    {
        swap(source, 0, --size);
        heapify(source, 0, size);
    }

源代码如下

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int swap(int source[], int a, int b)
{
    int temp = source[a];
    source[a] = source[b];
    source[b] = temp;
}
int heapsort(int source[], int len)
{
    for (int i = 0; i < len; i++)
    {
        heapInsert(source, i);
    }
    int size = len;
    while (size > 0)
    {
        swap(source, 0, --size);
        heapify(source, 0, size);
    }
}
int heapInsert(int source[], int index)
{
    while (source[index] > source[(index - 1) / 2])
    {
        swap(source, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
int heapify(int source[], int index, int size)//index表示要和它两个孩子比较的结点
{
    int left = index * 2 + 1;  //找到index左孩子结点的数组下标
    while (left < size)
    {
        int largest = left + 1 < size && source[left + 1] > source[left] ? left + 1 : left;//如果有右孩子且右孩子比左孩子大，令largest=右孩子的值，也就是把两个孩子中最大的一个数赋给largest
        if (source[index] < source[largest])
        {
            swap(source, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
        else break;
    }

}
int main()
{
    int source[] = { 10,16,123,8,79,6,54,65,48,6,54,536,654,64,8,9,25,17 };
    int len;
    len = sizeof(source) / sizeof(int);
    heapsort(source, len);
    for (int i = 0; i < len; i++)
    {
        printf("%d ", source[i]);
    }
    
}

输出结果

算法-一步步教你如何用c语言实现堆排序（非递归） - 文章图片

以上就是堆排序的所有细节，这个版本很优良，堆排序的额外空间复杂度是O(1)，如果用递归的话，递归有递归栈，额外空间复杂度不就上去了吗，设计成这种迭代的可以省空间，时间复杂度为O（n log n）

转载请注明出处、作者  谢谢

 

内容总结

以上是互联网集市为您收集整理的算法-一步步教你如何用c语言实现堆排序（非递归）全部内容，希望文章能够帮你解决算法-一步步教你如何用c语言实现堆排序（非递归）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/746548.html

来源：【匿名】