logo标签列表

什么是最低效的排序算法？

javaalgorithmsorting
3

对于一个整数数组，最低效的排序方式是什么？该函数应在每一步中取得进展（例如，没有无限循环）。该算法的运行时间是多少？

1
你认为什么是“进步”？ - Jon Skeet
2
听起来像是作业... - RonK
7
在每次迭代中随机打乱数组顺序，检查其是否已排序，如未排序则重复此过程直至排序完成。 - James Allardice
2
排序算法比较 - Joe Stefanelli
@JamesAllardice，又称Bogosort。 - Joe Stefanelli
显示剩余12条评论
10个回答
9

任何事物都不可能存在最低效的算法。只要你接受从任意算法开始，就可以构建出另一个等效但更低效的算法，那么这一点很容易通过反证法来证明。

好的思考。这种问题需要更多的定义思考。 - MarianP
每一步的进度在哪里？ - user unknown
@userunknown 你是什么意思？ - David Heffernan
从问题“函数应该在每一步中取得进展”中，如果你想升序排列1、4、3、2 - 我不明白你如何可以有超过3或4个改进步骤，直到它被排序。 - user unknown
如果你能合理地定义进展或改进步骤，那么你可能有一点道理。你能做出这样的定义吗？这个问题显然没有这样的定义。 - David Heffernan
6
更好的是，如果随机数生成器不喜欢你，或者你的伪随机数生成器没有生成排序数组所需的数字序列，它的最坏情况运行时间为O(infinity)。 - user395760
@delnan 对于任何相当大的数字列表，后者很可能发生。 - Nick Johnson
每一步的进展在哪里？ - user unknown
3

愚蠢排序无疑是最糟糕的算法。虽然不是无限循环，但其最坏情况的时间复杂度为O(inf)，平均时间复杂度为O(n × n!)。

2

我能想到的最低效的算法是排列排序，它有一个有限的运行时间上界。其思想是生成输入的每个排列（组合）并检查它是否已排序。

上界为O(n!)，当数组已排序时，下界为O(n)。

2

你可以通过生成所有唯一的排列，然后检查数组是否排序来在 O(n!*n) 的时间复杂度内完成。

每一步的进展在哪里？ - user unknown
1
  1. 使用对角线法遍历所有整数的有限序列。
  2. 对于每个序列，测试它是否已排序。
  3. 如果是，则测试其元素是否与数组中的元素匹配。

这将具有上界（第一个猜测：O(n^(n*m))?）。

0

"Worstsort"的复杂度为\Omega((n!^{(f(n))})^2)，其中n!^{(m)} = (...((n!)!)!...)! =表示n的阶乘迭代m次。Miguel A. Lerma的论文可以在这里找到。

0

这是一个奇怪的问题，通常我们会选择最快的方式。

找到最大值并将其移到一个列表中。重复上一步，直到原始列表只剩下一个元素。您可以保证 O(N^2) 的时间复杂度。

0

Bogosort是一种最糟糕的排序算法，使用洗牌。但从另一个角度来看，它在一步中对数组进行排序的概率很低 :)

每步操作没有保证的改进。 - user unknown
0
波戈波戈排序。它类似于乱序排序，但是会创建辅助数组，第一个数组与其他数组相比少1个元素。它们也可以被移除。平均复杂度为O(N的超阶乘*n)。最好情况是O(N^2)。就像乱序排序一样，最坏情况下的时间复杂度是O(无穷大)。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接