我试图了解插入排序和选择排序之间的区别。
它们似乎都有两个组成部分：未排序列表和排序列表。他们似乎都从未排序的列表中取出一个元素并将其放入已排序列表的适当位置。我看过一些网站/书籍说选择排序通过一次交换一个来做到这一点，而插入排序只是找到正确的位置并插入它。但是，我看到其他文章说了什么，说插入排序也可以交换。因此，我很困惑。有没有规范的来源？
问问题
236587 次
22 回答
209
选择排序：
给定一个列表，取出当前元素并将其与当前元素右侧的最小元素交换。
插入排序：
给定一个列表，取出当前元素并将其插入列表的适当位置，每次插入时调整列表。这类似于在纸牌游戏中排列纸牌。
选择排序的时间复杂度总是n(n - 1)/2，而插入排序的时间复杂度更好，因为它的最坏情况复杂度是n(n - 1)/2。一般来说，它会进行较少或相等的比较n(n - 1)/2。
来源：http ://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html
于 2013-04-03T22:07:26.610 回答
79
插入排序和选择排序都有一个外循环（在每个索引上）和一个内循环（在索引子集上）。内部循环的每一遍都将已排序的区域扩展一个元素，代价是未排序的区域，直到它用完未排序的元素。
不同之处在于内部循环的作用：
在选择排序中，内部循环位于未排序的元素之上。每遍选择一个元素，并将其移动到其最终位置（在排序区域的当前末端）。
在插入排序中，内循环的每一次遍历都会遍历已排序的元素。已排序的元素会被替换，直到循环找到插入下一个未排序元素的正确位置。
因此，在选择排序中，排序的元素按输出顺序找到，一旦找到就留在原地。相反，在插入排序中，未排序的元素保持原位，直到按输入顺序被消耗，而排序区域的元素不断移动。
就交换而言：选择排序每次通过内部循环进行一次交换。插入排序通常将要插入的元素保存在内循环temp 之前，为内循环留出空间将已排序的元素向上移动一个，然后复制temp到插入点。
于 2013-04-03T22:42:50.187 回答
30
选择排序
假设有一组以特定/随机方式写入的数字，假设我们要按递增顺序排列..所以，一次取一个数字并用最小的数字替换它们。在列表中可用。通过执行此步骤，我们最终会得到我们想要的结果。
插入排序
记住类似的假设，但唯一的区别是这次我们一次选择一个数字并将其插入预排序的部分，这减少了比较，因此效率更高。
于 2018-10-02T15:06:12.583 回答
22
混淆可能是因为您将排序链表的描述与排序数组的描述进行比较。但我不能确定，因为你没有引用你的消息来源。
理解排序算法最简单的方法通常是获取算法的详细描述（不是模糊的东西，比如“这种排序使用交换。某处。我没说在哪里”），拿一些扑克牌（5-10 应该足够了对于简单的排序算法），并手动运行算法。
选择排序：扫描未排序的数据，寻找最小的剩余元素，然后将其交换到紧跟排序数据的位置。重复直到完成。如果对列表进行排序，则不需要将最小元素交换到位，而是可以将列表节点从其旧位置移除并将其插入新位置。
插入排序：取紧跟在排序后的数据的元素，扫描排序后的数据，找到放置的地方，然后放在那里。重复直到完成。
插入排序可以在其“扫描”阶段使用交换，但不是必须的，而且这不是最有效的方式，除非您对具有以下数据类型的数组进行排序： (a) 不能移动，只能复制或交换；(b) 复制比交换更昂贵。如果插入排序确实使用交换，它的工作方式是同时搜索该位置并将新元素放在那里，通过重复将新元素与它之前的元素交换，只要它之前的元素大于它。一旦你到达一个不大的元素，你就找到了正确的位置，然后你继续下一个新元素。
于 2013-04-03T22:55:37.090 回答
14
两种算法的逻辑非常相似。它们在数组的开头都有一个部分排序的子数组。唯一的区别是它们如何搜索要放入排序数组的下一个元素。
插入排序：在正确位置插入下一个元素；
选择排序：选择最小的元素并与当前项交换；
此外，与选择排序相反，插入排序是稳定的。
我在 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
于 2015-12-27T17:55:12.360 回答
6
简而言之，
选择排序：从未排序的数组中选择第一个元素并将其与剩余的未排序元素进行比较。它类似于冒泡排序，但不是交换每个较小的元素，而是更新最小元素索引并在每个循环结束时交换它。
插入排序：与选择排序相反，它从未排序的子数组中选择第一个元素并将其与已排序的子数组进行比较，然后插入找到的最小元素并将所有已排序的元素从其右侧移动到第一个未排序的元素。
于 2017-07-21T16:36:21.100 回答
5
两种算法通常都是这样工作的
第 1 步：然后从未排序列表中取出下一个未排序元素
第2步：将其放在排序列表中的正确位置。
对于一种算法，其中一个步骤更容易，反之亦然。
插入排序：我们取出未排序列表的第一个元素，将其放入已排序列表的某处。我们知道将下一个元素放在哪里（未排序列表中的第一个位置），但是需要一些工作才能找到将它放在哪里（某处）。第 1 步很简单。
选择排序：我们从未排序列表中的某处获取元素，然后将其放在已排序列表的最后位置。我们需要找到下一个元素（它很可能不在未排序列表的第一个位置，而是在某处），然后将其放在已排序列表的末尾。第 2 步很简单
于 2015-12-25T18:52:30.523 回答
4
简而言之，我认为选择排序首先搜索数组中的最小值，然后进行交换，而插入排序取一个值并将其与留给它的每个值（在它后面）进行比较。如果值较小，则交换。然后，再次比较相同的值，如果它小于它后面的值，则再次交换。我希望这是有道理的！
于 2014-09-27T21:57:26.620 回答
4
这两种排序算法的选择归结为使用的数据结构。
当您使用数组时，请使用选择排序（尽管为什么，何时可以使用 qsort？）。当您使用链表时，请使用插入排序。
这是因为：
- 链表遍历比数组更昂贵。
- 链表插入比数组便宜得多。
插入排序将新值注入到已排序段的中间。因此，需要“推回”数据。但是，当您使用链表时，通过扭曲 2 个指针，您有效地将整个列表推回。在数组中，您必须执行 n - i 交换以将值推回，这可能非常昂贵。
选择排序总是追加到末尾，所以在使用数组时不存在这个问题。因此，数据不需要被“推回”。
于 2020-08-05T18:26:23.337 回答
3
我再试一次：考虑一下在几乎排序数组的幸运情况下会发生什么。
在排序时，数组可以被认为有两部分：左侧 - 已排序，右侧 - 未排序。
插入排序 - 选择第一个未排序的元素并尝试在已排序的部分中为它找到一个位置。由于您从右到左搜索，很可能会发生您要比较的第一个排序元素（最大的元素，左侧最右边的元素）小于选择的元素，因此您可以立即继续下一个未排序的元素。
选择排序 - 选择第一个未排序的元素并尝试找到整个未排序部分的最小元素，如果需要，交换这两个元素。问题是，由于正确的部分是未排序的，因此您每次都必须考虑每个元素，因为您无法确定是否存在比选择的元素更小的元素。
顺便说一句，这正是heapsort对选择排序的改进——由于heap，它能够更快地找到最小的元素。
于 2015-02-12T02:08:52.097 回答
3
选择排序：当您开始构建已排序的子列表时，该算法确保已排序的子列表始终是完全排序的，不仅在它自己的元素方面，而且在完整的数组方面，即已排序和未排序的子列表。因此，从未排序的子列表中找到的新的最小元素将被附加到已排序的子列表的末尾。
插入排序：算法再次将数组分成两部分，但这里的元素是从第二部分挑选出来的，并在正确的位置插入到第一部分。这永远不能保证第一部分是根据完整数组排序的，尽管在最后一遍中，每个元素当然都处于正确的排序位置。
于 2015-05-27T13:47:37.627 回答
2
基本上插入排序通过一次比较两个元素来工作，选择排序从整个数组中选择最小元素并对其进行排序。
从概念上讲，插入排序通过比较两个元素继续对子列表进行排序，直到整个数组被排序，而选择排序选择最小元素并将其交换到第一个位置第二个最小元素到第二个位置，依此类推。
插入排序可以显示为：
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;
于 2016-12-02T14:38:55.853 回答
2
虽然选择排序和插入排序的时间复杂度是一样的，都是n(n - 1)/2。平均性能插入排序更好。在我的 i5 cpu 上使用随机 30000 个整数进行测试，选择排序平均需要 1.5 秒，而插入排序平均需要 0.6 秒。
于 2020-08-05T17:36:15.963 回答
2
插入排序的内部循环遍历已经排序的元素（与选择排序相反）。这允许它在找到正确位置时中止内部循环。意思就是：
- 在一般情况下，内部循环只会遍历其一半的元素。
- 如果数组几乎已排序，内部循环将更快中止。
- 如果数组已经排序，内部循环将立即中止，在这种情况下，插入排序的复杂性是线性的。
选择排序必须始终遍历所有内部循环元素。这就是为什么插入排序比选择排序更受欢迎的原因。但是，另一方面，选择排序进行的元素交换要少得多，这在某些情况下可能更重要。
于 2018-11-27T17:04:24.860 回答
1
插入排序和选择排序都在前面有一个排序的列表，在最后有一个未排序的列表，算法的作用也相似：
- 从未排序的列表中取出一个元素
- 将其放入排序列表
区别在于：
- 插入排序取未排序列表的第一个元素，然后在排序列表中进行比较和交换以确保元素进入正确的位置，工作主要在步骤＃2中进行插入
auto insertion_sort(vector<int>& vs) { for(int i=1; i < vs.size(); ++i) { for(int j=i; j > 0; --j) { if(vs[j] < vs[j-1]) swap(vs[j], vs[j-1]); } } return vs; }
- 选择排序比较并标记未排序列表的最小元素，然后将其与未排序列表的第一个元素交换，实际上将此元素作为已排序列表的一部分 - 工作主要在步骤＃1中进行选择
auto selection_sort(vector<int>& vs) { for(int i = 0; i < vs.size(); ++i) { int iMin = i; for(int j=i; j < vs.size(); ++j) { if(vs[j] < vs[iMin]) iMin = j; } swap(vs[i], vs[iMin]); } return vs; }
于 2020-11-28T13:55:26.267 回答
0
我想从上面用户@thyagostall 的一个几乎很好的答案中添加一点改进。在 Python 中，我们可以进行一行交换。下面的 selection_sort 也已通过将当前元素与右侧的最小元素交换来修复。
在插入排序中，我们将从第二个元素开始运行外循环，并在当前元素的左侧执行内循环，将较小的元素向左移动。
def insertion_sort(arr):
i = 1
while i < len(arr):
for j in range(i):
if arr[i] < arr[j]:
arr[i], arr[j] = arr[j], arr[i]
i += 1
在选择排序中，我们也运行外循环，但不是从第二个元素开始，而是从第一个元素开始。然后内部循环将当前 + i 元素循环到数组的末尾以找到最小元素，我们将与当前索引交换。
def selection_sort(arr):
i = 0
while i < len(arr):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
i += 1
于 2021-02-07T08:50:32.453 回答
0
插入排序会做更多的交换选择。这是一个例子：
于 2019-09-22T16:51:20.890 回答
0
插入排序不交换东西。即使它使用了一个临时变量，使用 temp var 的目的是当我们发现索引处的值与其前一个索引的值相比要小时，我们将较大的值移动到较小值的位置会覆盖东西的索引。然后我们使用 temp var 在前一个索引处进行替换。示例：10、20、30、50、40。迭代 1：10、20、30、50、50。[temp = 40] 迭代 2：10,20、30、40（温度值）、50。所以，我们只需从某个变量在所需位置插入一个值。
但是当我们考虑选择排序时，我们首先找到具有较低值的索引并将该值与第一个索引中的值交换，并不断重复交换直到所有索引都被排序。这与传统的两个数字交换完全相同。示例：30, 20 ,10, 40, 50。迭代 1：10,20,30,40,50。这里 temp var 专门用于交换。
于 2019-07-08T11:20:22.793 回答
0
一个简单的解释可能如下：
Given：未排序的数组或数字列表。
问题陈述：按升序对数字列表/数组进行排序，以了解选择排序和插入排序之间的区别。
插入排序：您可以从上到下查看列表以便于理解。我们将第一个元素视为我们的初始最小值。现在，我们的想法是我们线性遍历该列表/数组的每个索引，以找出任何索引处是否有任何其他元素的值小于初始最小值。如果我们找到这样的值，我们只需交换它们索引处的值，即假设 15 是索引 1 处的最小初始值，并且在索引的线性遍历期间，我们遇到一个值较小的数字，例如索引 9 处的 7 . 现在，索引 9 处的这个值 7 与索引 1 交换，索引 1 的值是 15。此遍历将继续与当前索引的值与剩余索引进行比较以换取较小的值。这一直持续到列表/数组的倒数第二个索引，
选择排序：假设列表/数组的第一个索引元素已排序。现在从第二个索引处的元素，我们将它与之前的索引进行比较，看看该值是否更小。遍历可以可视化为两部分，已排序和未排序。一种是可视化列表/数组中给定索引从未排序到排序的比较检查。假设您在索引 1 处具有值 19，在索引 3 处具有值 10。我们考虑从未排序到已排序的遍历，即从右到左。所以，假设我们必须在索引 3 处排序。当我们从右到左比较时，我们看到它的值小于索引 1。一旦确定，我们只需将索引 3 的数字 10 放在索引 1 的值为 19 的位置。索引 1 处的原始值 19 向右移动了一个位置。
我没有添加任何代码，因为问题似乎是关于理解遍历方法的概念。
于 2019-06-19T14:37:22.790 回答
0
它们的共同点是它们都使用分区来区分数组的已排序部分和未排序部分。
不同之处在于，通过选择排序，您可以保证在将元素添加到已排序分区时，数组的已排序部分不会改变。
原因是，因为选择搜索未排序集的最小值并将其添加到排序集的最后一个元素之后，从而将排序集增加1。
另一方面，插入只关心遇到的下一个元素，即数组未排序部分的第一个元素。它将获取此元素并简单地将其放入已排序集中的适当位置。
对于仅部分排序的数组，插入排序通常总是更好的候选者，因为您正在浪费操作来找到最小值。
结论：
选择排序通过在未排序部分中找到最小元素来递增地将一个元素添加到末尾。
插入排序将在未排序部分中找到的第一个元素传播到已排序部分的任何位置。
于 2020-03-26T22:01:02.407 回答
-1
用外行的话来说，（可能是获得对问题的高级理解的最简单方法）
冒泡排序类似于站成一排并试图按高度对自己进行排序。您不断与您旁边的人切换，直到您在正确的位置。这从左侧（或右侧，具体取决于实现）一直进行，并且您不断切换，直到每个人都被排序。
然而，在选择排序中，您正在做的事情类似于安排一手牌。您查看卡片，取出最小的一张，将其一直放在左侧，依此类推。
于 2017-02-01T19:00:48.790 回答
-1
selection - 选择特定项目（最低）并将其与第 i（迭代次数）元素交换。（即，第一，第二，第三......）因此，在一侧制作排序列表。
插入 - 比较第一个和第二个比较第三个和第二个和第一个比较第四个和第三个，第二个和第一个......
于 2018-04-24T15:33:31.937 回答