插入排序与选择排序

选择类别:

给定一个列表，获取当前元素，并将其与当前元素右侧的最小元素交换。

插入排序:

给定一个列表，获取当前元素并将其插入到列表的适当位置，每次插入时调整列表。这类似于在纸牌游戏中排列纸牌。

选择排序的时间复杂度总是 n(n - 1)/2，而插入排序的时间复杂度最低为 n(n - 1)/2，因此插入排序的时间复杂度更高。一般来说，它将采取较小或相等的比较，然后 n(n - 1)/2。

资料来源: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

插入排序和选择排序都有一个外部循环(在每个索引上)和一个内部循环(在索引的子集上)。内部循环的每次传递都以未排序区域为代价，将已排序区域扩展一个元素，直到耗尽未排序元素为止。

不同之处在于内部循环的作用:

• 在选择排序中，内部循环位于 没有分类元素之上。每次传递选择一个元素，并将其移动到其最终位置(在排序区域的当前末尾)。

• 在插入排序中，内部循环的每次传递都迭代 解决了元素。排序的元素被置换，直到循环找到正确的位置插入下一个未排序的元素。

因此，在选择排序中，按输出顺序找到已排序的元素，并且一旦找到它们就保持不变。相反，在插入排序中，没有分类元素保持不动，直到按输入顺序使用，而排序区域的元素则不断移动。

就交换而言: 选择排序每传递一次内部循环就进行一次交换。插入排序通常将要插入的元素保存为 temp 之前内部循环，为内部循环留出空间，以便将已排序的元素向上移动一个，然后将 temp复制到插入点。

这种混淆可能是因为您正在比较对 连结清单排序的描述和对 数组排序的描述。但我不能确定，因为你没有提到你的消息来源。

理解排序算法最简单的方法通常是获得算法的详细描述(而不是模糊的东西，如“这种排序使用交换”。某个地方。我不是说“在哪里”) ，得到一些扑克牌(5-10应该足够简单的排序算法) ，并运行手工算法。

选择排序: 扫描未排序的数据，寻找剩余的最小元素，然后将其交换到排序数据后立即出现的位置。重复，直到完成。如果对列表进行排序，则不需要将最小的元素交换到位置，而是可以将列表节点从旧位置移除，并将其插入到新位置。

插入排序: 在已排序的数据之后立即获取元素，扫描已排序的数据以找到放置它的位置，并将它放在那里。重复，直到完成。

插入排序 可以在它的“扫描”阶段使用交换，但是没有必要，而且这不是最有效的方法，除非你排序一个数据类型的数组: (a)不能移动，只能复制或交换; (b)复制比交换更昂贵。如果插入排序确实使用交换，它的工作方式是同时搜索 还有将新元素放在那里的位置，只要前面的元素大于前面的元素，就重复交换新元素。一旦你到达一个不大的元素，你就找到了正确的位置，然后你就可以移动到下一个新元素。

简而言之，我认为选择排序首先搜索数组中最小的值，然后进行交换，而插入排序获取一个值，并将其与留给它的每个值(后面)进行比较。如果该值较小，则进行交换。然后，再次比较相同的值，如果它小于后面的值，则再次进行交换。 我希望这是有意义的！

我将再试一次: 考虑在几乎排序的数组的幸运情况下会发生什么。

在排序时，数组可以被认为由两部分组成: 左侧排序，右侧未排序。

插入 sort ——选择第一个未排序的元素，并尝试在已经排序的部分中为它找到一个位置。由于您从右到左搜索，所以很可能发生的情况是，您要比较的第一个排序元素(最大的一个，最右边的部分)比选中的元素要小，因此您可以立即继续下一个未排序的元素。

选择排序-选择第一个未排序的元素，并尝试找到整个未排序部分中最小的元素，如果需要，则交换这两个元素。问题是，由于正确的部分是未排序的，因此每次都必须考虑每个元素，因为您不可能确定是否存在比选中的元素更小的元素。

顺便说一句，这正是 堆排序在选择排序方面所做的改进——由于 很多，它能够更快地找到最小的元素。

选择排序: 当您开始构建排序的子列表时，算法确保排序的子列表始终是完全排序的，不仅根据它自己的元素，而且根据完整的数组，即排序的和未排序的子列表。因此，一旦从未排序的子列表中找到新的最小元素，它就会被添加到已排序的子列表的末尾。

插入排序: 该算法再次将数组分成两部分，但这里的元素是从第二部分中挑选出来，并插入到第一部分的正确位置。这从来不能保证第一部分是按照完整数组排序的，尽管在最后一次传递时，每个元素都处于正确的排序位置。

两种算法通常都是这样工作的

第一步: 然后从未排序的列表中获取下一个未排序的元素

第二步: 将它放在排序列表中的正确位置。

其中一个步骤对于一个算法来说更容易，反之亦然。

插入排序 : 我们获取未排序列表的第一个元素，将其放入排序列表 某个地方中。我们知道在哪里取下一个元素(未排序列表中的第一个位置) ，但是需要做一些工作来找到放置它的位置(某个地方)。第一步很简单。

选择排序 : 我们从未排序的列表中获取元素 某个地方，然后将其放在排序列表的最后一个位置。我们需要找到下一个元素(它很可能不在未排序列表的第一个位置，而是 某个地方) ，然后将它放在已排序列表的末尾。第二步很简单

两种算法的逻辑非常相似。它们在数组的开头都有一个部分排序的子数组。唯一的区别是它们如何搜索要放入排序数组中的下一个元素。

• 插入排序 : 插入物下一个元素在正确位置;

• 选择 sort : 选择最小的元素并与当前项交换;

此外，插入排序是稳定的，而不是 选择排序。

我都是在 python 中实现的，值得注意的是它们有多么相似:

def insertion(data):
data_size = len(data)
current = 1
while current < data_size:
for i in range(current):
if data[current] < data[i]:
temp = data[i]
data[i] = data[current]
data[current] = temp


current += 1


return data

只要稍作更改，就可以使选择排序算法成为可能。

def selection(data):
data_size = len(data)
current = 0
while current < data_size:
for i in range(current, data_size):
if data[i] < data[current]:
temp = data[i]
data[i] = data[current]
data[current] = temp


current += 1


return data

基本上，插入排序的工作原理是一次比较两个元素，选择排序从整个数组中选择最小元素并对其进行排序。

从概念上讲，插入排序通过比较两个元素来对子列表进行排序，直到整个数组被排序，而选择排序则选择最小元素并将其交换到第一位置的第二个最小元素到第二位置，依此类推。

插入排序可以显示为:

    for(i=1;i<n;i++)
for(j=i;j>0;j--)
if(arr[j]<arr[j-1])
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;

选择类别可显示为:

    for(i=0;i<n;i++)
min=i;
for(j=i+1;j<n;j++)
if(arr[j]<arr[min])
min=j;
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;

用外行人的话来说(可能是获得对问题的高层次理解的最简单的方法)

泡沫排序类似于站在一条线上，试图按高度对自己进行排序。你不断地与你身边的人交换，直到你到达正确的地方。从左边开始(或者从右边开始，取决于实现) ，一直切换，直到每个人都被排序。

然而，在选择排序中，你所做的类似于安排一手牌。你看着牌，拿最小的一张，把它放在最左边，依此类推。

简而言之,

选择 sort: 从未排序的数组中选择第一个元素，并将其与其余未排序的元素进行比较。它类似于 Bubble 排序，但不是交换每个较小的元素，而是交换 保持最小的元素索引更新，并在每个循环结束时交换它。

插入排序: 与 Select sort 相反，它从未排序的子数组中选择第一个元素，并将其与已排序的子数组进行比较，然后插入找到的最小的元素，并将所有已排序的元素从其右侧移动到第一个未排序的元素。

选择-选择一个特定的项目(最低)和 将它与 i (no of iteration) th 元素交换。 (即第一、第二、第三... ...) 因此，将排序列表放在一边。

插入-第一次与第二次比较 将第三名与第二名及第一名比较 比较第四和第三，第二和第一... ..。

比较所有排序的链接

选择 SORT < br/> 假设有一个以特定/随机方式书写的数组，让我们假设我们按增加的顺序排列。.所以，一次取一个数字，然后用最小的“不”代替。列表中可供选择。通过这个步骤，我们最终会得到我们想要的结果。< br/> < br/> < a href = “ https://i.stack.imgur.com/mGSJZ.gif”rel = “ noreference rer”> < img src = “ https://i.stack.imgur.com/mGSJZ.gif”alt = “ enter image description here”> < br/> < br/> < a href = “ https://i.stack.imgur.com/mGSJZ.gif”rel = “ noreference rer”> < img src = “ https://

插入 SORT < br/> 保持类似的假设，但唯一的区别是，这次我们一次选择一个数字，并将其插入预先排序的部分，这减少了比较，因此更有效。< br/>

插入排序的内部循环遍历已经排序的元素(与选择排序相反)。这使得它的 当找到正确的位置时，中止内循环。也就是说:

1. 在一般情况下，内部循环只会遍历其一半的元素。
2. 如果数组几乎排序完毕，内部循环将更快中止。
3. 如果数组已经排序，内部循环将立即中止，这使得插入排序的复杂性成为线性。

选择排序必须始终遍历所有内部循环元素。这就是为什么插入排序通常优于选择排序的原因。但是，另一方面，选择排序做的元素交换要少得多，这在某些情况下可能更重要。

一个简单的解释如下:

给定 : 未排序的数组或数字列表。

问题陈述 : 按升序对数字列表/数组进行排序，以理解选择排序和插入排序之间的区别。

插入排序: 您可以看到从上到下的列表，以便于理解。我们认为第一个元素是我们的初始最小值。现在，我们的想法是线性遍历该列表/数组的每个索引，以找出是否有任何其他元素在任何索引中的值小于初始最小值。如果我们找到这样一个值，我们只需交换它们索引处的值，比如说15是索引1处的最小初始值，在索引的线性遍历过程中，我们遇到一个值较小的数字，比如说索引9处的7。现在，索引9处的值7与索引1交换，索引1的值为15。此遍历将继续与当前索引的值进行比较，并与其余索引交换较小的值。这会一直持续到 list/array 的第二个最后一个索引，因为最后一个索引已经排序，没有值可以在 array/list 之外检查。

假设 list/array 的第一个 index 元素已经排序。现在，从第二个索引处的元素，我们将其与之前的索引进行比较，看看该值是否更小。遍历可以可视化为两部分，排序和未排序。一种方法是将未排序的索引与列表/数组中给定索引的已排序索引进行可视化比较检查。 假设索引1的值为19，索引3的值为10。我们考虑从未排序的到排序的遍历，也就是从右到左。那么，假设我们必须在索引3处进行排序。当我们从右向左比较时，我们发现它的值比索引1小。一旦确定，我们只需将索引3的这个数字10放在索引1的值为19的位置。索引1处的原始值19向右移动了一个位置。对于 list/array 中的每个元素，这个遍历一直持续到最后一个元素。