作者adrianshum (Alien)
看板C_and_CPP
标题Re: [问题] BucketSort做字串排序(linked list)
时间Mon Nov 2 10:59:50 2009
※ 引述《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
1F：推 jinmin88:可用ternary partition q-sort 时间复杂度大概是O(n^2) 11/03 02:42
2F：→ jinmin88:另外我记的还有一篇论文(改良t-qsort)可以降低到O(nlogn) 11/03 02:44