问题标签 [insertion-sort]

我有一个包含 100 个元素的数组，需要使用 OpenMP 进行插入排序。当我并行化我的排序时，它没有给出正确的值。有人能帮我吗

我必须使用 C++ 中的数组来实现一个向量，该数组用于计算输入中唯一单词的数量。它读取输入，然后将单词添加到包含其计数和唯一单词的结构中，然后将其添加到向量中。我已经成功实现了插入。问题是我无法让插入/递增唯一字数起作用（元素未添加到向量中）。这是我的代码：

n = 1,000,000假设您必须对包含元素的数组进行排序。假设每个基本步骤需要一毫秒，插入排序和堆排序大概需要多长时间？

我知道插入排序n^2在最坏的情况下采取步骤，而堆排序在最坏的情况下采取n log n步骤。

所以1,000,000 ^ 2对于插入排序 =1*10^12毫秒

和1,000,000 * log(1,000,000)堆排序？6,000,000毫秒

那是对的吗？

我正在阅读“算法简介”并阅读有关插入排序的内容。
我试图在没有先阅读他们的解决方案的情况下自己实现它。

这是我的解决方案，这是插入排序吗？

好的，我已经阅读了它，并理解为什么它不是插入排序......这要好得多。

我正在阅读《算法导论》，第 3 版这本书。首先要解释的事情之一是插入排序。在第 18 页有一些伪代码：

A = { 5, 2, 4, 6, 1, 3 };

它说使用了伪代码，因此可以轻松地将其翻译成任何类型的语言（C、C++、Java，他们没有提到，但我猜也是 C#）。因为我用 C# 编程，所以我用 LinqPad 翻译了它。

你可能会问，为什么 j 是从 1 开始的，而它明明是 2？在书中，数组的索引从 1 开始。是的，我现在可能应该更新所有的[i - 1]和[i + i]。

无论如何，完成后，我运行代码并注意到它实际上并没有正确排序。输出是{ 5, 1, 2, 3, 4, 6 }。已经很晚了，应该停止，但我努力使代码正确。我做了所有事情，甚至按照书中的伪代码（从 2 开始）。仍然不是正确的输出。

我联系了这本书的一位教授，他给我发了插入排序的代码，用 C 语言：

用 C# 翻译：

int[] a = { 5, 2, 4, 6, 1, 3 };

我得到一个数组越界。好吧，那么也许：

int[] a = { 5, 2, 4, 6, 1, 3 };

输出：{ 5, 1, 2, 3, 4, 6 }

我在想，这不可能是正确的。伪代码对 array.Length 说 2。是 2 < array.Length，还是 2 <= array.Length？这里发生了什么？

我个人认为是因为0 > 0while循环中的谓词。它实际上每次都不足一次。

我的解释（来自我发送给教授的电子邮件，懒得把它全部输入）：

循环仍然结束的{ 5, 1, 2, 3, 4, 6 }原因是i > 0谓词。每次在 while 循环中减去 i ( i--) 的 1。这最终会导致0 > 0which 以 false 结束（只会0 == 0返回 true），但此时循环仍需要再运行一次。它连续下降一分。它应该再执行一次while循环以正确排序。

另一种解释：

当 j 以 2 开头时，key == 4，i == 1 和 a[i] == 2。在这种情况下，while 循环不会运行，因为 2 > 0 但 2 不大于 4。

j == 3, key == 6, i == 2, a[i] == 4

While 循环不会运行，因为 4 不大于 6

j == 4, key == 1, i == 3, a[i] == 6

这次运行while循环：

a[i + 1] = a[i] -> a[4] = a[3] -> { 5, 2, 4, 6, 6, 3 } i-- -> i == 2

再次循环，因为 2 > 0 和 4 > 1

a[i + 1] = a[i] -> a[3] = a[2] -> { 5, 2, 4, 4, 6, 3 } i-- -> i == 1

再次循环，因为 1 > 0 和 2 > 1

a[i + 1] = a[i] -> a[2] = a[1] -> { 5, 2, 2, 4, 6, 3 } i-- -> i == 0

这就是（在我看来）错误的地方。i 现在等于 0，但是 while 循环应该再运行一次以使 5 脱离第 0 个位置。

教授向我保证他是正确的，但我无法得到正确的输出。我的想法哪里错了？

教授发给我的 C 代码中的数组实际上是从索引 1 开始的。我不知道这一点，检查 C 数组时，我发现它们都以 0 开头。是的，然后 C 代码没有t 产生正确的输出。教授向我解释了这一点，现在这些碎片都落到了它的位置。

我正在自学 Python，但我在一个相对简单的概念上遇到了困难。目标是使用插入排序按升序对列表进行排序。这是代码：

我不明白加粗的步骤是如何工作的。例如，如果我有一个 [6,5,4,3,1] 的列表并且我进行了第二次迭代，那么我的列表现在不是 [6,6,4,3,1] 吗？我正在分配 A[i+1]（在第一种情况下为 5）A[i] 的值（在第一种情况下为 6）。我的5怎么了？我最初对代码的尝试是：

这种方法也有效。我不明白为什么第一个也一样。有没有人想一针见血？

快速排序的运行时间可以在实践中利用插入排序在其输入接近排序时的快速运行时间来提高。当对少于 k 个元素的子数组调用 quicksort 时，让它简单地返回而不对子数组进行排序。在对快速排序的顶级调用返回后，对整个数组运行插入排序以完成排序过程。

认为这种排序算法在 O(nk + n log (n/k)) 预期时间内运行。在理论上和实践中应该如何选择 k？

插入排序如何处理分布式系统中数组的多个副本？我问是因为读取数据比写入数据更容易。就更新次数而言，分布式系统中算法的成本是多少？

目前，我被分配编写插入排序算法的递归版本。我做到了。事实上，这里是这样的：

我的问题是双重的。首先，我不确定我提出的递归关系是否正确。我想出了

作为我的递归关系。那正确吗？我在这之间弹跳

其次，我应该用代数来证明

解决了该递归关系。我真的很难做到这一点，因为 A. 我不确定我的复发是否正确，B. 我有时在数学上很糟糕。

对于任何问题的任何帮助将不胜感激。

谢谢。

好吧，我在数学教授的帮助下设法弄清楚了：P 我要把它留在这里，以便其他人知道该怎么做。有人应该将其复制为答案：D

所以这个的递归关系应该是 T(n) = T(n-1) + n 而不是我原来的，这是主要问题。为什么？好吧，这是执行 n-1 的递归回溯所需的时间，因为如果您要转到 n，您将只有一个元素，并且已经排序。加上进行一次插入或一次实际排序所需的时间。

那是 n 的原因是因为当你到那里时，你正在检查一个数字与它之前的每个数字，这恰好是 n 次。

现在你如何证明函数 f(n) 解决了 T(n)？

我们知道 f(n) 解决了 T(n)。所以这意味着你可以这样做：

哇！

我正在阅读《算法简介》一书，伪代码是

虽然 wiki 上的伪代码是

为什么一个从 2 开始并循环到长度，而另一个从 1 开始并循环到 A -1 的长度？