快速排序

现有接口ICompareAble

package z.j.sort;

public interface ICompareAble {
	/**
	 * 
	 * @param entity
	 * @return 被比较对象(即this)较小，return -1；相等，return 0；较大，return 1。
	 */
	int compare(ICompareAble entity);
	Object getKey();
}

 

 

排序工具类PlotUtil

 

package z.j.sort;

import java.util.Random;

public class PlotUtil {
	/**
	 * 获取一个随机序列
	 * @param l 长度
	 * @param seed 种子
	 * @return
	 */
	public static ICompareAble[] getArrays(int l, final int seed) {
		ICompareAble[] compareAbles = new ICompareAble[l];
		final Random random = new Random();
		for (int i = 0; i < l; i++) {
			compareAbles[i] = new ICompareAble() {
				int key = random.nextInt(seed);

				public int compare(ICompareAble entity) {
					if (this.key < (Integer) entity.getKey()) {
						return -1;
					} else if (this.key > (Integer) entity.getKey()) {
						return 1;
					} else {
						return 0;
					}
				}

				public Object getKey() {
					return key;
				}

				@Override
				public String toString() {
					return this.getKey().toString();
				}
			};
		}
		return compareAbles;
	}

	/**
	 * 打印序列
	 * @param T
	 * @param b
	 * @param e
	 */
	public static void print(ICompareAble[] T, int b, int e) {
		for (int i = b; i < e; i++) {
			System.out.print(T[i].getKey() + ",");
		}
		System.out.println();
	}

	/**
	 * 验证排序后的序列
	 * @param T
	 */
	public static void validate(ICompareAble[] T){
		for (int i = 0; i < T.length - 1;) {
			if(T[i].compare(T[++i]) > 0){
				throw new RuntimeException("存在相邻两元素，前一个较大");
			}
		}
	}
	
	/**
	 * 区划，并排序
	 * @param T 序列
	 * @param l 左端游标
	 * @param r 右端游标
	 */
	public static void plot(ICompareAble[] T, int l, int r) {
		ICompareAble $ = T[l]; // 控制字
		int b = l, e = r;
		while (l <= r) {
			while (l <= e && T[l].compare($) <= 0)
				l++;
			while (r >= b && T[r].compare($) >= 0)
				r--;
			if (l < r) {
				if (T[l].compare(T[r]) != 0) {
					ICompareAble $t = T[l];
					T[l] = T[r];
					T[r] = $t;
				}
				l++;
				r--;
			}
		}
		assert l > r;

		// 检查前后游标
		int _ = r;
		if (_ > b) {
			// 插入控制字到正确位置
			T[b] = T[_];
			T[_] = $;
			_ = _--;
		}

		if (b < _) {
			plot(T, b, _);
		}
		if (e >= l) {
			plot(T, l, e);
		}
	}

	public static void main(String[] args) {
		ICompareAble[] T = getArrays(220, 100000);
		print(T, 0, T.length - 1);
		plot(T, 0, T.length - 1);
		print(T, 0, T.length - 1);
		validate(T);
	}
	
}