《编程珠玑》10000000个数文件排序求解释姐妹篇

显示全部楼层 · 2021-1-27 06:28:24

在完成了的10000000个数的正常文件排序后，作者又提出了如果某个数最多重复10次，该如何求解。
网上的资料表明需要用4位来标明出现的次数。
但我一直没能理解该如何操作。
希望大家能提供思路一下。。。
参考网址：
http://hi.baidu.com/diwayou/blog/category/%B1%E0%B3%CC%D6%E9%E7%E1
分 -->

千问 · 2021-1-27 06:28:24

关于具体思路，请google“计数排序”

千问 · 2021-1-27 06:28:24

如果是32b的整数，这个数据量，随便一个n*log(n)的排序，无论在时间还是空间上都优于计数，何况还有2n时间复杂度的基数。

千问 · 2021-1-27 06:28:24

作者的意思好像是不仅要记录该值是否出现，还要记住出现的次数。
如果仅仅是排序的话，那方法还是直接用位向量就可以了。
如果还要记住出现的次数，就不清楚这个位向量该如何分配了，望指教。。。

千问 · 2021-1-27 06:28:24

用4位来标明出现的次数，这个已经很清楚了
1个比特只能表示出现0次和1次
4个比特能用来计数，0～15次都可以
如果用32个比特，就是用intA[N]这样的数组来排序
排序的结果就是A[N]里面的数值
如果A==0，说明i这个数没有出现
如果A==N，说明i出现了N次

千问 · 2021-1-27 06:28:24

引用4楼erorr的回复:用4位来标明出现的次数，这个已经很清楚了
1个比特只能表示出现0次和1次
4个比特能用来计数，0～15次都可以
如果用32个比特，就是用intA[N]这样的数组来排序
排序的结果就是A[N]里面的数值
如果A==0，说明i这个数没有出现
如果A==N，说明i出现了N次
hiError:有几个疑问。。。
1:intA[N],如果有10000000个数，那N==10000000？
2:A==0,也就是说A里面存放的仅仅是出现的次数，int占32位，剩余的28位就不用了啊？

千问 · 2021-1-27 06:28:24

我在最顶层帖子中的链接作者的做法应该是这样的：
1000000个数中每8个为一组。
inta[N/8]中记录的是这8个数出现的次数。每个数的次数占用4位，所以32位被8个数占用。
所以当我们要想取这个数的次数的时候需要
1：先获取该数在数组中的索引i>>3
2：获取该数的次数的索引i&0x07
3:移位则为(i&0x07)*4，获取次数
4:计算最新次数

《编程珠玑》10000000个数 文件排序求解释 姐妹篇

《编程珠玑》10000000个数文件排序求解释姐妹篇