m*****g
发帖数: 226 | 1 heapsort我觉得比quicksort好写
quicksort下标搞来搞去很烦 |
|
m********g
发帖数: 272 | 2 虽然worst－case quicksort是O(n^2), 但是on avarage, quicksort 为什么会比
heapsort 快呢？ |
|
s********x
发帖数: 914 | 3 // MaxHeap: heapArray starts from index 0
public static void heapSort(int[] a){
// Trickling Down in Place: start at node n/2-1, the rightmost node
with children
// O(n/2*log(n))
for (int i=(a.length/2-1) ; i>=0 ; i--)
trickleDown(a,i, a.length);
// remove max from heap and insert it at the end
// O(n*log(n))
for (int i= a.length - 1; i> 0; i--){
int max = a[0];
a[0] = a[i];
trickleDown(a,0, i... 阅读全帖 |
|
s********x
发帖数: 914 | 4 heapSort is n/2*log(1.5n)+n*log(1.5n)
quickSort is nlog(n)
node |
|
m***p
发帖数: 86 | 5 quicksort时间最差是O(n^2)
mergesort空间上需要O(n)
heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
是比较复杂还是其他什么原因? |
|
w**2
发帖数: 8 | 6 1.quicksort 随机化后 nlogn 时间
2.mergesort 链表上 O(1)空间
3.heapsort 需要O(n)辅助空间 除非只是打印 |
|
|
j****y
发帖数: 684 | 8 heapsort 很多修改index，在内存里跳来跳去
一堆cache miss，能快就鬼了。
? |
|
|
G*********n
发帖数: 53 | 9 因为 Heapsort 会有大量的 cache 的in & out， 对cache利用不充分，所以用的最少
。对于 mergesort 需要分配一个 新的array来help，所以速度也没有比quick sort快
。相对来说，quicksort最快 |
|
b***y
发帖数: 2799 | 10 ☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Sun Jun 29 23:05:45 2008) 提到:
报错： error LNK2001: unresolved external symbol "public: static int
HeapSort::heap_size" (?heap_size@HeapSort@@2HA)
error LNK2001: unresolved external symbol "public: static int * HeapSort::heap" (?heap@HeapSort@@2PAHA)
－－－－－－－－－－－－－－－－－－－－－－
class HeapSort
{
public:
static int heap_size;
static int heap[MAX_HEAP]; //define an array of the heap
public:
HeapSort(void);
static void AddNu |
|
w****h
发帖数: 212 | 11 就是说，比如构造函数
class Point
{
Point (int x):myX(x) {};
private int myX;
}
那么程序可以直接定义Point u1(10)来定义这个实例u1,其myX=10
现在问题是，我想初始化类时传入一个数组，而不是一个整型变量，比如
class HeapSort
{
HeapSort (int* a):dataHeap(a) {};
public dataHeap[100];
}
当我定义
int a[N];
HeapSort h1(a)时，编译报错说cannot specify explicit initializer for arrays
是不是不能初始化就传入一个数组，而必须在函数里显示初始化数组 |
|
z****e
发帖数: 2024 | 12 比较 heapsort , quicksort
我怎么觉得从理论上说heapsort比quicksort 好呢？
那为什么大部分书都说 "in practice, quicksort beats heapsort"
看到有个文献是从entropy的角度考虑这个问题。太长了，结论也不清楚。
哪位大侠肯出手相救？ |
|
g***j
发帖数: 1275 | 13 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
quicksort, mergesort, heapsort，如何选择用哪个sort？ 我只知道mergesort
stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
另外，是不是只要涉及到交换的，都不stable? |
|
s**x
发帖数: 7506 | 14 heapsort related 的题 多不胜举吧？ 你为什么问这个问题？
heapsort 不搞得滚瓜熟是不行的. |
|
z****e
发帖数: 2024 | 15 请问 heapsort vs. quicksort.
基本的不提了，什么 worst case, pre-sorted, in place, etc.
不明白，看到一些资料，说 in practice, quicksort beats heapsort, because
quicksort has less comparisons on average.
有这么一说吗？觉得 less comparisons 这句话挺深刻的，有什么文献提到两者的比
较？
谢谢。 |
|
w****h
发帖数: 212 | 16 如果程序报错：
error LNK2001: unresolved external symbol "public: static int HeapSort::
heap_size" (?heap_size@HeapSort@@2HA)
如何解决？
以前遇到这个问题，似乎是开始不应该选择console application,应该用empty
project。当时重建empty project就解决了。
但现在再次遇到，在VC 2008 express edition，代码文件很多，不知道如何设置？难
道要重新建一个empty project吗？
多谢。 |
|
K*****n
发帖数: 65 | 17 Can you do a search in all cpp of your project for
"int HeapSort::heap_size"?
static class data member gets no memory allocated, you need to define one
like global variables.
say
int HeapSort::heap_size = 100; //initialization is optional |
|
K*****n
发帖数: 65 | 18 I know you define
static int heap_size;
in your class HeapSort in header file.
static class member is shared by all its class objects, so it gets no room
in objects. That's why you need make ANOTHER GLOBAL define in
your cpp file.
int HeapSort::heap_size = 100; //initialization is optional |
|
s***e
发帖数: 122 | 19 你刚好用反了，而且最好传一个长度进去。另外你的语法怎么这么怪，看着这么像Java.
class HeapSort
{
public:
HeapSort (int a[], int len):dataHeap(a), length(len) {};
private:
int * dataHeap;
int length;
} |
|
m********7
发帖数: 37 | 20 class HeapSort
{
HeapSort (int* a):dataHeap(a) {};
std::vector dataHeap[100];
} |
|
|
S******a
发帖数: 862 | 22 ......
给包子的话我写给你
多练练25很轻松
类似的，我面试的时候20min写过KMP字符串匹配
这些经典算法我都每次面试前都会过一遍
如果是电面，我就直接翻出写过的code来贴过去 |
|
|
|
f**********w
发帖数: 93 | 25 google intrasort.
If I remember it right, it begins with quicksort, but if it could not finish
in O(nlogn), it switch to heapsort. |
|
I**********s
发帖数: 34 | 26 http://en.wikipedia.org/wiki/Shuffling
"Shuffling algorithms
In a computer, shuffling is equivalent to generating a random permutation of
the cards. There are two basic
algorithms for doing this, both popularized by Donald Knuth.
The first is simply to assign a random number to each card, and then to sort
the cards in order of their random
numbers. This will generate a random permutation, unless any of the random
numbers generated are the
same as any others (i.e. pairs, triplets etc). This can b... 阅读全帖 |
|
y*******g
发帖数: 6599 | 27 heapsort就是inplace nlogn |
|
|
m****v
发帖数: 84 | 29 很可能会有一个在Palo Alto的实习机会，公司愿意给房子住两人间，或者给点钱自己
找。如果自己
找的话，可能会有交通不便、租金贵等问题，但是会自由很多。请问大家觉得哪个选择
比较合适呢。
谢谢。
同时在此汇报碰到过的面试题若干（来自不同公司的面试环节），抱歉之前没有整理过
，如果有时间
会把它们整理好再发一下。
算法、数据结构：
Prefix Tree
Kth element
BST serialization
quicksort
heap, heapsort
M links, find the Kth element
判断二叉树合法
按层打印二叉树
矩阵找最大和子矩阵
设计：
任务管理
交通系统
语言：
dynamic_cast, static_cast, ...
virtual function
exception in destructor
malloc, dealloc
polymorphism
regex in perl/python/etc.
数学、概率：
Monte Carlo: give an example and explain
Fibonacci series... 阅读全帖 |
|
|
|
|
|
h***o
发帖数: 30 | 34 Expected complexity是O(nlogn), partition很精简常数小， in-place, 每次逐个扫
数据
(cache miss少) |
|
k****n
发帖数: 369 | 35
no
This is a very interesting problem, also very chanllenging.
Worked on it for 10 mins, and finally worked it out.
For a min heap, what we can first think of is doing heap sort.
Then we have a sorted array.
How to convert it to a BST (in array)?
lets first check an example, but in extreme case:
For the sorted array 1 through 7.
The form of BST is
4
2 6
1 3 5 7
So what is it for 1 through 15?
easily to guess:
8
4 12
2 6 10 14
1 3 5 7 9 11 13 15
So it is not very hard to change an array of lengt... 阅读全帖 |
|
c*****m
发帖数: 315 | 36 搞了一上午搞出来了第一题，包含以下几点
1. 基本想法类似于HEAPSORT， 每次取HEAP 的最小值，和BST tree 当前最小位置的值
交换，然后再维护HEAP 的结构，同时取BST 中序遍历的下一个值。在整个过程中，树
的一部分变成了BST TREE, 另一部分还是HEAP 结构。
下面介绍相关的步骤。
2. 取HEAP 的最小值：粗略的想法是用HEAP[0]。这里有个问题：当HEAP[0] 被并入BST
部分以后，最小值不再是HEAP[0]，而是HEAP[0] 的右子树。可以证明HEAP[0] 被并入
BST 的时候，它的左子树已经全部在BST 里了，而它的右子树都不在BST里，因此可以
TRACK 当前HEAP 的ROOT。
3.维护HEAP 的结构。算法和SIFTDOWN 一样，但要注意的是SIFT DOWN 的时候必须要检
查当前节点的子节点是不是在BST 部分，如果是，就停止交换。要做到这一点，只需要
TRACK 住当前HEAP 的最小值，BST 里的元素都会小于它。
代码如下（HEAP 用数组heap 表示）：
//取一个BST子树最小节点的索引， 辅助函数
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 37 bubblesort,quicksort,mergesort,countsort,heapsort
至少得知道这5种的空间、时间复杂度吧 |
|
s*********5
发帖数: 514 | 38 一百万个amazon product id，问过去一小时销售量top 10的(map-
reduce)
这个还要用到map-reduce, 答错方向了吧。
这是从N个数中找最大的k个数，修改一下quicksort, 或者用heapsort, with a heap
of size of k.
heap build time: Nlog(k)
sort time: klog(k)
here N=1,000,000, k = 10,
total operation less than 4 million, 2G clock, 也就几个微秒的事情。
数据量不上T，单次map计算时间少于1分钟，都没必要map-reduce |
|
x*******5
发帖数: 152 | 39 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
x*******6
发帖数: 262 | 40 quicksort空间是O(1)吧，mergesort有最坏情况？一直都是O（nlogn）时间O（n）空间
吧。
磁盘上mergesort有优势。heapsort效率和quicksort相当但是多些额外操作所以一般没
人用吧。 |
|
r********d
发帖数: 7742 | 41 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
of-K 和 少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
被beat, 因为cache的访问速度比内存寻址快两个数量级。
Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
比较大，是quicksort的好几倍。一般比Quicksort慢。
Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论
分析。constant factor还不错，比merge sort... 阅读全帖 |
|
d**********x
发帖数: 4083 | 42 作为一个补充，stl的sort是introsort，除了这里提到的对quicksort的优化以外，还
可能会在quicksort递归深度过深的时候切换成heapsort
median-
factor |
|
g***j
发帖数: 1275 | 43 谢谢大牛指点！ 能不能详细谈谈这里的cache的问题，我一直困惑的是为啥heapsort用
得少，既然你谈到了他的致命的弱点，我还是不太清楚，请可以详细谈谈么？
另外，你这里constant factor具体指的什么？是 cNlgN里面的c么？
median-
factor |
|
g***j
发帖数: 1275 | 44 另外你说的insertion sorting, 应该不是用到了交换吧，它应该用到的是平移和插入
，跟quicksort和heapsort里面的纯交换两个元素的位置，不是一个意思吧？
median-
factor |
|
s*****t
发帖数: 11 | 45 堆排序算法如下
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.size downto 2
3 exchange A[1] with A[i]
4 A.size = A.size - 1
5 MAX-HEAPIFY(A, 1)
算法书上说
1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
那么, 整个算法的时间复杂度是
O(N) + O(lg(N-1)) + O(lg(N-2)) + ... O(1)
= O(N + lg(N-1) + lg(N-2) + ... 1)
= O(N + lg(N-1)!)
= O(lgN!)
比快速排序的 O(NlgN) = O(lg(N^N)) 还要快?
迷惑了,求大牛指点. |
|
l*******b
发帖数: 2586 | 46 log (n!)本来就和 n log(n)是同阶的呀，有什么问题？
heapsort本来速度就和quicksort差不多， quicksort的hidden factor小一点，
locality好一点吧 |
|
|
|
s********x
发帖数: 914 | 49 我找到proof啦 - quick sort worst case is nlog(n)
Data Structures
& Algorithms
in Java
Second Edition
Robert Lafore
page 725
TABLE 15.3 Comparison of Sorting Algorithms
Sort Average Worst Comparison Extra Memory
Bubble O(N2) O(N2) Poor No
Selection O(N2) O(N2) Fair No
Insertion O(N2) O(N2) Good No
Shellsort O(N3/2) O(N3/2) — No
Quicksort O(N*logN) O(N2) Good No
Mergesort O(N*logN) O(N*logN) Fair Yes
Heapsort O(N*logN) O(N*logN) Fair No |
|
|
