s***e
发帖数: 403 | 1 QuickSort递归栈的空间不算内存占用？
我觉得QS应该是时间复杂度O(nlogn)，空间复杂度O(logn)的。
heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的，而quicksort过的
数组如果要插入数据并且保持排序状态，插入要求是O(N)的，删除看具体数据结构而定。
quicksort的cpu cache friendly也要看情况，如果是链表做qs那很难做到每个node都
在cache中。就算是数组，qs里面左移的指针也不一定cache friendly。 |
|
x*********w
发帖数: 533 | 2
In practice quick sort is faster,
I think this is because every iteration the array becomes more "tend to be
sorted" so less "swap" operation like heapsort. And if the number of
members is less than a certain limite, insert sort is taken place, which is
the best sorting method for "almost sorted" array. |
|
f****p
发帖数: 18483 | 3
我其实还好少说了一个。
quick sort把一个分裂成两个的时候，理想情况是平均分。而下一步两个子表的长度都
是那个父表的一伴。而heap sort则不是。
你仔细观察这个动画。heap的准备和每一步做的都有。
http://en.wikipedia.org/wiki/Heapsort
如果一般情况下
quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
= n * log(n)
heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
所以尽管heap sort 是 n log(n)，quick sort基本上是最优的。
为了达到最优效果，对于大的n，一般还会做个randomization。很多randomized
algorithms就是这个思路。一般就一两遍就可以达到了，就是说再加上个n 或者 2n。 |
|
d******l
发帖数: 98 | 4 In my opinion, quicksort() is better because the CPU cache thing, has better
locality of reference -- the next thing to be accessed is usually close in
memory to the thing you just looked at. In java, java.util.Arrays.sort()
uses quicksort(), while java.util.Collections.sort() use mergesort().
As for heapsort(), it doesn't build a real heap(tree-heap), it is array/
arraylist in fact, through the index jumping, give us an illusion of a heap.
By the way, bless for myself recent onsite. ^_^ |
|
h**o
发帖数: 548 | 5 Hi,
qsort： nlogn = log n^n
heapsort：sum(log(i)) = log (n!) < log n^n
为什么 qsort 常数因子最小最优那？ |
|
s********u
发帖数: 1109 | 6 是的，对这道题目而言，完全没影响。
但是比如对一个数组做heapsort的时候就有影响了。。 |
|
a******e
发帖数: 710 | 7 Heap sort 不也是nlogn么？
是的，对这道题目而言，完全没影响。但是比如对一个数组做heapsort的时候就有影响
了。。 |
|
s********u
发帖数: 1109 | 8 量级上是没有影响。
heapsort相当于是先建立一个heap,需要O(n),再removefirst n次，就是nlogn
如果第一步是通过push来操作的，那么总共就是2nlogn。
而且有的时候我看会单独问buildheap的time cost |
|
s********u
发帖数: 1109 | 9 不sort的话，你重复的字母不会到一起去啊。因为他不允许用其他数据结构记录重复的
字母，所以只能先排序再做啦。反正只要用in place的sort方式就行了，比如者qsort
，heapsort。 |
|
s********u
发帖数: 1109 | 10 我觉得你可以继续做leetcode，不会的数据结构和算法再回去看（但mergesort，quick
sort，heapsort这些就必须提前看好）。然后不会的题目的答案，想想人家为什么这
么做，不懂的细节再去查。像dp这种，提前看了也没啥大用，我也是做了很多题目，才
大致明白dp是个什么东西，什么时候应该用dp，原来我已经用过好多次dp啊。。
版上面经面试前再看。 |
|
Q****a
发帖数: 296 | 11 请问大牛们海量数据用什么排序方法好？我想的是把数据分成很多小文件，每个文件先
自己排序。然后再用一个heap做heapsort。然后面试官就问这个方法怎么improve
performance？ 想听听大牛们的看法。考虑分布式的话怎么回答这个比较好呢？ |
|
|
s*******z
发帖数: 83 | 13 我觉得还好,不能算是故意刁难.
有一点是面试里面听不懂一定要求他说清楚, 没有说清楚是他的责任, 但是听不清楚就
做题是你的责任了, 就是平时间deliver东西一个道理, 你不做都比assign给你以后不
完成要强的.
第二个应该heapsort和bitmap都是比较好的法子了. |
|
r******l
发帖数: 10760 | 14 复杂度跟实际速度是两码事。quick sort平均来说是最快的。
? |
|
|
y*******g
发帖数: 6599 | 16 quicksort操作的是local memory
? |
|
|
V*********r
发帖数: 666 | 18 堆排序很常用啊。之所以在“面试”中不常出，准确的说法是不常考其实现，无非两个
原因：
1. 白板篇幅有限，heapify/siftup/siftdown全写完白板容不下。
2. quicksort/mergesort变种很多，可inplace可外借空间，可迭代可递归（比如考你
非inplace的迭代式mergesort），是分治思想的典型代表，容易形成考点。而且其思想
适用于任何线性表（不管是数组还是链式存储），也可扩展到树形存储。考点密集不奇
怪。
? |
|
J*****a
发帖数: 4262 | 19 quick sort在实践中是最快的，你可以看看相关文献
而且quicksort有很多变种，改变pivot的选取，或者三头并进，能大大提高最坏情况的
性能 |
|
L***s
发帖数: 1148 | 20 “实践中”要考虑的情况可就多了，比如locality of reference、输入数据已经部分
有序、排序稳定性、内存不够要外排序、多机并行排序 等等，工程中的默认实用排序
一般都是mergesort的变种，也就是两轮或两轮以上的混合排序：最后一轮mergesort，
前面几轮找sorted runs to be merged的方法八仙过海各显神通（比如简单地插入排序
、双pivot快排等等）。
楼主明显是说面试的情况，不必考虑这么多工程上的因素。 |
|
t***t
发帖数: 6066 | 21 quicksort是O(nlogn)算法中常数最小的。 |
|
d********i
发帖数: 582 | 22 到底是O(klogn) 还是 O(nlogk)?
谢谢。。。自己被搞糊涂了。。 |
|
|
l******i
发帖数: 880 | 24 我一直觉得是nlogk啊。。。堆调整不是logk吗？一共n次，所以nlogk?
我看到一种说法是求最大K个，用最大堆的话是klogn，用最小堆是nlogk? |
|
j*********6
发帖数: 407 | 25 应该是 nlogk吧 ls说的应该是对的 但是话说用最大堆怎么做？ |
|
|
x*j
发帖数: 271 | 27 我当然知道有O(n)的算法去找到k个最大的数，是quicksort的partition部分部分的一
个改版，在最开头我已经说的很清楚了。
这个问题的原因在于大于和小于的关系还在，但等于的关系没了。
举例说明 假设有3个单词a b c
a和b之间的 edit distance是 1 b和c之也是1，但a和c之间可能就是2，如果我们定义
edit distance是1或者0的都是不可分的，但二以上就有一个大小于关系，我们可以说a
这个topk的问题是要求返回一个子集，对于没有返回的任何元素，这个子集里都存在着
k个比它大的，但这个子集可以存在和它约等于的元素。因为对于元素a和b，如果a约等
于b，那么比a大的元素不一定比b大。所以这个返回的集合是可能包含不只k个元素的。
我很欢迎有帮助的讨论。对于问题不理解我也很愿意继续澄清，但是请注意的是这里没
有等于只有约等于，所以那些对于integer的排序的算法比如quicksort mergesort
heapsort，它们的复杂度不适用于这个问题。
我知道mergesort的复杂度是O(n^2logn)在这个 |
|
h*******e
发帖数: 225 | 28 I dont think quicksort has less comparisons on average. It really depends on
how you implement them. For example, using William's original heapify
algorithm, you need 2nlogn + O(n) comparisons, whereas using Floyd's heapify
algorithm, you only need nlogn + O(n) on average. There are many variants
for quicksort too.
The reason why quicksort generally beats heapsort is largely due to the data
access pattern. It has better cache locality. |
|
T**********n
发帖数: 480 | 29 quicksort beat heapsort是因为Cache Locality减少了缓存抖动
要说更深刻的原因可以说机器的结构针对quicksort做了优化 |
|
t***t
发帖数: 6066 | 30 quicksort, heapsort, reverse singlist, etc |
|
e***r
发帖数: 68 | 31 有规律吗? 例如相同的几个key，如何如何排列时一定stable, 否则不然之类的。 |
|
p**v
发帖数: 853 | 32 这个几乎没有规律，除非你从头写的code。
如果在比较大小的同时再比较index，应该可以stable。
不过只是call函数，就没法预判了。
那就选择mergesort之类的stable sorting algorithm. |
|
|
|
|
k**f
发帖数: 372 | 36
parameter 'a' is a pointer to int. HeapSort::dataHeap is an array of int.
They are not the same type. You cannot assign a *int to int[]. This is not
only true in ctors, but also true in normal code. Consider:
void func(int *b)
{
int x[10];
x = b; // compiler error. In fact, x cannot be assigned a new value.
}
In your case, you need to explicitly copy the elements led by *a to dataHeap
, and your ctor interface is insufficient because it does not tell how many
to copy.
Alternatively, if yo |
|
k**f
发帖数: 372 | 37
Sorry, I'm afraid both lines are wrong.
A std::vector cannot be initialized by a single pointer. You have to provide
the other pointer pointing to the end of the array outside the array, such
as
HeapSort (int* a):dataHeap(a, a+100) {};
You cannot specify the size of a std::vector in the class definition. You
have to say
std::vector dataHeap; |
|
b***y
发帖数: 2799 | 38 ☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Sun Jul 6 20:08:03 2008) 提到:
还是以前写的代码，报错stack overflow。
如果去掉里面所有unsigned int为int,define RANGE, N为较小的数如1000，那么编译
就可以正常通过。但是为何不支持unsigned很大的数呢
#include
#include "HeapSort.h"
#include "SelectionSort.h"
#include
#include
#include
#include "MersenneTwister.h"
#define RANGE 1000000 //define the range of input data
#define N 10000000 //define how many random numbers to
generate |
|
z****e
发帖数: 2024 | 39 计算机系主任对此问题回复：大家好文共赏
A very good question. Which of the two is faster in practice depends
on a lot of factors, including how you implement each of them. Quicksort
has less random access of memory. You are absolutely right
that quick sort could be much worse than heapsort in some
cases.
I used quick sort to illustrate the technique (e.g., one could
adapt to select the kth smallest item) and not so much because
it was the fastest algorithm. |
|
M***0
发帖数: 1180 | 40 附件中的auto suggestion应该是根据popularity score来决定提示哪5条信息的吧？
实现上，是用SQL database（分表？）来存储每个item和search count好，还是用自己
的代码实现好？如果是用自己的代码，是用heapsort吗？
数据量100M条，这个功能要用在ajax auto suggestion上，速度不能太慢。 |
|
d**********x
发帖数: 4083 | 41 这也是一个好理由。
一个比较贴边的例子：
碰巧昨天刚和人讨论过in-place mergesort的问题
这东西做到了O(1) space，O(nlogn) time，结果实际上还是比同阶的heapsort差很多
which
_< |
|
f*******y
发帖数: 988 | 42 我看最难的就是证明heapsort的复杂度了
奇难无比
x^{n-1} |
|
