作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] heapsort
时间Sat Jan 7 21:09:21 2012
Let A be an array of n arbitrary and distinct numbers
A has the following property: If we imagine B as being sorted version of A,
then any element that is at position i in array A would, in B,
be at a position j such that |i–j| <= k
In other words, each element in A is not farther than k positions away from
where it belongs in the sorted version of A
Suppose you are given such an array A, and you are told that A has this
property for a particular value k (that value of k is also given to you)
Design an O(n lg k) time algorithm for sorting A.
网路上的解法是这样:
http://algnotes.wordpress.com/2010/06/08/150/
可是我看不太懂这样跟2k有甚麽关系@@
请问有人可以举简单的例子来说明网路的解法吗?
还是有更好的方法呢?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.118.32
1F：推 springman:那个答案是对的。只是我总觉得应该建 k+1 个元素的 01/08 06:09
2F：→ springman:minimum heap 就可以，为什麽需要 2k 个元素呢？ 01/08 06:09
3F：→ springman:将最小的 k+1 个元素建成一个 minimum heap 01/08 06:11
4F：→ springman:输出最小值、并再加下一个元素进来 01/08 06:11
5F：→ springman:重复一直做应该就可从小输出到大才对 01/08 06:12
6F：→ springman:从中间做起才需要用到 2k 个元素 01/08 06:12