面试手写堆排还是挺难的

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2844 天前的主题，其中的信息可能已经有所发展或是发生改变。

今天面试说手写一个堆排序

之前写过几次

临时叫写，还是很难一下写出来

所以面试之前，一定要刷算法题啊

堆排

堆排序

面试

手写

36 条回复 • 2017-02-15 18:44:17 +08:00

sagaxu

2017-02-12 17:33:10 +08:00

工作了好多年，我都不记得堆排是什么了，每次排序都调的标准库

logbang

2017-02-12 17:35:33 +08:00 via Android

反正我不会

Powered

2017-02-12 17:59:05 +08:00 via iPhone

找工作就是刷题加背书

Yourdaye

2017-02-12 18:00:34 +08:00

写的时候不能用手机 google ？

coderluan

2017-02-12 18:15:30 +08:00

不刷题确实不容易，虽然嘴上描述或者伪代码出来很容易，但是敲代码细节容易卡住，需要调试才行，面试还要心里压力之类的，很正常。

Mirana

2017-02-12 18:27:29 +08:00

网络上嘴炮太多了

gouchaoer

2017-02-12 18:32:08 +08:00 via Android

堆排序那么一大堆能写出来的有几个，这面试这么厉害？

allan888

2017-02-12 18:38:30 +08:00

谁家面试让写堆排序了啊？

gejun123456

2017-02-12 18:55:19 +08:00

蛋疼的面试，反问面试官让他写一个。

wodesuck

2017-02-12 18:55:31 +08:00

其实堆排还是挺好写的吧，逻辑清晰，相比快排又没什么容易写错的细节。
（说这样的话会不会被喷呀……

zgqq

2017-02-12 19:01:28 +08:00 via Android

都是大佬

binux

2017-02-12 19:02:29 +08:00

@wodesuck #10 我没记错的话，堆排只有一个调整堆要写啊
（看那么多人喊难，我只能默默给你点赞

svenFeng

2017-02-12 19:34:57 +08:00 via Android

堆排还是算简单的吧。。。给纸笔推倒一遍就可以写了吧

JohnLou

2017-02-12 19:38:08 +08:00

大公司面试基本都考这些啊，看了楼上，难道我面的是假的？

scnace

2017-02-12 19:44:02 +08:00 via Android

@coderluan 严重同意！

scnace

2017-02-12 19:45:45 +08:00 via Android

伪算法还是直接 code ？表示不 debug 真写不来……～

wildlynx

2017-02-12 20:20:53 +08:00

简单的二分查找算法，很多人也很难一下子手写出正确的程序来。

hxndg

2017-02-12 20:52:22 +08:00

额。。。。。基本都是就调整需要注意一下。。。剩下的都是几个大概就可以了。。。

lonenol

2017-02-12 21:45:53 +08:00

堆排应该是最好写的了吧。。

LukeXuan

2017-02-12 21:51:03 +08:00

堆排应该是 O(n log n)里面最好写的了...

Allianzcortex

2017-02-12 21:54:23 +08:00

。。。。。。我虽然能写出来，但堆排序怎么都不是最简单的吧。。。 @LukeXuan merge sort 是 O(nlogn) 时间复杂度里最好写的啊

davy1995

2017-02-12 21:55:25 +08:00 via Android

@LukeXuan 归并不是更好写？

qzheng93

2017-02-12 23:34:53 +08:00 via iPhone

堆排怕不是太长了吧。而且写堆排意义不大呀，毕竟有优先队列的。

oska874

2017-02-12 23:52:45 +08:00

社招还要现场写代码？

owt5008137

2017-02-13 08:09:22 +08:00 via Android

归并应该才是最好写。
堆排就从后往前扫一次建堆，然后再扫一次换掉堆顶重新建堆就好了嘛。
之前有一次想到手写堆排发现忘记了，后来特意记了一下就一直没忘。

LokiSharp

2017-02-13 08:44:56 +08:00 via iPhone

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md 不客气

LukeXuan

2017-02-13 09:32:26 +08:00

@Allianzcortex
@davy1995
个人感觉吧...其实是我 merge 没写过(多一倍空间所以用到很少) 不过仔细想想应该是 merge 简单或者至少一个级别的。总之比 quicksort 方便多了也形象

zouchuan1993

2017-02-13 10:02:07 +08:00

@wodesuck 你的头像是真的骚

ytmsdy

2017-02-13 10:22:44 +08:00

真的很好奇，面试官出这样子的题目的意义在于什么？
考验面试者技术扎实的程度？堆排这鬼东西，实际 coding 过程中千百年都用不到一次吧？！

blackjar

2017-02-13 10:38:29 +08:00

写 Pseudo code 足够了思路说清楚就 ok

wshcdr

2017-02-13 10:43:17 +08:00

堆排算是实际里基本不用的了......要考手写，的确难

woostundy

2017-02-13 14:50:07 +08:00

@LukeXuan
@lonenol
O(N logN)里最简单应该是快排啊

woostundy

2017-02-13 14:53:05 +08:00

感觉归并和快排比较多见，实际用到的也多一点。
堆排突然让写，是挺有难度的。

LedChang

2017-02-13 17:42:26 +08:00

刚考过研的肯定记得，工作那么多年后，我现在就记得是用一个 list 模拟树去操作。

nec

2017-02-15 18:43:22 +08:00

@oska874 当然，考查算法以及编程基础

nec

2017-02-15 18:44:17 +08:00

@Allianzcortex 是啊，快排和归并都比较好写