Re: [問題] BucketSort做字串排序(linked list)
※ 引述《HUGOZVC (HUGO)》之銘言：
: 小弟要用single linked list寫Bucket Sort來排序字串，
: 字串的Alphabet={0,1,...,9, A, B,..., Z, a, b,..., z}
: 0 1 ... 9 10 11 ... 35 36 37 ... 61
: 排列優先順序是從左到右，
: 如果我有下面這幾個字串，
: the last string, second string, first string, st 7 7 6, st 1 0 3, st 5 5 4
: 排序之後應該是
: first string, second string, st 1 0 3, st 5 5 4, st 7 7 6, the last string
: 數字的部分很好處理，
: 讀進來的如果是0，就存到list[0]，
: 讀進來的如果是5，就存到list[5]，依此類推。
: 那字母的部分我就沒有頭緒了，
: 如果讀進來的是A的話，我要怎麼把A存到list[10]呢？
: 如果讀進來的是b的話，我要怎麼把A存到list[37]呢？
: 我目前的想法是讀進來之後，
: 先去判斷目前的值排在Alphabet這個array的第幾個位置(如n在第n個位置)，
: 然後就將目前的值存在list[n]，
: 不過這個作法看起來有點笨，
: 不知道有沒有更有效的方法？
: 希望各位先進看得懂我的問題，
: 煩請指點迷津，感激不盡。
: ※ 編輯: HUGOZVC 來自: 208.123.162.2 (11/01 23:40)
: 推 snowlike:LList為什麼要用到這種矩陣？數字對應轉換可以參考ASCII 11/02 01:01
沒有理由要用 Linked List.
Bucket Sort 需要的長度已知,
另外 Bucket Sort 需要 random access (by index)
這個正是 linked list 的弱項,
你直接用一個 62-element 的 array 就好了吧.
另外 bucket sort 不是單純是把東西放進 bucket 而已
嗎? 應該做不到你想要的 sorting 效果
anyway, 判斷要放哪一個 bucket 很簡單吧
if (c >= '0' && c<='9') {
index = c - '0';
} else if (c >= 'A' && c <= 'Z') {
index = c - 'A' + 10;
} else if (c >= 'a' && c <= 'z') {
index = c - 'a' + 36;
}
更直接的, 建一個 256-element 的 array,
第 48 至 57 ('0' 至 '9') 放 0 - 9,
第 65 至 90 ('A' 至 'Z') 放 10 至 36
第 97 至 122 ('a' 至 'z') 放 37 至 61
其他放 -1
然後直接做
index = INDEX_TABLE[c];
if (index >= 0) {
.....
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.155.236.82
推
11/03 02:42, , 1F
11/03 02:42, 1F
→
11/03 02:44, , 2F
11/03 02:44, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：