好几天前看完的这一章可是一直没写，因为没写，总感觉印象不是很深刻，幸好，现在有点时间，巩固一下。
这一章总共涉及到3个算法，第一个算法很有趣，它的问题是: 一个数组data有n个元素，怎么同时找出最大值和最小值？最直接的算法无疑是下面的：
int max = min = data[0]; for(int i=1; i<data.length; i++) { if(max<data[i]) { max = data[i]; }; if(min>data[i]) { min = data[i]; }; }
可是这样的话，总共比较了2（n-1）次，有没有更好的算法呢？当然有，下面看看这个更好算法。
这个算法的思想是，先给min和max初始化，然后将数组中的元素一对一对的进行比较，比较出来的较大的值再与max比较，较小的值与min进行比较，并作相应的处理(如，给max、min赋新的值等等)。这样下来，第一对值比较了3次，总共比较了3*(n/2)次。这看起来不像从O(n^2)降到O(nlgn)那么明显，不过这的确是一个有趣的算法。
代码：
//同时取得最大值和最小值，int[0]是最小值，int[1]是最大值 public int[] getMaxAndMin() { //先处理一些数组长度方面的特殊情况 int len = data.length; if(len==0) { System.out.println("数组中无数据"); return null; } else if(len==1) { min = max = data[0]; } //对min,max进行初始化，根据数组长度奇偶性不同的，有不同的初始化方法 boolean odd; //用来标志数组长度的奇偶性，在下面代码中还要用到 if(len%2==1) { //如果是长度为奇数，则min和max都初始化为第一个元素 min = data[0]; max = data[1]; odd = true; } else { //如果是长度为偶数，则min初始化为第一、二个元素中较小的数，max初始化为较大的数 if(data[0]<=data[1]) { min = data[0]; max = data[1]; } else { max = data[0]; min = data[1]; } odd = false; } //将数组中剩下的元素一对一对进行比较，将比较的结果保存在bigger, smaller中 //再将bigger, smaller分别和max、min进行比较，并做相应的处理 int bigger, smaller; int i = odd?1:2; for(; i<len; i++) { if(data[i]<=data[i+1]) { smaller = data[i]; bigger = data[i+1]; } else { smaller = data[i+1]; bigger = data[i]; } min = (smaller<min)?smaller:min; max = (bigger>max)?bigger:max; i++; //每次i步进2，所以在这里还要进行一次i++ } int[] result = new int[2]; result[0] = min; result[1] = max; return result; }
第二个算法讲的是从数组data中找出第i小的值(用MINi表示吧)。这个问题看似也好办，先将数组进行排序嘛，然后MINi不就一下就出来了？然而，先进行排序的话，用最popular的快排，所需时间是O(nlogn)，算法的一个很重要的作用就是在解决问题的前提下，怎么样提高效率？
对于当前的这个问题，书上提出一种平均时间在O(n)内找出MINi的算法，这个算法有点像二分法查找，先用快速排序中的partition算法，将数组分成2部分，再将i与pivot的下标（用Ip表示吧）进行比较，如果i==Ip的,那么不用说pivot就是所求的值，这点稍微思考一下，应该很快能理解的。如果i〈Ip的话，则说明MINi应该处在partition所划分的前半部分，接下来对前半部分进行递归处理。类似的，如果i>Ip的话，则说明MINi应该处在后半部分，接下来对后半部分进行递归处理。直到某一次递归处理中，i==Ip，这样，便找出了MINi。
代码如下：
//返回start到end之间第i小的元素值
public int randomizedSelect(int start, int end, int i) { System.out.println("start: "+start+" end: "+end+" i: "+i); if(start==end) { return data[start]; } int m = randomizedPartition(data, start, end); int k = m - start + 1; //k的值是从start开始，data[m]的位置 if(i==k) { return data[m]; } else if(i<k) { return randomizedSelect(start, m-1, i); } else { return randomizedSelect(m+1, end, i-k); } }
其中涉及到的randomizedSelect与前面所讲的快排中的randomizedSelect是一样的。
第三个算法就比较复杂了，但是它解决的问题与第二个是一样的，前面也提到过，第二个算法是在平均条件下，时间复杂度是O(n)，那么第三个算法就更进一步，在最坏的条件下，时间复杂度依然是O(n)。我们叫这个算法为SELECT，它的思想大概是这样的：
1.首先，将这n个数分成ceil（n/5）组，每组5个元素，最后一组n%5个元素。
2.用Insertion Sort将每组进行排序，找出它们的中位数，总共有ceil（n/5）个。
3.用递归的调用SELECT，在第二步找出的ceil（n/5）个中位数，找出他们的中位数（中位数中的中位数），用x表示。
4.用x作为pivot对数组中的n个元素进行快速排序中的partition，如果m表示partition后小于x的部分中的元素个数，则说明x是数组中的第m+1小的元素。
5.如果i==m+1，则x就是所要找的值。否则，如果i〈m+1，则递归调用SELECT，在小于x的部分中找第i小的元素。如果i〉m+1，则递归调用SELECT，在大于x的部分中找第i-(m+1)小的元素。
如果熟悉快排，熟悉递归，则上面的算法还是比较容易理解的，但是我实现了一下，没有成功，原因未知，下次解决了，再把代码贴上来吧。
