UC Berkeley CS61B Homework 10

done hw10

楼上的各位为啥都说很简单呢，我读了半天题目还是不怎么懂。勉强做出来了，先贴结果，之后再自己慢慢理解一下。

基本上就是copy老师上课讲的内容。。。counting sort注意两点: 取位后的digit[i]，就是原来的x[i].key。最后结果输出赋值时，已经确定digit[i]的position，但需要用keys[i]来赋值。
完结撒花！ 这个教授的课讲得确实好！！有点恋恋不舍。。。。

还剩个Project2,3。。暂时就先放着了，完结~

打卡打卡，最后一次作业，cs61b完成啦。
由于是对数据的某一部分进行排序，要用老师课上讲的一个小trick。先将counts数组扫描一遍，确认每个区间前有多少个数，这样才能正确的将原数组中的数搬运到新数组的正确位置。
感觉现在在2014版本中打卡的人并不多了。那位用雅人叔头像的同学，我每次交作业都在你后面，现在我比你先完成啦啦啦啦啦。

就只剩下最后一个lab了，这次作业比较简单，没有用hashtable，感觉如果用了可以更快些

1. /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=58154:/Applications/IntelliJ IDEA.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/tools.jar:/Users/Lim/@inbox/cs61b14/hw/hw10/out/production/hw10 sort.Sorts
   
2. keys are [ 60013879 11111119 2c735010 2c732010 7fffffff 4001387c 10111119 529a7385 1e635010 28905879 11119 0 7c725010 1e630010 111111e5 61feed0c 3bba7387 52953fdb 40013879 ]
   
3. keys are [ 0 1e630010 1e635010 2c732010 2c735010 7c725010 111111e5 529a7385 3bba7387 11119 10111119 11111119 28905879 40013879 60013879 52953fdb 4001387c 61feed0c 7fffffff ]
   
4. 
   
5. Process finished with exit code 0
   

复制代码

hw10也做完了，只剩下pj3了

交作业，开始把radixsort和countingsort with values搞混了，countingsort原理感觉和题目要求是矛盾的，题目必须用带链表的hashtable的数据结构，这样题目的countingsort就不像它的prototype那么简单了，后来明白是为了radixsort做准备

本次作业加深了对counting sort 和radix sort的理解！！只有自己做作业才知道自己有多菜，要继续努力！！注意点以及思路
(1)readme.pdf提到本次容器中待排序的数字都是 base-16 digit，就是16进制的意思，可以看到在main方法中有一个测试输入，并且有 Integer.parseInt()方法。
(2)由于int是32位的，whichDigit这个变量在0-7之间。因此给某个指定的whichDigit变量，我们就对这个整个32位int数组中的某4位进行排序，比如whichDigit=0,我们就是对32位的前4位进行排序。
这里要注意一点，我们所说的32位是以2进制的标准来看的，如果以16进制来看，int类型变量只有8位。
(3) 我们在counting sort 方法里要新构建三个数组(实际上也可以只用2个，但是为了我们自己画图便于理解算法的思路，我们用三个数组）
第一个是AfterBit数组，长度为keys.length。这个数组是存放了所有即将被排序的32位数，并将其转换为4位数的临时数组。
第二个是count数组，长度为16。为什么是16，一个四位的二进制的范围是0-15，因此count数组的长度是16。这个count数组代表AfterBit数组中的元素 的 某个指定数 之前所有的数字总和。
感觉讲的不是很清楚，但是如果我们自己理解了counting sort的原理，去画个图，上面的拗口的语句就能理解。
(4)完成了counting sort以后，在radix sort中我们就可以利用写好的counting sort。循环内传入输入数组，whichDigit的变量从0到7。这样就得到了最后的排序数组。

贴图

补充内容 (2019-5-27 10:24):
(3)中的第三个数组是我们的result 数组，长度就是keys.length。用于存放返回的结果

补充内容 (2019-5-27 10:32):
(3)中 AfterBit数组将32位数转化为4位数的处理方式是  afterBit[i]=(keys[i]>>(whichDigit*4))&15;

shendezhuti 发表于 2019-5-27 10:22
本次作业加深了对counting sort 和radix sort的理解！！只有自己做作业才知道自己有多菜，要继续努力！！注 ...

写一个图示流程，帮助自己记忆。