网易 前k个数，用快排还是堆排

TOPK 问题一般就是 快排划分，以及，构建并维护一个大小为k的堆，这两种方法。。。

不完全快排O(n) 堆排序O(nlog(n)) 但是牛客网上原题答案是堆排 搞不懂

呃，只能说用了快排和堆排的思想。快排的partion很难写到O(N)， 维护一个k个数的大顶堆呢，空间小，复杂度O(nlogk)，一般不会超时。

只用partition不用排序 复杂度O（n）的

题目感觉不明确，什么叫最方便（大致意思）？考虑角度不一样，这个方便意思不一样

partition O(n) 堆 O(nlogk)

堆排。

题目说的数据量不小，所以我觉得还是用堆排序的好

求最小的 k 个元素： 一、 所谓的快排实际上是 QuickSelect(k)，通过分治的方式找到第 k 个数， 总时间复杂度 是 O(N) 的，因为前 K 个数不要求有序。 这个方法的主要优点是平均时间复杂度最小 ，如果用 BFPRT 算法，可以把最坏时间复杂度降到 O(N)。 二、 堆排序有两种： 建立大小为 N 的小根堆，出堆 K 次得到最小的 K 个数。 建堆是 O(N)，出堆一次 O(logN)， 总时间复杂度 O(N+KlogN)； 建立大小为 K 的大根堆，如果下一个数比堆顶大就替换掉堆顶元素并维护堆性质，每次操作都是 O(logK)，总时间复杂度 O(NlogK)。这个方法的主要优点是空间复杂度最小，如果假设 N 个数通过管道流式输入的话，这个方法的空间复杂度是 O(K)；

快排全部排序的话是O(nlogn) 堆排是O(nlogk) 我觉得是堆排

快排O(n)的

这题好像是选快排吧，记得是个旧题目，但是也记不清答案了，因为快速排序是有办法降低最坏情况出现概率的，然后k是不定的，所以赶脚单选题就是考察快排的思想

其实你说的那个用到的只是快排的划分思想，但是并不需要用来进行排序

堆排

用堆排序，堆排序稳定nlogn