algorithm - 对 4 个数字进行排序，比较少

Question

如何在 5 次比较中对 4 个数字进行排序？

Answer 1

将数字 {a,b,c,d} 分成两组 {a,b} {c,d}。对这 2 组中的每一个进行排序，这样您就可以得到 (e,f) (g,h)。这是每组一个比较。

现在从前面选择最低的(比较 e、g)。现在是三个比较。从 (e, h) 或 (f, g) 中选择下一个最低的。那是四个。比较最后两个元素(如果这两个元素来自同一个集合并因此已经排序，您甚至可能不需要此步骤)。那是五个。