这是一个不可变的 Scala 版本,它具有最少的比较次数 (6) 并且看起来不太难看:
def med5(five: (Int,Int,Int,Int,Int)) = {
// Return a sorted tuple (one compare)
def order(a: Int, b: Int) = if (a<b) (a,b) else (b,a)
// Given two self-sorted pairs, pick the 2nd of 4 (two compares)
def pairs(p: (Int,Int), q: (Int,Int)) = {
(if (p._1 < q._1) order(p._2,q._1) else order(q._2,p._1))._1
}
// Strategy is to throw away smallest or second smallest, leaving two self-sorted pairs
val ltwo = order(five._1,five._2)
val rtwo = order(five._4,five._5)
if (ltwo._1 < rtwo._1) pairs(rtwo,order(ltwo._2,five._3))
else pairs(ltwo,order(rtwo._2,five._3))
}
编辑:根据丹尼尔的要求,这是一个适用于所有尺寸和数组的修改,因此它应该是高效的。我无法让它变得漂亮,所以效率是第二好的事情。 (>200M 中位数/秒,预分配数组为 5,比 Daniel 的版本快 100 倍多一点,比我上面的不可变版本(长度为 5)快 8 倍)。
def med5b(five: Array[Int]): Int = {
def order2(a: Array[Int], i: Int, j: Int) = {
if (a(i)>a(j)) { val t = a(i); a(i) = a(j); a(j) = t }
}
def pairs(a: Array[Int], i: Int, j: Int, k: Int, l: Int) = {
if (a(i)<a(k)) { order2(a,j,k); a(j) }
else { order2(a,i,l); a(i) }
}
if (five.length < 2) return five(0)
order2(five,0,1)
if (five.length < 4) return (
if (five.length==2 || five(2) < five(0)) five(0)
else if (five(2) > five(1)) five(1)
else five(2)
)
order2(five,2,3)
if (five.length < 5) pairs(five,0,1,2,3)
else if (five(0) < five(2)) { order2(five,1,4); pairs(five,1,4,2,3) }
else { order2(five,3,4); pairs(five,0,1,3,4) }
}