最小的次数找中位数&排序

题目

试设计比较策略：用 6 次比较在 5 个元素中找到中位数；用 7 次比较完成 5 个元素的排序。

解析思路：

a1 a2 a3 a4 a5

6次比较寻找中位数

• 第一步：比较 a1,a2 得出二者大小顺序 a1 < a2
• 第二步：比较 a3,a4 得出二者大小顺序 a3 < a4
• 第三步,第四步：a5 与a3,a4进行比较，得出 a3<a4<a5
• 第五步，第六步：a2分别跟a3,a4进行比较，得出中位数

7次比较排序5个元素

• 第一步：比较 a1,a2 得出二者大小顺序 a1 < a2
• 第二步：比较 a3,a4 得出二者大小顺序 a3 < a4
• 第三步：两组中小的相比 得出假设结果：a1<a3<a4,a1<a2
• 第四步,第五步：a5向长链中的中间值做比较，进行两次比较，得出结果:a1<a3<a4<a5 ，a1<a2
• 第六步，第七步，拿a2 a4比较，然后再将a2跟 a3或者a5比较