比较来自世界各地的卖家的域名和 IT 服务价格

插入比排序泡沫更好的排序?

我为考试做了我的审计。

我想知道对插入物的排序是什么条件,比排序泡沫更好,鉴于相同的平均水平复杂性 O/N^2/.

我真的发现了几篇相关文章,但我无法理解它们。

谁能以简单的方式解释它吗?
已邀请:

奔跑吧少年

赞同来自:

优势 bubblesort 在于已分拣列表的检测率:

BubbleSort 最佳事件开发方案:

O/n

/

但是,即使在这种情况下,插入物的排序也变得更好 / 同样的表现。

Bubblesort, 或多或少,善于理解和 / 或学习机制 sortalgorithm, 但今天它没有在编程中找到适当的用途,因为它的复杂性

O /n2

/

这意味着它的有效性在超过少数项目的列表中急剧减少。

快网

赞同来自:

以下事件发生在我身上:

泡沫排序始终接受阵列的另一个段落,以确定它是否排序。 另一方面,一旦插入最后一个元素,算法就不需要插入排序,确保将阵列进行排序。

泡沫分类确实如此。
n

每篇文章的比较。 插入分类少于
n

比较:一旦算法查找需要插入当前元素的位置,它就停止比较并采用下一个元素。

最后,从文章中引用
http://en.wikipedia.org/wiki/Bubble_sort
:


泡沫分类也与现代设备相互作用 CPU. 它
需要至少两倍的记录,而不是分类两次
更多的缓存通过和渐近的分支机构预测。
字符串排序实验 Astrachan 在 Java 显示排序泡泡
大约是 5 时间比分拣插入速度慢 40% 慢于
排序选择

在那里,您可以找到原始研究工作的链接。

窦买办

赞同来自:

我认为你正在寻找的答案是
http://en.wikipedia.org/wiki/S ... _sort
:

泡沫分拣也可以在列表中有效地使用,即已有
分类,除了非常少量的项目。 例如,如果
只有一个元素不是按顺序排列的,将采取排序泡沫 2n 时间。
如果两个元素没有按顺序,泡沫分拣将不再需要
3n 时间...



排序插入 - 这是一种简单的排序算法相对
对小小的清单有效,主要是排序的清单,通常使用
作为更复杂算法的一部分

龙天

赞同来自:

您能否提供与您不明白的相关文章的链接? 我不确定他们可以影响哪些方面。 此外,有一种理论差异,可以是气泡分选更适合作为阵列呈现的集合 /而不是以相关清单形式呈现的那些/, 插入排序时适用于相关列表。

推理将是泡沫分类总是同时改变两个元素,这是阵列和关联列表的差异 /更有效地阵列/, 当将在此列表中排序插入到附件中,这对于相关列表进行微不足道,但包括右侧数组中的所有后续元素的移动。

尽管如此,请用不信任地带走它。 首先,在实践中的排序阵列几乎总是发生比排序相关列表更快。 只是由于列表扫描一次已经存在巨大差异。 也移动 n 右侧的元素右上发生比执行快得多 n /甚至 n/2/ Swrap。 这就是为什么其他答案正确声明插入通常很好,为什么我真的想知道你读过的文章,因为我不能提出一种简单的方式来说,在一个情况下,它更好,而且它更好案件。

知食

赞同来自:

在最坏的情况下,两者都倾向于与之合作 O /n^2/

最多,当阵列已经对时,可以执行泡沫排序时 O /n/.

要回复问题请先登录注册