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

/**
 * Radix sort O(n)
 * @author wpc
 * @version 0.0.1
 */
public class RadixSort {

	/**
	 * The waiting for sorting elements
	 */
	private static Object[] element;

	/**
	 * The max digit
	 */
	private static int maxd;

	/**
	 * Sort the elements
	 * @param element
	 */
	public static void sort(Object[] element) {
		RadixSort.element = element;
		init();
		sort();
	}

	/**
	 * Initalize the maxd
	 *
	 */
	private static void init() {
		maxd = 0;
		for (int i = 0; i < element.length; i++) {
			maxd = Math.max(maxd, element[i].toString().length());
		}
	}

	/**
	 * Sort
	 *
	 */
	private static void sort() {
		for (int i = 1; i <= maxd; i++) {
			CountingSort.sort(element, getKeyWord(i));
		}
	}

	/**
	 * Get the key word by the static element
	 * @param d
	 * @return
	 */
	public static Integer[] getKeyWord(int d) {
		Integer[] a = new Integer[element.length];
		for(int i=0;i<a.length;i++){
			String s = element[i].toString();
			if(s.length()<d){
				a[i] = 0;
			}else{
				a[i] = s.charAt(s.length()-d)-'0';
			}
		}
		return a;
	}
}