插入排序与选择排序
eb8*_*b80 93 sorting algorithm insertion-sort selection-sort
我试图理解插入排序和选择排序之间的差异.
它们似乎都有两个组件:未排序列表和排序列表.它们似乎都从未排序的列表中取出一个元素并将其放入适当位置的排序列表中.我已经看到一些网站/书籍说选择排序是通过一次交换一个而插入排序只是找到正确的位置并插入它.但是,我看到其他文章说了些什么,说插入排序也交换了.因此,我很困惑.有没有规范来源？
Nik*_*tov 167
选择排序:
给定一个列表,获取当前元素并将其与当前元素右侧的最小元素进行交换.
插入排序:
给定一个列表,获取当前元素并将其插入列表的适当位置,每次插入时调整列表.它类似于在纸牌游戏中安排牌.
时间选择排序的复杂性始终是n(n - 1)/2,而插入排序具有更好的时间复杂性,因为它的最坏情况复杂性n(n - 1)/2.通常,它将采用较小或相等的比较n(n - 1)/2.
资料来源:http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html
- 但掉期数量呢？选择总是进行n(n-1)/ 2次比较,但在最坏的情况下,它只会进行n-1次交换.在最坏的情况下,插入将进行n(n-1)/ 2次比较以及n(n-1)/ 2次交换. (21认同)
- @ eb80我不确定你正在读什么材料,但我不知道一个例子怎么比这更具体呢？ (6认同)
- 主要区别在于选择步骤.选择排序选择最小的一个,并将其与第一个交换.插入排序将当前的一个插入到适当的位置 (4认同)
- @Nikolay-这只是从我已经阅读的http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html复制而来。我读过有冲突的文章时，还有其他协奏曲吗？ (2认同)
- @Adorn 这些都不是分而治之的算法。 (2认同)
- @Adorn如果您考虑重复选择一个要“划分”的元素并发现它的正确位置（以及插入排序的相反方式）要“征服”，那么也许您可以将这些算法称为分而治之。然而，在大多数计算机科学文献中，根据经验，您会发现分而治之的算法根据定义本质上是递归的。请注意，我本质上是说迭代算法可以通过尾递归实现，递归算法可以通过堆栈迭代实现。 (2认同)
- @Adorn适得其反的效果 (2认同)
- @AskyMcAskface@Adorn 我认为你们俩都错了。插入和选择都不是分而治之；但同时，分治法不需要递归。由于更容易实现，因此通常将其编写为递归，但可以将其实现为迭代。定义分而治之的主要内容是被征服的主体必须被划分——即列表必须被划分为子列表，然后被处理并合并回来。这两种算法都不会发生这种情况。 (2认同)
com*_*orm 54
插入排序和选择排序都有一个外部循环(在每个索引上)和一个内部循环(在索引子集上).内循环的每次传递都将排序区域扩展一个元素,代价是未排序区域,直到它用完了未排序的元素.
不同之处在于内循环的作用:
在选择排序中,内部循环位于未排序的元素上.每个传递选择一个元素,并将其移动到其最终位置(在已排序区域的当前末尾).
在插入排序中,内循环的每次传递都在已排序的元素上进行迭代.排序的元素被移位,直到循环找到插入下一个未排序元素的正确位置.
因此,在选择排序中,排序的元素在输出顺序中找到,并在找到它们后保持不变.相反,在插入排序中,未排序的元素保持不变,直到按输入顺序消耗,而排序区域的元素不断移动.
就交换而言:选择排序在内循环的每次传递中进行一次交换.插入排序通常会在内循环temp 之前保存要插入的元素,为内循环留出空间,将排序后的元素向上移动,然后复制temp到插入点.
Ste*_*sop 20
这可能是因为您将链接列表的排序描述与排序数组的描述进行比较.但我不能确定,因为你没有引用你的消息来源.
理解排序算法的最简单方法通常是获得算法的详细描述(不是模糊的东西,比如"这种类型使用交换.某处.我不是说在哪里"),得到一些扑克牌(5-10应该足够了)对于简单排序算法),并手动运行算法.
选择排序:扫描未排序的数据,查找剩余的最小元素,然后将其交换到排序数据后面的位置.重复直到完成.如果对列表进行排序,则不需要将最小元素交换到位,您可以将列表节点从其旧位置移除并将其插入到新位置.
插入排序:在排序数据之后立即获取元素,扫描排序数据以找到放置它的位置,并将其放在那里.重复直到完成.
插入排序可以在"扫描"阶段使用交换,但不是必须的,并且它不是最有效的方式,除非您正在排序数据类型的数组:(a)不能移动,只能复制或交换; (b)复制比交换更昂贵.如果插入排序确实使用swap,它的工作方式是你同时搜索该位置并将新元素放在那里,只要在它之前的元素重复地交换新元素,只要它之前的元素大于它.一旦你到达一个不大的元素,你就找到了正确的位置,然后你继续前进到下一个新元素.
小智 16
SELECTION SORT
假设存在以特定/随机方式编写的数字数组,并且假设我们要按递增顺序排列.所以,一次取一个数字并用最小的数字替换它们.可在列表中找到.通过这一步,我们最终会得到我们想要的结果.
INSERTION 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
简而言之，
选择排序：从未排序的数组中选择第一个元素并将其与剩余的未排序元素进行比较。它类似于冒泡排序，但不是交换每个较小的元素，而是保持更新最小元素索引并在每个循环结束时交换它。
插入排序：它与选择排序相反，它从未排序的子数组中选取第一个元素并将其与已排序的子数组进行比较，然后插入找到的最小元素，并将所有已排序元素从其右侧移至第一个未排序元素。
这两种排序算法的选择取决于所使用的数据结构。
当您使用数组时，请使用选择排序（尽管为什么，当您可以使用 qsort 时？）。使用链表时，请使用插入排序。
这是因为：
- 链表遍历比数组更昂贵。
- 链表插入比数组便宜得多。
插入排序将新值插入已排序段的中间。因此，数据需要“推回”。但是，当您使用链表时，通过扭转 2 个指针，您实际上已将整个列表推回原处。在数组中，您必须执行 n - i 次交换才能将值推回原处，这可能非常昂贵。
选择排序总是追加到末尾，因此使用数组时不会出现此问题。因此，数据不需要“推回”。
小智 5
两种算法通常都是这样工作的
步骤1：从未排序的列表中取出下一个未排序的元素然后
第2步：将其放在排序列表中的正确位置。
对于一种算法来说，其中一个步骤更容易，反之亦然。
插入排序：我们取未排序列表的第一个元素，将其放入已排序列表的某处。我们知道在哪里取下一个元素（未排序列表中的第一个位置），但是需要一些工作才能找到放置它的位置（某处）。第 1 步很简单。
选择排序：我们从未排序列表中的某处取出元素，然后将其放在排序列表的最后位置。我们需要找到下一个元素（它很可能不在未排序列表的第一个位置，而是在某处）然后将它放在排序列表的末尾。第 2 步很简单