堆排序

亦凉 2021-11-26 12:56 197阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    int n;
    
    /*
     * 生成堆
     */
    void HeapAdjust(int *array, int s, int m)
    {
        int i;
        array[0] = array[s];
        for (i = s * 2; i <= m; i *= 2)
        {
            if (i < m && array[i] < array[i + 1])
            {
                i++;
            }
            if (!(array[0] < array[i]))
            {
                break;
            }
            array[s] = array[i];
            s = i;
        }
        array[s] = array[0];
    }
    
    /*
     * 堆排序
     */
    void HeapSort(int *array)
    {
        int i;
        for (i = n / 2; i > 0; i--)
        {
            HeapAdjust(array, i, n);
        }
        for (i = n; i > 1; i--)
        {
            array[0] = array[1];
            array[1] = array[i];
            array[i] = array[0];
            HeapAdjust(array, 1, i - 1);
        }
    }
    
    int main()
    {
        int i;
        int *array;
        printf("请输入数组的大小：");
        scanf("%d", &n);
        array = (int*) malloc(sizeof(int) * (n + 1));
        printf("请输入数据（用空格分隔）：");
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &array[i]);
        }
        HeapSort(array);
        printf("排序后为：");
        for (i = 1; i <= n; i++)
        {
            printf("%d ", array[i]);
        }
        printf("\n");
    }

转载于:https://www.cnblogs.com/kxzh/p/10920051.html

发表评论取消回复

表情：

评论列表（有 0 条评论，197人围观）

还没有评论，来说两句吧...

相关阅读

相关排序-堆排序

1.堆排序前言前面博客中讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则如何知

旧城等待，/ 2022年09月30日 06:45/ 0 赞/ 228 阅读

相关【排序】堆排序

堆的定义设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 ![图示][SouthEast] 解释：如果让满足以上条件的元素序列（k

分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 264 阅读

相关看懂堆排序——堆与堆排序（三）

看懂堆排序——堆与堆排序（三）看懂堆排序——堆与堆排序（三）堆排序的基本思想代码详解

偏执的太偏执、/ 2022年05月25日 06:52/ 0 赞/ 281 阅读

相关排序——堆排序

堆排序代码 include <iostream> using namespace std; include <stdio.h> in

墨蓝/ 2022年05月21日 12:05/ 0 赞/ 256 阅读

相关堆排序

include <stdio.h> include <stdlib.h> int n; / 生成堆 /

亦凉/ 2021年11月26日 12:56/ 0 赞/ 198 阅读

相关堆排序

什么是堆排序，堆排序能解决什么问题？在排序的过程中，不能把进行排序的过程中，得一些信息保留下来吗？来加快排序的速度吗？答案是可以的。通过利用完全二叉堆的结构来保留信息。

迷南。/ 2021年10月29日 07:20/ 0 赞/ 363 阅读

相关堆和堆排序

堆排序堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也

柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 396 阅读

相关堆排序

文章目录一、堆排序介绍二、如何进行堆排序一、堆排序介绍百度百科：堆排序（Heapsort）是指利用堆积树

我会带着你远行/ 2021年10月18日 16:46/ 0 赞/ 353 阅读

相关排序-堆排序

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆：先看下图（来源

清疚/ 2021年09月20日 03:22/ 0 赞/ 432 阅读

相关堆排序

堆排序的特点是：在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）

不念不忘少年蓝@/ 2021年09月17日 00:16/ 0 赞/ 456 阅读