最低效的排序程序是什么？
对于整数数组，排序数组效率最低的方法是什么。该函数应该在每个步骤中取得进展（例如，没有无限循环）。该算法的运行时间是多少？
For an array of integers, what is the least efficient way of sorting the array. The function should make progress in each step (eg no infinity loop). What is the runtime of that algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
我认为运行时上限有限的效率最低的算法是排列排序。这个想法是生成输入的每个排列（组合）并检查它是否已排序。
当数组已排序时，上限为 O(n!)，下限为 O(n)。
The least efficiant algorithm I can think with a finite upper bound on runtime is permutation sort. The idea is to generate every permutation (combination) of the inputs and check if it's sorted.
The upper bound is O(n!), the lower bound is O(n) when the array is already sorted.
这将有一个上限（第一个猜测：O(n^(n*m)？）。
This will have an upper bound (first guess: O(n^(n*m)?).
奇怪的问题，通常我们会追求最快。
找到最高的并将其移至列表中。重复上一步，直到原始列表只剩下一个元素。保证您的时间复杂度为 O(N^2)。
Strange question, normally we go for the fastest.
Find the highest and move it to a list. Repeat the previous step till the original list has only one element left. You are guaranteed O(N^2).
Bogosort是最糟糕的使用shuffle的排序算法。但从另一个角度来看，一步对数组进行排序的概率很低:)
Bogosort is a worst sorting algorithm uses shuffle. But in another point of view it has low probability to sort array in one step :)
“Worstsort”的复杂度为
其中 
n 迭代 m 次的阶乘。 Miguel A. Lerma 的论文可以在此处找到。
"Worstsort" has a complexity of
where 
factorial of n iterated m times. The paper by Miguel A. Lerma can be found here.
Bogobogo排序。它就像bogo排序，洗牌。但它创建辅助数组，第一个是相同的数组，其他数组比前一个小1个元素。它们也可以被删除。
它的平均复杂度是 O(N superfactorial*n)。最好的情况是 O(N^2)。就像 bogo 排序一样，它的最坏情况也是 O(inf)。
Bogobogo sort.It's like bogo sort,shuffles.But it creates auxiliary arrays,the first one is the same array others are smaller by 1 element compared to previous one.They can be removed as well.
It's average complexity is O(N superfactorial*n). It's best case is O(N^2). Just like bogo sort it has worst case of O(inf).
对于任何事情都不存在效率最低的算法。只要您接受从任何算法开始，都可以构造另一个等效但效率较低的算法，就可以很容易地通过矛盾来证明这一点。
There can be no least efficient algorithm for anything. This can easily be proved by contradiction so long as you accept that, starting from any algorithm, another equivalent but less efficient algorithm can be constructed.
Bogosort 的平均运行时间为
O(n*n!)，哎呀。Bogosort has average runtime of
O(n*n!), ouch.愚蠢的排序无疑是最糟糕的算法。这并不完全是无限循环，但这种方法的最坏情况为
O(inf)，平均为O(n × n!)。The stupid sort is surely the worst algorithm. It's not exactly an infinite loop but this approach has as worst case
O(inf)and the avarage isO(n × n!).您可以在
O(n!*n)中完成此操作，方法是生成所有独特的排列，然后检查数组是否已排序。You can do it in
O(n!*n)by generating all unqiue permutations and afterwards checking if the array is sorted.