BFPRT 算法

今天我写这个算法的时候发现了很多运行的时候总是有很多问题，先挂上代码：

package org.iaiai.suanfa;

/**
 * 
 * <p>
 * Title: BFPRT.java
 * </p>
 * <p>
 * E-Mail: [e-mail]
 * </p>
 * <p>
 * QQ: 176291935
 * </p>
 * <p>
 * Http: iaiai.iteye.com
 * </p>
 * <p>
 * Create time: 2011-8-5
 * </p>
 * 
 * @author 丸子
 * @version 0.0.1
 */
public class BFPRT {

	public static final int N = 5;
	public static int number[];

	public BFPRT(int size) {
		number = new int[size];
		System.out.println("the arrray is:");
		for (int i = 0; i < size; i++) {
			number[i] = (int) (Math.random() * 12);
			System.out.print(number[i] + ",");
		}
		System.out.println("");
	}

	public void sw(int i, int j) {
		int tmp = number[i];
		number[i] = number[j];
		number[j] = tmp;

		/*
		 * number[i]^=number[j]; number[j]^=number[i]; number[i]^=number[j];
		 */
	}

	public void bubleSort(int begin, int end) { // /元素不包括end的
		for (int i = end - 1; i > 0; i--) {
			for (int j = begin; j < i; j++) {
				if (number[j] > number[j + 1]) {
					sw(j, j + 1);
				}
			}
		}
	}

	public int partion(int begin, int end, int NUM) {// 将小于NUM的放在左边，将大于等于NUM的放在右边
		int pbegin = begin;
		int pend = end - 1;
		System.out.println("the NUM:" + NUM);
		while ((pbegin <= pend)) {
			System.out.println("pbegin=" + pbegin);
			System.out.println("number[pbegin]=" + number[pbegin]);
			System.out.println("number[pbegin]>=NUM: "
					+ (number[pbegin] >= NUM));
			if ((number[pbegin] >= NUM)) {
				while ((number[pend] >= NUM)) {
					System.out.println("pend=" + pend);

					pend--;
				}
				if (pbegin > pend) { // 这里要判断是否越界了
					return pbegin;
				}
				sw(pbegin, pend);
				System.out.println("pend==" + pend + " and pbegin=" + pbegin);
				pend--;
			}
			pbegin++;
		}
		return pbegin;
	}

	public void printARR(int begin, int end) {
		System.out.println("the array is:");
		for (int i = begin; i < end; i++) {
			System.out.print(number[i] + ",");
		}
		System.out.print("\n");
	}

	public int selectKnum(int begin, int end, int K) { // 寻找第K小的
		// printARR(begin,end);
		int i = 0;
		int size = end - begin;
		if (size <= 9) {
			if (K > size) {
				System.out
						.println("the K is:" + K + " and the size is:" + size);
				System.out.println("the K is overall the numbers length");
				return -1;
			}
			bubleSort(begin, end);
			return number[begin + K - 1];
		}
		for (i = 0; i < (end - begin) / N; i++) {
			bubleSort(i * N + begin, (i + 1) * N + begin);
			sw(begin + i, i * N + 2 + begin); // 将每一组中的中位数放到数组的前面去
		}
		printARR(begin, end);
		System.out.println("the i is:" + i);
		int x = selectKnum(begin, begin + i, (end - begin + 6) / 10);
		int Pnow = partion(begin, end, x);
		int j = Pnow - begin;
		printARR(begin, end);
		System.out.println("the x is:" + x);
		System.out.println("the pNow is:" + Pnow);
		System.out.println("the j is:" + j);
		System.out.println("the K is: " + K);
		if (K > j) {
			return selectKnum(Pnow, end, K - j);
		} else {
			return selectKnum(begin, Pnow, K);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int size = 15;
		int nth = 14;
		BFPRT A = new BFPRT(size);
		int num = A.selectKnum(0, size, nth);
		System.out.println("the " + nth + "'num is:" + num);
	}

}

运行后直接爆栈！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

引用

the array is:
2,3,2,7,8,2,2,2,3,9,8,
the x is:2
the pNow is:4
the j is:0
the K is: 10
the array is:
3,2,2,7,8,2,2,2,3,9,8,
the i is:2
the NUM:2
pbegin=4
number[pbegin]=2
number[pbegin]>=NUM: true
pend=14
pend=13
pend=12
pend=11
pend=10
pend=9
pend=8
pend=7
pend=6
pend=5
pend=4
the array is:
2,3,2,7,8,2,2,2,3,9,8,
the x is:2
the pNow is:4
the j is:0
the K is: 10
the array is:
3,2,2,7,8,2,2,2,3,9,8,
the i is:2
the NUM:2
pbegin=4
number[pbegin]=2
number[pbegin]>=NUM: true
pend=14
pend=13
pend=12
pend=11
pend=10
pend=9
pend=8
pend=7
pend=6
pend=5
pend=4
the array is:
2,3,2,7,8,2,2,2,3,9,8,
the x is:2
the pNow is:4
the j is:0
the K is: 10
the array is:
3,2,2,7,8,2,2,2,3,9,8,
the i is:2
the NUM:2
pbegin=4
number[pbegin]=2
number[pbegin]>=NUM: true
pend=14
pend=13
pend=12
pend=11
pend=10
pend=9
pend=8
pend=7
pend=6
pend=5
pend=4
the array is:
2,3,2,7,8,2,2,2,3,9,8,
the x is:2
the pNow is:4
the j is:0
the K is: 10
the array is:
3,2,2,7,8,2,2,2,3,9,8,
the i is:2
the NUM:2
pbegin=4
number[pbegin]=2
number[pbegin]>=NUM: true
pend=14
pend=13
pend=12
pend=11
pend=10
pend=9
pend=8
pend=7
pend=6
pend=5
pend=4
the array is:
2,3,2,7,8,2,2,2,3,9,8,
the x is:2
the pNow is:4
the j is:0
the K is: 10
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.ext.GB18030$Encoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.ext.GB18030$Encoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at BFPRT.printARR(BFPRT.java:59)
at BFPRT.selectKnum(BFPRT.java:83)
at BFPRT.selectKnum(BFPRT.java:94)
at BFPRT.selectKnum(BFPRT.java:94)

看到没有，总是在两个数组之间不停的切换，原因是在数字有相同的情况下，可能存在一种情况就是那样的，select与partion不停的切换，而且此时select找到的中位数在第一位，后来的partion找到把数组还原了。

所以我的程序是有BUG的，如何消除由相同数的影响，你可以采用重新随机打乱来操做（但是还是可能会出现那样的情况，比如全部是2），所以这样地方法适用在所有数字互不相同的情况下面。切记这个话，所以这个算法不是万能的，要分情况使用；