algorithm - 随机排序的复杂性

Question

好吧，这可能是对 n 个不同整数的数组 arr 进行排序的最糟糕的方法，但我想分析这个算法:

1. 检查 arr 是否已排序。如果是，返回。
2. 随机排列arr的元素。
3. 重复第 1 步和第 2 步，直到出现返回。

Goofy 的分类程序是否有效？ GoofySort 的最佳案例是什么？最好情况下的运行时间是多少？最坏情况下的运行时间是多少？平均案例运行时间是多少？

Answer 1

这种排序称为 Bogosort .

• 最好的情况是 O(n):您的第一个 shuffle 返回一个排序列表。如果任何大小适中的名单发生这种情况，您可能应该买一张彩票。
• 平均情况是 O((n+1)!)
• 最坏情况是无限的。不能保证随机改组将永远返回排序列表。毕竟是随机的。