java算法：排序实现

排序最基本规则：先比较，再对数据项进行排序。

例1：数据项接口

interfaceItem{
booleanless(Itemv);
}

interface Item{
	boolean less(Item v);
}

例2：排序方法类

classSort{
staticbooleanless(Itemv,Itemw){
returnv.less(w);
}
staticvoidexch(Item[]a,inti,intj){
Itemt=a[i];
a[i]=a[j];
a[j]=t;
}
staticvoidcomExch(Item[]a,inti,intj){
if(less(a[j],a[i])){
exch(a,i,j);
}
voidsort(Item[]a,intl,intr){
example(a,l,r);
}
staticvoidexample(Item[]a,intl,intr){
for(inti=l;i<r;i++){
for(intj=i;j>l;j--){
compExch(a,j-1,j);
}
}
}
}

class Sort{
	static boolean less(Item v, Item w){
		return v.less(w);
	}
	static void exch(Item [] a, int i, int j){
		Item t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	static void comExch(Item [] a, int i, int j){
		if(less(a[j], a[i])){
			exch(a, i, j);
	}
	void sort(Item [] a, int l, int r){
		example(a, l, r);
	}
	static void example(Item [] a, int l, int r){
		for(int i = l; i < r; i++){
			for(int j = i; j > l; j--){
				compExch(a, j - 1, j);
			}
		}
	}
}

数据项ADT的接口：数据项，或要排序的一般对象；数据项数组。

例3：数据项ADT接口

classMyItemimplementsItem{
publicbooleanless(Item)
voidread()
voidrand()
pubicStringtoString()
}

class MyItem implements Item{
	public boolean less(Item)
	void read()
	void rand()
	pubic String toString()
}

排序算法不仅对数据项，也对数据项数组起作用。

例4：可排序的数组ADT接口

classSArray{
SArray(int)
voidrand()
voidread()
voidshow(int,int)
voidsort(int,int)
}

class SArray{
	SArray(int)
	void rand()
	void read()
	void show(int, int)
	void sort(int, int)
}

例5：可排序数组的排序驱动程序

classArraySort{
publicstaticvoidmain(String[]args){
intN=100;
SArraysa=newSArray(100);
sa.rand();
sa.sort(0,N-1);
sa.show(0,N-1);
}
}

class ArraySort{
	public static void main(String [] args){
		int N = 100;
		SArray sa = new SArray(100);
		sa.rand();
		sa.sort(0, N - 1);
		sa.show(0, N - 1);
	}
}

该程序表明：可以定义一个这样的计算而不需要涉及要排序的数据类型。

模块化的组织方式允许用别的实现来代替，这取决于该应用。如，当对大型数组测试排序时，可能会使用只输出部分数组的show的实现。

例6：可排序数组ADT的样本实现

classMyArray{
privateItem[]a;
privateintN;
MyArray(intN){
this.N=N;
a=newItem[N];
for(inti=0;i<N;i++){
a[i]=newItem();
}
}
voidrand(){
for(inti=0;i<N;i++){
a[i].rand();
}
}
voidread(){
for(inti=0;i<N;i++){
if(!In.empty()){
a[i].read();
}
}
}
voidshow(intl,intr){
for(inti=l;i<r;i++){
System.out.println(a[i]+"");
}
}
voidsort(intl,intr){
Sort.sort(a,l,r);
}
}

class MyArray{
	private Item[] a;
	private int N;
	MyArray(int N){
		this.N = N;
		a = new Item[N];
		for(int i = 0; i < N; i++){
			a[i] = new Item();
		}
	}
	void rand(){
		for(int i = 0; i < N; i++){
			a[i].rand();
		}
	}
	void read(){
		for(int i = 0; i < N; i++){
			if(!In.empty()){
				a[i].read();
			}
		}
	}
	void show(int l, int r){
		for(int  i = l; i < r; i++){
			System.out.println(a[i] + " ");
		}
	}
	void sort(int l, int r){
		Sort.sort(a, l, r);
	}
}

对不同类型数据项进行排序的ADT实现。

例7：整数数据项的ADT实现

classMyItemimplementsItem{
privateintkey;
publicbooleanless(Itemv){
returnkey<((Item)v).key;
}
voidread(){
key=In.getInt();
}
voidrand(){
key=(int)(1000*Math.random());
}
publicStringtoString(){
returnkey+"";
}
}

class MyItem implements Item{
	private int key;
	public boolean less(Item v){
		return key < ((Item)v).key;
	}
	void read(){
		key = In.getInt();
	}
	void rand(){
		key = (int)(1000 * Math.random());
	}
	public String toString(){
		return key + "";
	}
}

例8：样本记录类

classRecord{
intid;
doublebalance;
Stringwho;
staticintSortKeyField=0;
publicStringtoString(){
returnid+""+balance+""+who;
}
}

class Record{
	int id;
	double balance;
	String who;
	static int SortKeyField = 0;
	public String toString(){
		return id + " " + balance + " " + who;
	}
}

例9：记录项的ADT实现

classMyItemextendsRecordimplementsItem{
publicbooleanless(Itemv){
MyItemr=(MyItem)v;
switch(SortKeyField){
case2:returnwho.compareTo(r.who)<0;
case1:returnbalance<r.balance;
default:returnid<r.id;
}
}
voidread(){
id=In.getInt();
balance=In.getDouble();
who=In.getString();
}
}

class MyItem extends Record implements Item{
	public boolean less(Item v){
		MyItem r = (MyItem) v;
		switch(SortKeyField){
			case 2: return who.compareTo(r.who) < 0;
			case 1: return balance < r.balance;
			default: return id < r.id;
		}
	}
	void read(){
		id = In.getInt();
		balance = In.getDouble();
		who = In.getString();
	}
}

上述方法在经典文献中被称为指针排序。

例10：字符串数据项的ADT实现

classMyItemimplementsItem{
Stringkey;
publicboolean(Itemv){
returnkey.compareTo(((MyItem)v).key)<0;
}
voidread(){
key=In.getString();
}
voidrand(){
inta=(int)('a');
key="";
for(inti=0;i<1+9*Math.random();i++){
key+=(char)(a+26*Math.random();
}
}
publicStringtoString(){
returnkey;
}
}

class MyItem implements Item{
	String key;
	public boolean(Item v){
		return key.compareTo(((MyItem)v).key) < 0;
	}
	void read(){
		key = In.getString();
	}
	void rand(){
		int a = (int)('a');
		key = "";
		for(int i = 0; i < 1 + 9*Math.random(); i++){
			key += (char)(a + 26*Math.random();
		}
	}
	public String toString(){
		return key;
	}
}

说明了在java中对关键字使用String域直接实现String对象的MyItemADT。

java方法有很多好处。在排序情况下，使用引用避免对排序的数组直接进行操作。即时是只读文件，也能对它进行“排序”。而且，通过使用多重引用数组，能对一个数据体用两种不同的排序表示法来表示。这种不改变数据就能对数据进行操作的灵活性在许多应用中都十分有用的，同时，使用引用能节省移动整个记录的开销。