直选择排序与交换选择排序 [英] Straight selection sort vs. exchange selection sort

问题描述

直接选择排序之间的区别是什么与交换选择排序？今天我到一个小的争论 - 我的教授用他的讲义这两个术语。选择排序，维基百科和任何教科书或网站都会给你的是什么，他呼吁交换选择排序。

What is the difference between straight selection sort vs. exchange selection sort? I got into a little debate today - my professor uses these two terminologies in his lecture notes. The selection sort that Wikipedia and any textbook or website will give you is what he is calling "exchange selection sort".

我从来没有听说过（只有选择排序）中使用的术语交换选择排序，并不能找到对前者的术语任何相关的资源联机。此外，交换排序重定向到维基百科上冒泡排序。

I've never heard the term "exchange selection sort" used before (only "selection sort"), and cannot find any relevant resources on the former terminology online. Also, "exchange sort" redirects to bubble sort on Wikipedia.

我还从来没有听说过使用的术语直选择排序，并不能找到任何相关的资源联机。他说明指出，这是一个版本的选择排序的，它使用一个辅助阵列，而不是就地排序，填充它一个接一个从最小到最大的元素。当我提出了这个问题，他声称这是旧的，而只是因为它不来在谷歌并不意味着它是不正确。但是，我发现在谷歌更为晦涩的东西，有点像选择排序将有在网络上的资源的巨量。

I've also never heard the term "straight selection sort" used before, and cannot find any relevant resources online. His notes state that it's a version of selection sort which uses a secondary array rather than an in-place sort, populating it one-by-one from the smallest to largest element. When I brought up the issue he claimed it was older and that just because it doesn't come up on Google doesn't mean it's incorrect. However, I've found far more obscure things on Google, and something like selection sort is going to have a massive amount of resources on the web.

所以，做这些算法去了其他的名字？难道他只是有名字错了吗？谁是对的？

So, do these algorithms go by other names? Does he simply have the names wrong? Who is right?

推荐答案

我从来没有听说过这些具体条款，但他们做出了意义。我不认为术语是真的那么重要，只要你明白他们在做什么。

I hadn't heard those exact terms before but they make sense to me. I don't think the terminology is really that important as long as you understand what they're doing.

如果您要创建一个列表的排序副本，您可以创建在新的列表中的一个接一个从最小的旧列表中的每一项; 直似乎合理的说明，任何这一点。

If you're creating a sorted copy of a list, you can create each item in the new list one-by-one from the minimum of the old list; ‘straight’ seems as reasonable a description as any for this.

OTOH如果你每次一个新的项目移到列表的头部时间排序就地列表，然后，你必须移动，这是previously有倒退，以腾出空间的项目。在一个数组列表，这样做只是为了留下新的最低项目和旧项目交换位置最便宜的方法：进行交流。 （在一个链表，将更快地让该列表的整个尾滑回一个地方。）

OTOH if you're sorting a list in-place then each time you move a new item to the head of the list, you have to move the item that was previously there backwards to make room. In an array list the cheapest way to do that is just to left the new minimum item and the old item swap places: an exchange. (In a linked list it would be quicker to let the whole tail of the list slide back one place.)

教科书往往集中在就地分拣。

Textbooks tend to concentrate on in-place sorting.

这篇关于直选择排序与交换选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！