是否可以实现"in-place"迭代LSD n-radix排序？澄清一下：我已经阅读了wikipedia atricle就地MSD基数排序 . 它说：
计数排序用于确定每个bin的大小及其起始索引 .
因此需要一个辅助数组来存储索引，但如果这就是它需要的全部，我仍然认为它是一个就地算法（因为这个数组的大小为n，对于一个n-radix排序） . 我还阅读了this answer，再次实现了递归MSD基数排序 . 那个也没有针对n-radix排序的一般实现 .
是否可以实现"in-place"迭代LSD n-radix排序？澄清一下：我已经阅读了wikipedia atricle就地MSD基数排序 . 它说：
计数排序用于确定每个bin的大小及其起始索引 .
因此需要一个辅助数组来存储索引，但如果这就是它需要的全部，我仍然认为它是一个就地算法（因为这个数组的大小为n，对于一个n-radix排序） . 我还阅读了this answer，再次实现了递归MSD基数排序 . 那个也没有针对n-radix排序的一般实现 .
1 回答
编辑：我终于在答案中描述了我的算法：https://cs.stackexchange.com/questions/93563/fast-stable-almost-in-place-radix-and-merge-sorts
是 . 将输入数据虚拟地分成一些大小的页面（4 KB将很好地服务） . 然后在消耗数据时重用这些页面 . 但是你需要一些额外的内存 - 初始桶最多n页，下一页指针（每页一个指针），每桶有3 * n个head_page / current_page / current_write_ptr指针
算法：
Alloc n页面并将它们放入免费页面列表中
处理输入数据，将条目移入其存储桶 . 处理完整页输入数据后，将此页面添加到空闲页面列表中 . 填充整个存储桶页面后，将其添加到此存储桶页面的列表中，并从空闲列表中分配新的存储桶页面 . 您将最终得到每个bicket的页面列表，此列表中的最后一页已部分填充
移动数据以按桶的顺序将其装回原始数组
当然，如果你需要多个LSD传递，你可以跳过第3步，除了最后一次传递并直接从第2步 Build 的列表开始每个排序传递 . 但是它将需要n个额外的页面 .