堆排序算法,C语言代码实例详解

2022-07-1717:17:03数据结构与算法Comments1,171 views字数 2043阅读模式

1.复杂度与稳定性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

算法时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

最坏情况:O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

最好情况:O(n)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

平均情况:O(nlogn)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

稳定性:不稳定排序文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

2. 什么是堆?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

堆排序是一个比较特殊的排序方式,在学习之前我们必须要了解什么是堆。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

堆是一种非线性的数据结构,可以把堆看作一个数组,也可以被看作一个完全二叉树,通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

按照堆的特点可以把堆分为大顶堆和小顶堆。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

a)大顶堆:每个结点的值都大于或等于其左右孩子结点的值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

b)小顶堆:每个结点的值都小于或等于其左右孩子结点的值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

这种特性与我们在前面学习查找方法时学过的二叉排序树很相似,这种特殊的数据结构可以让我们快速访问到我们需要的值,如优先队列就使用堆进行处理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

PS:我们这里提到的堆这个概念与编译器概念堆栈需要区分。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

3.过程介绍文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

基本思想:把待排序的元素按照大小在二叉树位置上排列(使用数组模拟,没必要一定使用二叉树),排序好的元素要满足:父节点的元素要大于等于其子节点;这个过程叫做堆化过程,如果根节点存放的是最大的数,则叫做大根堆;如果是最小的数,自然就叫做小根堆了。根据这个特性(大根堆根最大,小根堆根最小),就可以把根节点拿出来,然后再堆化下,再把根节点拿出来,一直循环到最后一个节点,就排序好了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

基本步骤:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

其实整个排序主要核心就是堆化过程,堆化过程一般是用父节点和他的孩子节点进行比较,取最大的孩子节点和其进行交换;但是要注意这应该是个逆序的,先排序好子树的顺序,然后再一步步往上,到排序根节点上。然后又相反(因为根节点也可能是很小的)的,从根节点往子树上排序。最后才能把所有元素排序好。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

4. 相关的代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

请慢慢理解堆排序这一特殊的排序算法,在排序循环中逐步运算出数据。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html

#include <stdio.h>
 
/* Function: 交换交换根节点和数组末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
 
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
 
/* Function: 构建大顶堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根节点大于左子树 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 检查交换后的左子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根节点大于右子树 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 检查交换后的右子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    int i;
 
    for (i = n; i > 0; i--) {
        BuildMaxHeap(a, i);
        Swap(a, i);
    }
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
 
    return 0;
}
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25225.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25225.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定