堆排序 我会带着你远行 2021-10-18 16:46 308阅读 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
还没有评论,来说两句吧...