首页 > 试题广场 >

关于堆排序复杂度分析的叙述中正确的是（）

[不定项选择题]

```
堆排序的时间复杂度为O(nlogn)
```

整个构建堆的时间复杂度为O(n)

```
堆排序的空间复杂度为O(1)
```

堆排序是一种不稳定的排序算法

查看答案及解析

月夜将至

建堆的时间复杂度为O(n)

(1)证明如下：
构建堆从叶节点的父节点开始，以树高递减的方向逐层往上，一直到根。
假设堆敏感词有N个元素，则树高H=log2(N)，对于从树高为h的节点建堆的复杂度为O(H - h)；
从最底层开始，为从各节点建堆的复杂度求和：
S = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0
  = 2^H + 2^(H-1) + ... + 2^1 - H
  = 2^(H+1) - 2 - H
将H=log2(N)代入，S = 2N - 2 - log2(N)

发表于 2017-06-30 15:05:40 回复(0)

果冻Bryce

判断排序算法是否稳定，看排序前后的相同元素是否发生交换，若有交换则是不稳定的，否则是稳定的。

发表于 2018-03-11 08:59:20 回复(0)

牛客287369450号

建堆时间复杂度：O(n)，与堆中的元素个数有关

建堆空间复杂度：O(1)，表示所需空间为常量,并且与元素数无关

不稳定的排序算法：（快些选堆~朋友来聊天）快速排序、希尔排序、选择排序、堆排序

堆排序时间复杂度：O(nlogn)

发表于 2023-02-25 18:21:21 回复(0)

枫叶@

堆是一颗完全二叉树，假设有n个节点，树高
证明方法如下：
1. 假设根节点的高度为0，叶子节点高度为h，那么每层包含的元素个数为2^x，x从0到h。
2. 构建堆的过程是自下而上，对于每层非叶子节点需要调整的次数为h-x，因此很明显根节点需要调整(h-0)次，第一层节点需要调整(h-1)次，最下层非叶子节点需要调整1次。
3. 因此可知，构造树高为h的二叉堆精确时间复杂度为：
s = 1*2^(h-1) + 2*2^(h-2)+……+h*2^0
可以看出以上公式是等差数列和等比数列乘积之和，可以通过错位相减求：
2s = 2^h + 2*2^(h-1)+3*2^(h-2)+……+h*2^1
因此可得:
s = 2s -s = 2^h + 2^(h-1) + 2^(h-2) +…… + 2^1 - h
最终可以通过等比数列公式进行计算得到s = 2*2^h - 2 -h

将

代入的s = 2n - 2 - log2(n)，近似的时间复杂度就是O(n)。

发表于 2019-04-15 11:35:49 回复(0)

牛客912866077号

空间复杂度O(1)表示常量，与n无关。

发表于 2022-04-14 15:08:57 回复(0)

陳丶奕丶迅

不稳定的排序算法:堆排序，希尔排序，快速排序，选择排序。稳定的排序算法:选择排序，插入排序，归并排序，基数排序

发表于 2022-09-05 10:40:16 回复(1)

天尊墨宇

选ABCD

发表于 2020-07-19 07:27:14 回复(0)

牛客34821334号

C也是对的吧

发表于 2020-07-31 15:48:27 回复(0)

提交观点

问题信息

C++工程师 2017 京东堆 Java工程师

上传者：齐小乐

难度：

8条回答 885收藏 5716浏览

关于堆排序复杂度分析的叙述中正确的是（）

问题信息

热门推荐

相关试题

关于堆排序复杂度分析的叙述中正确的是（ ）

问题信息

热门推荐

相关试题

关于堆排序复杂度分析的叙述中正确的是（）