countingsort.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * 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.
 */
//2 Nov 2007
package cn.edu.whu.iss.algorithm.unit08;

import static cn.edu.whu.iss.algorithm.basictools.BasicSortTool.*;

/**
 * The counting sort.Because of not using compare methodk,O(n) But this method
 * can't solve the problem very well.
 * 
 * @author wpc
 * @version 0.0.1
 */
public final class CountingSort {

	/**
	 * Counting number
	 */
	private static Integer[] countingNumber;

	/**
	 * The object list waiting for sort
	 */
	private static Object[] element;

	private static int maxK;

	/**
	 * The main method for sorting the elements. And the elements must be the
	 * integer.But this method need another O(n) memory.
	 * 
	 * @param element
	 */
	public static void sort(Object[] element) {
		CountingSort.element = element;
		sort();
	}

	/**
	 * Counting sort the array of element by the keyword
	 * @param element array 
	 * @param keyword keyword
	 */
	public static void sort(Object[] element,Object[] keyword){
		CountingSort.element = keyword;
		sortByKeyword(element);
	}
	
	/**
	 * Sort the o array by the keyword element(static)
	 * @param o
	 */
	private static void sortByKeyword(Object[] o){
		initCountingNumber();
		Object[] a = element.clone();
		Object[] s = o.clone();
		for (int i = a.length - 1; i >= 0; i--) {
			int k = countingNumber[toInteger(a[i])] - 1;
			element[k] = a[i];
			o[k] = s[i];
			countingNumber[toInteger(a[i])]--;
		}
	}
	
	/**
	 * Sort the elements(a) and save them to the b
	 * 
	 * @param a
	 * @param b
	 * @param k
	 */
	protected static void sort(Object[] a, Object[] b, Object k) {
		int maxK = toInteger(k);

		// Count the number.
		Integer[] c = new Integer[maxK + 1];
		// Initial the c
		for (int i = 0; i <= maxK; i++) {
			c[i] = 0;
		}

		for (int i = 0; i < a.length; i++) {
			c[toInteger(a[i])]++;
		}

		for (int i = 1; i <= maxK; i++) {
			c[i] += c[i - 1];
		}
		for (int i = a.length - 1; i >= 0; i--) {
			b[c[toInteger(a[i])] - 1] = a[i];
			c[toInteger(a[i])]--;
		}
	}

	/**
	 * For the sort()
	 * 
	 */
	private static void sort() {
		initCountingNumber();
		Object[] a = element.clone();
		for (int i = a.length - 1; i >= 0; i--) {
			element[countingNumber[toInteger(a[i])] - 1] = a[i];
			countingNumber[toInteger(a[i])]--;
		}
	}

	/**
	 * O(n) counting sort without using another memory.
	 * @param element
	 */
	public static void constantSort(Object[] element) {
		CountingSort.element = element;
		constantSort();
	}

	private static void constantSort() {
		initCountingNumber();
		int i = element.length-1;
		while (true) {
			while ((i >= 0) && (countingNumber[toInteger(element[i])] == i+1)) {
				countingNumber[toInteger(element[i])]--;
				i--;
			}
			while ((i >= 0) && (countingNumber[toInteger(element[i])]< i+1)) {
				i--;
			}
			
			if (i < 0) {
				break;
			}
			Object o = element[countingNumber[toInteger(element[i])]-1];
			element[countingNumber[toInteger(element[i])]-1] = element[i];
			countingNumber[toInteger(element[i])]--;
			element[i] = o;
		}
	}
 
	/**
	 * 
	 * @param o
	 * @return
	 */
	private static int toInteger(Object o) {
		return Integer.parseInt(o.toString());
	}

	/**
	 * Init the max number of k in the list of elements
	 * 
	 */
	private static void initMaxK() {
		maxK = toInteger(max(element));
	}

	/**
	 * Initalize the counting numbers
	 * 
	 */
	private static void initCountingNumber() {
		if (element != null) {
			initMaxK();
			countingNumber = new Integer[maxK + 1];
			for (int i = 0; i < countingNumber.length; i++) {
				countingNumber[i] = 0;
			}

			for (int i = 0; i < element.length; i++) {
				countingNumber[toInteger(element[i])]++;
			}

			for (int i = 1; i <= maxK; i++) {
				countingNumber[i] += countingNumber[i - 1];
			}
		}
	}

	/**
	 * 
	 * @param o
	 */
	private static void initCountingNumber(Object[] o) {
		element = o;

		initMaxK();
		countingNumber = new Integer[maxK + 1];
		for (int i = 0; i < countingNumber.length; i++) {
			countingNumber[i] = 0;
		}

		for (int i = 0; i < element.length; i++) {
			countingNumber[toInteger(element[i])]++;
		}

		for (int i = 1; i <= maxK; i++) {
			countingNumber[i] += countingNumber[i - 1];
		}
	}

	public static Integer[] getCountingNumberByList(Object[] o) {
		initCountingNumber(o);
		return countingNumber;
	}

	public static Integer[] getCountingNumber() {
		return countingNumber;
	}

	public static void setCountingNumber(Integer[] countingNumber) {
		CountingSort.countingNumber = countingNumber;
	}

	public static int getMaxK() {
		return maxK;
	}

	public static void setMaxK(int maxK) {
		CountingSort.maxK = maxK;
	}
}