提问人：Sheep_Walker 提问时间：4/5/2023 更新时间：4/7/2023 访问量：183
插入排序算法需要多长时间才能对 6 个元素的列表进行排序？
how long will an insertion sort algorithm take to sort a list of 6 elements?
问：
“在最坏的情况下，假设每个奇数比较需要 2 μs，每个偶数比较需要 1 μs，那么插入排序算法需要多长时间才能对 6 个元素的列表进行排序？”
所以我有一堂课，教我们如何用 Java 编码。我们正在学习诸如冒泡、合并、插入或快速排序等排序算法及其时间复杂性。在一次测验中，我得到了这个问题。这个问题的答案是 30 μs。为什么会这样呢？（顺便说一句，问题就是这样。未提供程序或说明）。
答：
1赞
Daniel Figueroa
4/5/2023
#1
我已经很多年没有做过这样的 CS 了，所以我可能完全不对劲，但我相信人们会评论这个答案的有效性，但我认为这就是你的教授的意思。 如果我是对的，这似乎很奇怪，因为其中一个比较是项目本身。
第一次迭代：将 6 与 6 进行比较，因为它是列表中的第一项，因此不执行任何操作。
第二次迭代：将 5 与 5 进行比较，但它不是第一个元素，将其与左侧的下一个元素进行比较。由于 5 < 6 将 5 放在 6
之前 第三次迭代：将 4 与 4 进行比较，但它不是第一个元素，将其与左侧的下一个元素进行比较。由于 4 < 6 移动到下一项并比较 4 < 5 是正确的，在 5 之前放置 4。
等等......
1. 654321 | 1 ({6,6} = 1)
2. 564321 | 3 ({5,5 = 1}, {5,6 = 2})
3. 456321 | 4 ({4,4 = 1}, {4,6 = 1}, {4,5 = 2})
4. 345621 | 6 ({3,3 = 1}, {3,6 = 2}, {3,5 = 1}, {3,4 = 2})
5. 234561 | 7 ({2,2 = 1}, {2,6 = 1}, {2,5 = 2}, {2,4 = 1}, {2,3 = 2})
6. 123456 | 9 ({1,1 = 1}, {1,6 = 2}, {1,5 = 1}, {1,4 = 2}, {1,3 = 1}, {1,2 = 2})
1+3+4+6+7+9 = 30
评论
0赞
Sheep_Walker
4/5/2023
哦，非常感谢！你怎么知道什么是偶数或奇数？我们是通过 i 的索引还是掉期数来获得它？
1赞
Daniel Figueroa
4/5/2023
我将其解释为 6 和 5 之间的比较算不均匀，而 6 和 4 之间的比较算作偶数。
0赞
Sheep_Walker
4/5/2023
哦，我明白了，它们之间的总和将决定比较是否均匀。
0赞
Kelly Bundy
4/6/2023
谁编写插入排序，以便将每个元素与自身进行比较？那太愚蠢了。
0赞
Daniel Figueroa
4/7/2023
@KellyBundy同意了，我实际上希望我对这位教授正在寻找的东西是错误的。而且我错过了一些明显的东西。
评论