替换选择排序v.选择排序

Question

我一直在做一些关于替换选择排序的研究，但是我找不到它的任何实现，也找不到一个好的、彻底的替换选择排序的实现！也许我找得还不够仔细，但是Google把替换选择排序和选择排序混淆了……所以这让我想知道：

选择排序和替换选择排序的真正区别是什么？

我在哪里可以找到替换选择排序的实现(或编写它的指南)？

替换选择排序的特征是什么使它比其他排序算法更可取？

这个算法还有其他名称吗？

Answer 1

替换排序仍然用于外部排序，因为它将产生最少数量的要合并的字符串，而合并是排序中开销最大的部分。使用的方法比提供的优秀示例templatetypedef稍微复杂一点，但基本上它缓冲了许多记录，对它们进行排序，收集不连续的记录，如-1 1等，并将它们保存在缓冲区中，写出序列的低位部分，填充空白空间，再次排序，从缓冲区合并适合的任何记录，并重复，直到序列无法继续，然后它转储序列，从序列记录和新输入记录中取出缓冲的记录，从下一个字符串开始。重复到输入的末尾。

在一些应用程序中，不需要合并，因为替换排序会将序列记录扫出，然后在稍后将它们重新插入到正确的位置。当霍尼韦尔和IBM在1964年推出这种产品时，这对许多商业客户来说是一个惊喜。