好几天前看完的这一章可是一直没写,因为没写,总感觉印象不是很深刻,幸好,现在有点时间,巩固一下。
这一章总共涉及到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)小的元素。
如果熟悉快排,熟悉递归,则上面的算法还是比较容易理解的,但是我实现了一下,没有成功,原因未知,下次解决了,再把代码贴上来吧。