UC Berkeley CS61B Homework 10

CS61b的最后一次作业，终于把61b修完了！

这次作业也比较简单，但是依然难以理解+_+，可能是我英语不太好的缘故=。=。

这次作业是实现 Counting Sort 和 Radix Sort，input是一组整数，是16进制的，integer在java里面是占32个bits，如果以16进制表示的话，一共有8位（每4个bits表示一位16进制数，比如FFFFFFFF）。assume input全部是正数，对input进行radix sort，所以总共进行了8次每一次的 radix sort 用 counting sort 来实现。

下面是输出，一组是16进制的，一组的10进制的。yell方法我稍微改动了一下。

很巧妙的方法，把输出改了下可以看到每一次的结果：

一个小细节写错，对着counting sort的教程debug了好久

最后一次作业，从counting sort 到radix sort，按照lecture 所讲转化成代码即可。
实现counting sort时，注意在item哈希表x中，key就是截取出来的某一位，value就是原本的一长串数字。



我终于完成了cs61b！


Party time!!!!!!!

CS61B搞定，求学分

交作业，发现lecture里面radix sort讲的不是很清楚，所以一开始弄错了一点。写下给后来人做点参考。radix sort原理是：将十进制的整数转化为16进制的整数（当然题目中是反过来输入，都差不多），其好处在于，16进制的整数可以利用（&15）取出最低4位，第二低四位，一直到最高四位进行countingSort（bucket number 和 新产生的小于16的数range比较符合，可以进行countingSort），注意countingSort传回的int[]数组不是那个4位的数组，而是原先传进去的keys[]拷贝后的数组（因为4位产生的数组传回去没有意义，需要将原先的数组的拷贝数组传回去，因为keys不能改变），然后迭代地进行8次，根据stable性质（每次低位排序后，若其高位相同，则在高位的排序中这两个数字位置关系保持不变）即可得到排序后的数组。

cs61b done...

终于搞完cs61b了。。泪流满面

终于完成了cs61b！！好鸡冻！！