关于最小排序算法的建议

这个算法的效率是多少?

好可怕。

• 对于列表中的每个项(O(N)操作)
• …取剩余列表的最大值或最小值(O(N)操作)
• …然后将需要列表压缩的项从原始项中移除(也是O(N)操作)。

所以这是一个o(n^3)算法。立方体复杂度=非常非常差。

有什么改进可以使这个算法更快吗?

删除它并使用正确的排序算法。排序是一个已解决的问题,除非您有一些可以利用的特定于域的数据模式,所以不要重新发明wheel=)

• 气泡排序->o(n^2)
• 插入排序->o(n^2)
• 快速排序->o(n日志n)
• 合并排序->o(n日志n)

特别是对于python,使用内置的sort函数;这是一个很好的算法,而且很可能是由本机实现支持的,这将比在解释代码中执行相同的算法更快。

我相信你在说 selection sort ,或者至少是非常相似的东西。选择排序具有 O(n^2) 复杂度(虽然由于该算法产生下一个值,而不是将其移动到列表的前面,它需要 O(n^3) solidpixel的答案解释了时间),所以并不理想。在改进方面,您最好的选择可能是使用不同的算法-插入排序也是 o(n^2) 但是在小列表上更有效,在大列表上应该使用 O(n log n) 排序。

或者,如果对您非常重要的是,您必须立即产生第一个值(例如,它是一个非常大的列表,并且您需要排序列表的第一个元素比您处理整个列表要快得多),而不是删除该值,您可以用最小值覆盖它(或者将最小值保存在某个地方,所以你不需要每次都重新计算)。这避免了列表压缩的问题,减少了 N 在复杂性方面。