[問題] heapsort
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
推
01/08 06:09, , 1F
01/08 06:09, 1F
→
01/08 06:09, , 2F
01/08 06:09, 2F
→
01/08 06:11, , 3F
01/08 06:11, 3F
→
01/08 06:11, , 4F
01/08 06:11, 4F
→
01/08 06:12, , 5F
01/08 06:12, 5F
→
01/08 06:12, , 6F
01/08 06:12, 6F