一道面试算法题 - 范文无忧网

[三支一扶面试技巧：面试怎么演讲]三支一扶面试技巧之“演讲”技巧： 1. 分析自己报考岗位的特点，在面试前找一些比较有代表性的优秀人物和故事，提前准备，便于在考场上应用自如。 2. 提出一个问题，进一步引导听众。...+阅读

这是典型的桶排序算法，

假设有9个桶，每个桶里存放N个数字。桶应该是唯一的。

所以推出结论：

1。桶是唯一的（我们因此可以利用Hashtable的唯一性来做到）；

2。桶内成员可以不排序，因此可以利用数组或者Vector来做到；

3。Hashtable需要主键key来唯一标识，正好数字1~9是不重复的，是唯一的；

3。把每个数值的第一位取出来，以第一位值做为key找到hashtable中的相应vector，再将vector.addElements（该数值）；

4。完成；

具体做法：

1.生成桶，9个桶，每个桶以数字1~9做为主键命名

Hashtable table=new Hashtable();

for(int i=1;iVector vector=new Vector();

table.put(new String(i), vector);

}

2. 遍历每个数字，将当前数字的第一位分解出来，办法有很多种，比如除十法，这里介绍直接转字符串再取第一位法：

假设你的要处理的数字们放在数组里面int[] tmp;

for(int i=0;iint num=tmp[i];

String str=new String(num);

char ch=str.charAt(0);

//压入到桶里，先把想要的桶找到，利用主键

Vector vect=(Vector)table.get(＂＂+ch);

//找到桶后再把数值压到桶里

vect.addElements(new Integer(num));

}

//取出来的时候，有多种方法，一种是利用key取出Vector，再遍历Vector，得到其中元素，元素的key为String，内容为Integer

另一种方法是先遍历hashtable再遍历vector

同样的应用还有给一幅被洗过的扑克牌进行升或降排弃，因此可以建13个桶（A~K），每个桶内的牌再按花色排序（相当于对Vector排序，也可以不用Vector而直接用数组或者ArrayList等等）

我看了你的修改提问，现回答如下：

即使不能使用java己经封装好的Hashtable类，自己也可以很轻易地利用代码编写出类似于Hashtable的集合类，用来包容其它对象，并以主键key来唯一标识.

如果你不想这样思考，那么直接用数组来实现桶排序也很方便，外层数组长度是固定的，即1~9共9个数组元素 Elements e=new Elements[9]。

这九个数组元素不是数字，必须是你自定义的类。并用这个类形成链表结构

比如：

public class Element{

int data；//存数字

Element next=null；//下一个元素是谁

}

比如有数字 51,52,53 这三个数都是以5打头，那么他们应该放在一个桶里面，即第五号桶，也就是外层数组的第个元素中。

if（判断该数字，是否应该放在5号桶）{

Elements tmp=new Elements();

tmp.data=该数字；

Elements current=e[4];

if(current==null){current=tmp；}//如果该桶以前从未放过数字，则放进去的就是头部，直接引用就行了，比如51应该放在头部

else{//如果该桶以前己经放过数字，如51，己经放了，现在放52。52就应该做为51的next元素，而53就是52的next就行了

while(current!=null){current=current.next；}//遍历，从而取到最后一个元素的引用

//取到最后一个元素后，current=tmp；即可，这样就形成了链表结构

}

通过上述代表形成的结果是，外层结构是9个元素组成的数组

每个数组元素是Elements类对象形成的链表结构，有头有层通过next字段串连起来。

如果要排序，只需要对每个链表内部进行排序就可以了