permutelist.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.
 */
//24 Jan 2008
package cn.edu.whu.iss.algorithm.unit05;

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

import java.util.Arrays;


public class PermuteList<T> {
	public void permuteBySorting(T[] a){
		class Pcmp<T> implements Comparable<Pcmp<T>>{
			private int p;
			private T o;
			public int compareTo(Pcmp<T> o) {
				return p-o.getP();
			}

			public Pcmp(int p, T o) {
				super();
				this.p = p;
				this.o = o;
			}

			public int getP() {
				return p;
			}

			public T getO() {
				return o;
			}
			
		}
		int n = a.length;
		int m = n*n*n;
		Pcmp[] p = new Pcmp[n];
		for(int i=0;i<n;i++){
			p[i] = new Pcmp<T>(randomInt(1, m),a[i]);
		}
		Arrays.sort(p);
		for(int i=0;i<p.length;i++){
			a[i] = (T) p[i].getO();
		}
	}
	
	public void permuteRandomizeInPlace(T[] a){
		int n=a.length;
		for(int i=0;i<n;i++){
			swap(a, i, randomInt(i, n-1));
		}
	}

}