编程之美2.10： 对于一个有N个整数组成的数组，需要比较多少次才能把最大值和最小值找出来呢?
算法的思想是: 分而治之
测试数据：----------------------------------------------------
int [] input1 = { 94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72 };
最大数据：679
最小数据：1
第二大数：435
--------------------------------------------------------------
方法一：递归
// 方法一： 递归法 (分而治之） public static void FindMaxAndMinValues(int[] array, int startIndex, int endIndex, out int max, out int min) { int tempMaxL, tempMaxR, tempMinL, tempMinR; tempMaxL = tempMaxR = tempMinL = tempMinR = 0; if (endIndex - startIndex > 1) { FindMaxAndMinValues(array, startIndex, startIndex + (endIndex - startIndex) / 2, out tempMaxL, out tempMinL); FindMaxAndMinValues(array, startIndex + (endIndex - startIndex) / 2 + 1, endIndex, out tempMaxR, out tempMinR); } else { if (array[startIndex] > array[endIndex]) { max = array[startIndex]; min = array[endIndex]; } else { max = array[endIndex]; min = array[startIndex]; } return; } max = tempMaxL > tempMaxR ? tempMaxL : tempMaxR; min = tempMinL < tempMinR ? tempMinL : tempMinR; }
方法二：非递归方式
// 方法二： 非递归的实现分而治之。 public static void FindMaxAndMinValues2(int[] array, out int max, out int min) { int startIndex = 0; if (array.Length % 2 == 0) // 偶数 { max = array[0] > array[1] ? array[0] : array[1]; min = array[0] < array[1] ? array[0] : array[1]; startIndex = 2; } else // 奇数 { max = min = array[0]; startIndex = 1; } for (int i = startIndex; i < array.Length; i += 2) { int tempMaxValue = Math.Max(array[i], array[i + 1]); int tempMinValue = Math.Min(array[i], array[i + 1]); if (tempMaxValue > max) { max = tempMaxValue; } if (tempMinValue < min) { min = tempMinValue; } } }
可以将递归的分而治之算法划分成以下的步骤：
1) 从图1 4 - 2中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问题的大小为1或2。
2) 比较每个大小为2的问题中的金块，确定哪一个较重和哪一个较轻。在节点D、E、F和G上完成这种比较。大小为1的问题中只有一个金块，它既是最轻的金块也是最重的金块。
3) 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。对于节点A到C执行这种比较。根据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值，这个工作对应于3 )。
for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。
下面进行复杂性分析。注意到当n为偶数时，在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 )次比较，比较的总次数为3 n / 2 - 2。当n 为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数，当n>0时，比较的总次数为「3n/2ù-2次
引申：
1. 如果需要找出N个数组中的第二大数，需要比较多少次呢？是否可以使用类似的分而治之思想来降低比较的次数呢？
// 寻找第二大的数.(分而治之） public static void FindSecondMaxValue(int[] array, out int max, out int secondMax) { max = secondMax = 0; int startIndex = 0; if (array.Length % 2 == 0) // 偶数 { max = array[0] > array[1] ? array[0] : array[1]; secondMax = array[0] < array[1] ? array[0] : array[1]; startIndex = 2; } else // 奇数 { max = secondMax = array[0]; startIndex = 1; } for (int i = startIndex; i < array.Length; i += 2) { int tempMaxValue = Math.Max(array[i], array[i + 1]); if (tempMaxValue > max) { secondMax = max; max = tempMaxValue; } else { if (tempMaxValue > secondMax) { secondMax = tempMaxValue; } } } }