大数据量排序算法

无心人

这么做行不行？ 使用方法三 假设数字a 高位掩码是H，低位掩码是L 预先初始化一个数组A 将A[a & L]加一 如何？

liangbch

等有空的时间，把这3篇论文描述的算法重新实现一下，看看速度如何（预计应该不会超过我的程序）。另外，我又想到一个高cache命中率的分段排序算法，该算法的特点是，内存写采用顺序方式进行，因此L2 cache命中率较高，速度应该可以超过我现有的程序，不过内存占用率也是最高的，如对32bit 整数排序，辅助空间需要原始数据占用空间的1.5倍多。

无心人

我也能写个辅助空间是(n + k)的算法 我想k最大是最大整数的1/16 k越大，速度越快

liangbch

1. 这几天仍然在继续研究大数据量快速排序算法。 2. 昨天重新实现了论文《 无符号整数按位快速排序算法》，发现这个算法有局限性，只适用于最大关键字比较小的序列的排序。另外，文章对其复杂度的叙述也不太清楚，更精确的说法是，该算法的复杂度是O(ceil(log2(max+1))*n), max是最大关键字，ceil为向上取整函数，并不是作者宣称的O(n). 而快速排序的复杂度是O(log2(n)*n),显然，当max大于数组长度时，该算法慢于快速排序。实验表明，max 等于数组长度时，该算法略快与快速排序，原因是该算法对内存读取时，内存地址的连续性好于快速排序，故L2 cache的命中率比快速排序更高，所以速度比快速排序快些。

无心人

如果不考虑辅助内存的问题 只要一次就能排好序 但目前关键是如何分组即保证排序速度又保证内存使用

hellomfk

great code appreicate.

djj99888

下载下来学习学习！

djj99888

为什么下载不下来？

djj99888

不知道为什么下载不下来！

KeyTo9_Fans

欢迎你来到数学研发论坛。 下载$1$个附件至少需要消耗$1$枚金币。 你的金币数为$0$，所以不能下载。 金币可以通过发贴获取。 每发$1$张贴子就可以获得$1$枚金币。 如果发够了$5$张贴子，还有机会赢得优秀新人奖。 希望这里可以给予你知识和乐趣。