
因为只能比较6次,所以这个程序不能使用排序算法。
众所周知,5个整数需要完成排序,最少需要7次比较。
也就是,不能先让数组排序,然后输出中间那位。
只能一次性找到中位数。
public class Main { public static void main(String[] args) { // TODO Auto-generated method stub // Input int[] a = new int[5]; int mid; for (int i = 0; i < 5; i++) { a[i] = Integer.parseInt(args[i]); } // Sort if (a[0] < a[1]) { int tmp = a[0]; a[0] = a[1]; a[1] = tmp; } if (a[2] < a[3]) { int tmp = a[2]; a[2] = a[3]; a[3] = tmp; } if (a[0] < a[2]) { int tmp = a[0]; a[0] = a[2]; a[2] = tmp; tmp = a[1]; a[1] = a[3]; a[3] = tmp; } if (a[1] < a[4]) { int tmp = a[1]; a[1] = a[4]; a[4] = tmp; } if (a[1] < a[2]) { int tmp = a[1]; a[1] = a[2]; a[2] = tmp; tmp = a[3]; a[3] = a[4]; a[4] = tmp; } if (a[4] < a[2]) { mid = a[2]; } else { mid = a[4]; } // Output System.out.println(mid); } }
这个方法与一种排序方法类似,不完全一致,就是分成有序区域和无序区域。
前2次判断保证了[0]>[1]、[2]>[3]。
第3次判断保证了[0]>[2]。
因此,到这里为止,[0]、[1]、[2]、[3]这4个数里,[0]是最大的。
不论[4]比[0]大还是比[0]小,[0]都不可能是中位数了。
第3次比较,如果需要交换,那么不仅要交换[0]和[2],还要把[1]和[3]一起交换。
至于为什么要一起交换,因为[0]>[1]、[2]>[3],应该把[0]和[1]、[2]和[3]看成组合了,如果[0]和[2]交换了,就要把[1]和[3]也一块儿交换了,不然的话(比如只交换了[0]和[2]),交换之后可能不是有序的(由于此时[0]是最大的,所以[0]>[1]显然保证,但是也许无法保证[0]和[2]交换以后,[2]还是大于[3]),只有一起交换才能保证已知组合都是有序的。
后面第4次比较保证[1]>[4]。
这时又回到了与最初情况类似的状态,[1]>[4]和[2]>[3]。
下面继续,第5次比较,比较[1]和[2],这里就相当于上面比较的[0]和[2]。
同样地,保证了[1]是[1]、[2]、[3]、[4]这4个数中最大的,所以也不可能是中位数。
这样一来,中位数只可能是[2]、[3]、[4]中的一个。
而[2]>[3],所以[3]不可能是中位数。
最后一次比较只要在[2]和[4]中比较就行了。
谁大,谁就是中位数。