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

Question

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

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

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

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

Answer 1

我以前没有听过这些确切的术语，但它们对我来说是有意义的。我不认为这个术语真的很重要，只要你了解他们在做什么。

如果要创建列表的排序副本，则可以从旧列表的最小值逐个创建新列表中的每一项；“直”似乎是对此的合理描述。

OTOH，如果你在适当的位置排序一个列表，那么每次你把一个新的项目移到列表的头，你就必须把先前在列表中的项目向后移动，这样才能腾出空间。在数组列表中，最便宜的方法是只保留新的最小项和旧项交换位置:交换。(在链接列表中，让列表的整个尾部滑回一个位置会更快。)

教科书往往集中在就地分类上.

Answer 2

这两种算法都有相同的技术。但是，两者之间的唯一区别是，在选择排序中，每次进行比较时只更新索引，并且在迭代结束时进行交换。另一方面，在交换排序中，当右边的元素小于当前位置上的元素时，交换就会发生。

作为参考，您可以看到以下2分钟的视频:插入排序：https://www.youtube.com/watch?v=JU767SDMDvA Exchange排序：https://www.youtube.com/watch?v=v0ipy1h-TPM