堆排序 我会带着你远行 2021-10-18 16:46 366阅读 0赞 ### 文章目录 ### * * * 一、堆排序介绍 * 二、如何进行堆排序 ### 一、堆排序介绍 ### 百度百科: * 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大顶堆和小顶堆,是完美二叉树。 * 大顶堆 :每个结点的值都大于或等于其左右孩子结点的值 * 小顶堆:每个结点的值都小于或等于其左右孩子结点的值 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70] * 完全二叉树:除了最后一层之外的其他每一层都被完全填充,并且所有节点都保持向左对齐。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 1] * 满二叉树:除了叶子结点之外的每一个节点都有二个孩子,每一层(当然包括最后一层)都被完全填充。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 2] * 完满二叉树:除了叶子结点之外的每一个结点都有两个孩子节点。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 3] ### 二、如何进行堆排序 ### 堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70]: /images/20211018/7694895573f2475fa06590230e556da4.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 1]: /images/20211018/acf67095dca741af892e352175387edd.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 2]: /images/20211018/eb7f4fb4d2574f84b3a7b5ec3135af10.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDUwMjgwNA_size_16_color_FFFFFF_t_70 3]: /images/20211018/4a83b104861c4373943112c18a0c27f3.png
相关 排序-堆排序 1.堆排序前言 前面博客中讲到简单选择排序,它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知 旧城等待,/ 2022年09月30日 06:45/ 0 赞/ 242 阅读
相关 【排序】堆排序 堆的定义 设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆。 ![图示][SouthEast] 解释:如果让满足以上条件的元素序列 (k 分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 281 阅读
相关 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 堆排序的基本思想 代码详解 偏执的太偏执、/ 2022年05月25日 06:52/ 0 赞/ 302 阅读
相关 排序——堆排序 堆排序代码 include <iostream> using namespace std; include <stdio.h> in 墨蓝/ 2022年05月21日 12:05/ 0 赞/ 272 阅读
相关 堆排序 什么是堆排序,堆排序能解决什么问题? 在排序的过程中,不能把进行排序的过程中,得一些信息保留下来吗?来加快排序的速度吗?答案是可以的。通过利用完全二叉堆的结构来保留信息。 迷南。/ 2021年10月29日 07:20/ 0 赞/ 381 阅读
相关 堆和堆排序 堆排序 堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复 杂度均为 O(nlogn),它也 柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 414 阅读
相关 堆排序 文章目录 一、堆排序介绍 二、如何进行堆排序 一、堆排序介绍 百度百科: 堆排序(Heapsort)是指利用堆积树 我会带着你远行/ 2021年10月18日 16:46/ 0 赞/ 367 阅读
相关 排序-堆排序 [2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆: 先看下图(来源 清疚/ 2021年09月20日 03:22/ 0 赞/ 452 阅读
相关 堆排序 堆排序的特点是:在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中父结点和子结点之间的内在关系,在当前无序区中选择关键字最大(或最小) 不念不忘少年蓝@/ 2021年09月17日 00:16/ 0 赞/ 472 阅读
还没有评论,来说两句吧...