→ keepoo:我也是想說變成radix sort...但怕怕 03/11 00:26
推 NOtWorThy:THX!! 03/11 00:29
推 Lautreamont:n+10 (0,..,9) 03/11 01:28
→ sa074463:=.="打錯 03/11 08:29
※ 編輯: sa074463 來自: 61.62.95.211 (03/11 08:29)
※ 引述《NOtWorThy (分子小於64)》之銘言：
: 第13題
: a b c要如何做呢 //沒想法 QQ
: 第14題
: 想請問一下
: hash 如何來sort data阿
------------------------------------------------
把hash fuction定義為:Hash(x,i)=x的第i個位數值
先把data放在一個A[1...n]，Hash table為H[0...9]
algorithm如下:
m=A中最大位數個數;//所以跑m回合
for i=1 to m
{
for j=1 to n
Hash(A[j],i); //把資料放到桶子
for j=0 to 9 //回收桶子
回收Hash table裡的元素然後放到A這個矩陣裡
}
time complexity: O(m*(n+10))→m會是個常數
所以最後為O(n)
有錯請指正XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.62.201.126