这种排序算法的平均性能（大 O 符号）是多少

Question

第 1 步：选择列表中的两个随机元素

第 2 步：如果第一个元素大于第二个元素，则交换它们

第 3 步：重复直到排序

Answer 1

感谢 reddit 上的 u/teraflop，我们现在有了解决方案。在 this paper 中，该算法称为 bozo-sort_opt 并且提到预期的比较次数为 O(n^3 log n)。遗憾的是没有提供证据，但它会做。