放置“迭代LSD n

2018-06-03 14:58:21

是否有可能实现一个“就地”迭代LSD n-radix排序？澄清：我已经阅读了就地MSD基数排序的维基百科atricle。它说：

计数排序用于确定每个bin的大小及其起始索引。

因此需要一个辅助数组来存储索引，但如果这只是它所需要的，我仍然认为它是一个就地算法（因为这个数组只有n个大小为n的基数）。我也读过这个答案，再一次执行递归MSD基数排序。那个也没有一个n-radix排序的通用实现。

是。实际上将输入数据分割成一定大小的页面（4 KB将很好地工作）。然后在您使用数据时重新使用这些页面。您将需要一些额外的内存 - 最多可达n页初始桶，下一页指针（每页一个指针），3 * n指针每个桶的head_page / current_page / current_write_ptr

算法：

分配页面并将它们放入空闲页面的列表中

处理输入数据，将条目移入其桶中。处理完整个输入数据页面后，将此页面添加到空闲页面列表中。一旦完整的桶页面被填充，将其添加到这个桶页面的列表并从空闲列表中分配新的页面。您将以每个bicket的页面列表结束，此列表中的最后一页部分填满

移动数据以按照桶的顺序回到原始数组

当然，如果您需要多个LSD通行证，您可以跳过第3步，除了最后一个通行证，并直接从第2步构建的列表中开始每个排序通道。但是，它需要n个额外的页面。

链接地址: http://www.djcxy.com/p/12219.html