selectkquantile.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 117 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//16 Nov 2007
package cn.edu.whu.iss.algorithm.unit09;

import cn.edu.whu.iss.algorithm.unit07.QuickSort;

/**
 * Find the k quantile numbers.
 * 
 * @author wpc
 * 
 */
public class SelectKQuantile {
	//Save all data
	private static QuantileData data;
	//The elements
	private static Object[] o;
	//The k quantiles
	private static int k;

	/**
	 * Get the k quantile numbers
	 * @param element the object list
	 * @param k the k quantile
	 * @return result
	 */
	public static Object[] get(Object[] element, int k) {
		SelectKQuantile.o = element;
		SelectKQuantile.k = k;
		if (checkOk()) {
			data = new QuantileData(o.length, k);
			get(o, 0, o.length - 1);
			return getResult();
		} else {
			System.err.println("Error Input data");
			return null;
		}
	}

	/**
	 * Check whether it has the result
	 * @return
	 */
	private static boolean checkOk() {
		if (o.length < k) {
			return false;
		} else if (k < 2) {
			return false;
		} else {
			return true;
		}
	}

	/**
	 * Get the result
	 * @return
	 */
	private static Object[] getResult() {
		Object[] list = new Object[k - 1];
		int[] r = data.getKResult();
		for (int i = 0; i < k - 1; i++) {
			list[i] = o[r[i]];
		}
		QuickSort.selectSort(list);
		return list;
	}

	/**
	 * Get 
	 * @param element
	 * @param p
	 * @param r
	 */
	private static void get(Object[] element, int p, int r) {
		if ((data.isFull()) || (p > r)) {
			return;
		}
		if (p == r) {
			data.add(p);
			return;
		}

		int q = QuickSort.randomizedPartition(element, p, r);
		int k = q;

		if (data.contains(k)) {
			data.add(k);
		}
		if (data.isFull()) {
			return;
		}

		if (data.checkHave(p, q - 1)) {
			get(element, p, q - 1);
		}
		if (data.checkHave(q + 1, r)) {
			get(element, q + 1, r);
		}
	}
}