设为首页 加入收藏

TOP

经典排序之堆排序详解
2018-12-11 14:10:38 】 浏览:82
Tags:经典 排序 详解

首先我们来看看什么叫做堆排序?


再来看看总结一下基本思想:


通过上面的规律发现两个问题,而堆排序需要解决这两个问题:1.如何建堆? 2.如何调整?


n个元素的序列{k1,k2,…,kn},当且仅当满足下列关系时,成为堆:


如果将序列看成一个完全二叉树,非终端结点的值均小于或大于左右子结点的值。
利用树的结构特征来描述堆,所以树只是作为堆的描述工具,堆实际是存放在线形空间中的。





代码如下:


当我们将数组进行建立大顶堆或者小顶堆的时候,我们就会发现堆顶元素必然是该排序数组的最大或者是最小的那个数据。如何在输出堆顶元素后调整,使之成为新堆?


时间效率:O(nlog2n)  O(nlog2n)
空间效率:O(1) O(1)
稳 定 性:不稳定
适用于n 较大的情况


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Bash 中常见的字符串操作 下一篇基于C++11实现线程池的工作原理

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目