python - 使用最小元素比较对 5 个元素进行排序

Question

我必须在 python 中使用元素之间的最少比较次数对排序 5 个元素的列表的执行计划进行建模。除此之外，复杂性无关紧要。

结果是一个对列表，表示在另一时间对列表进行排序所需的比较。

我知道有一种算法可以在 7 次比较中执行此操作(在元素之间，总是，不考虑复杂性)，但我找不到可读(对我来说)的版本。

如何在 7 次比较中对 5 个元素进行排序，并为排序构建“执行计划”？

PD:不是家庭作业。

Answer 1

嗯，元素的排序方式有 5!=120 种。每次比较都会为您提供一位信息，因此您至少需要进行 k 次比较，其中 2^k >= 120。您可以检查 2^7 = 128，因此 7 是您需要执行的最少比较次数。