问题标签 [insertion-sort]

我必须制作一个电话簿程序。程序应该从文件中读取名称和数字。我已经成功创建了一个包含这些数据的链表。现在我想按字母顺序对它们进行排序。我该怎么做？

这是我在 Cormen, Leiserson, Rivest 书中描述的插入排序的实现。唯一的区别是我使用的是内部 for 循环而不是 while 循环。我觉得它有点笨拙。我怎样才能简化这个？

numpy 中的某处是否有插入排序？我的数组需要一个 argsort，但内置的快速、合并和堆不适合几乎排序的数组。

我使用以下算法进行插入排序：

但是，我需要维护一个列表来将 A 的原始值的索引映射到 A 的排序值，这意味着如果在对 list = [4, 3,2,1] 我将有一个索引列表 [3,1,0,2]。

任何指针？我有点卡住了。

已编辑：抱歉，按降序排序..

假设我们有一个索引为 0 的序列 S，取 S[0] 并将其插入 S 中下一个值高于 S[0] 且前一个值低于 S[0] 的位置。形式上，S[i] 应该放在 S[i-1] < S[i] < S[i+1] 这样的地方。继续按列表上的顺序对每个项目执行相同的操作。在将元素放在正确的位置之前从列表中删除元素。在对列表进行一次迭代之后，列表应该被排序。我最近有一次考试，我忘记了插入排序（别笑），我就是这样做的。然而，我的教授把它标记错了。据我所知，该算法确实会产生一个排序列表。

在列表中像这样工作：

由于每次将一个元素插入列表时，列表中的 (n-1) 个数字可能会被移动，我们必须这样做 n 次，算法应该在 O(n^2) 时间内运行。

我有一个 Python 实现，但不知何故我放错了位置。稍后我会尝试再次编写它，但实现起来有点棘手。有任何想法吗？

Python 实现在这里：http ://dpaste.com/hold/522232/ 。它是由 reddit.com 的 busy_beaver 写的，在这里讨论时http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/

我们正在做一个涉及存储和比较各个城市的项目。在将新城市添加到数据库后，我们陷入了困境，它位于列表的底部 - 我们希望它进入数据库，按字母顺序排序。由于一次只能添加一个值，因此所有其他条目都已按字母顺序排列。

以下是与此相关的代码。

问题区域是添加 // 出位时的 // 插入排序。

错误代码是：

全部对应线

如果你能指出我们正确的方向，那就太好了。谢谢

所以我正在根据这个高级代码编写一个插入排序（在汇编中）：

在一个名为 myArray 的数组中恰好有 20 个随机数。我不能使用随我们的书一起提供的图书馆中的决策衍生工具。所以基本上 movs、cmps、loops 和 jumps 这就是我得到的。我早些时候让它对 20 个随机数中的第一个进行排序，但我已经把自己弄糊涂了，不知道我在做什么了。当它到达插入排序方法时它会崩溃。请帮忙。

我到处寻找以及我找到的任何算法（如果有的话）用于在 C++ 中的向量上进行插入排序，它不会起作用，所以我假设它与我的代码有关。谁能帮我找到一种方法，可以将向量作为参数传递给方法，然后对其进行插入排序？目前它等待几秒钟并显示所有未排序的值:(

插入排序代码

代码的重要部分

如果您认为该代码没有任何问题并且您希望我向您展示更多内容，请告诉我，不过应该只是这一点，我认为其他内容无关紧要

谢谢

目前，我正在准备计算机科学课程的期末考试。将要问的问题之一很可能是关于如何组合运行时间的问题，所以我将举一个例子。

我想知道，如果我创建了一个使用插入排序预处理输入的程序，然后使用二进制搜索搜索值“X”，我将如何结合运行时间来找到最佳、最差和平均情况时间复杂度整体方案？

例如...

插入排序
最坏情况 O(n^2)
最佳情况 O(n)
平均情况 O(n^2)

二进制搜索最坏情况 O(logn)
最佳情况 O(1)
平均情况 O(logn)

最坏的情况是 O(n^2 + logn)，还是 O(n^2)，或者两者都不是？
最好的情况是 O(n) 吗？
平均情况是 O(nlogn)、O(n+logn)、O(logn)、O(n^2+logn)，还是都不是？

我倾向于过度思考解决方案，所以如果我能得到任何关于结合运行时间的指导，我将不胜感激。

非常感谢。

目前，我不担心效率，我只是在学习。我想知道是否有人可以帮助我学习一个简单的单链表插入排序。这是我的作业，所以我想了解它。这是代码：

到目前为止，我已将它读入 istream，因此我需要在读入时对其进行排序。节点是一个结构 btw。有人可以帮我吗？