algorithm - 直接选择排序与交换选择排序

Question

直接选择排序与交换选择排序有什么区别？我今天陷入了一场小辩论——我的教授在他的讲义中使用了这两个术语。维基百科和任何教科书或网站会给你的选择排序就是他所说的“交换选择排序”。

我以前从未听说过“交换选择排序”这个术语(只有“选择排序”)，并且在网上找不到任何关于以前术语的相关资源。此外，“交换排序”重定向到维基百科上的冒泡排序。

我也从来没有听说过“直选排序”这个词，网上也找不到相关的资源。他的笔记指出这是选择排序的一个版本，它使用辅助数组而不是就地排序，从最小到最大的元素一个一个地填充它。当我提出这个问题时，他声称它是旧的，并且仅仅因为它没有出现在谷歌上并不意味着它是不正确的。然而，我在 Google 上发现了更多晦涩的东西，而选择排序之类的东西将在网络上拥有大量资源。

那么，这些算法有其他名称吗？他只是把名字弄错了吗？谁是对的？

Answer 1

我以前从未听过这些确切的术语，但它们对我来说很有意义。我不认为术语真的那么重要，只要您了解他们在做什么即可。

如果您正在创建一个列表的排序副本，您可以从旧列表的最小值开始一个接一个地创建新列表中的每个项目；对于这个，“直”似乎是一个合理的描述。

OTOH 如果您在原地对列表进行排序，那么每次将新项目移动到列表的头部时，您都必须向后移动之前在那里的项目以腾出空间。在数组列表中，最便宜的方法是只留下新的最小项和旧项交换位置:交换。 (在链接列表中，让列表的整个尾部向后滑动一个位置会更快。)

教科书往往专注于就地排序。