sortdemo.java

*一个简单的能够形象演示各种排序算法的applet小程序 *类似于Sun公司的示例程序

//<applet code = SortDemo.class width=880 height=500>
//</applet>
/**
 *一个简单的能够形象演示各种排序算法的applet小程序
 *类似于Sun公司的示例程序，但比它复杂一点，
 *因为这个程序支持简单选择排序，冒泡排序，双向冒泡，
 *快速排序，希尔排序，堆排序,归并排序共七种排序算法
 *每次80个整数随机生成，七种算法同时运行，之间的对比非常明显
 *
 *author:Skyang      徐阳
 *school:nuaa
 *E_mail:[e-mail]
 *QQ:530139481
 *
 *All rights reserved,it's just for studying and researching,
 *you should not use it for other purpose.Thank you!
 **/
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class Material{
	int x,y;
	int num;
}

public class SortDemo extends Applet implements Runnable{
	int W,H;
	Graphics drawOffScreen;
	Image OffScreen;
	boolean start = true;

	Material M[][] = new Material[7][80];
	isRandom AA;

	Thread controlRepaint;//repaint every 20ms
	Thread1 th1;//Simple Selection Sort
	Thread2 th2;//Bubble Sort
	Thread3 th3;//Bidirectional Bubble Sort
	Thread4 th4;//Quick Sort
	Thread5 th5;//ShellSsort
	Thread6 th6;//HeapSort
	Thread7 th7;//MergeSort
//	Thread8 th8;

	class isRandom{
		Material p[] = new Material[80];
		public isRandom(){
			for(int i=0;i<80;i++){
				p[i] = new Material();
				p[i].num = (int)(Math.random()*140+10);
			}
		}
	}

	public void init(){
		W = this.getWidth();
		H = this.getHeight();
		OffScreen = this.createImage(W,H);
		drawOffScreen = OffScreen.getGraphics();
		AA = new isRandom();

		for(int i=0;i<7;i++)
			for(int j=0;j<80;j++){
				M[i][j] = new Material();
				M[i][j].num = AA.p[j].num;
				if(i<4){
					M[i][j].x = (3*i+1)*65+2*j;
					M[i][j].y = 200;
				}
				else{
					M[i][j].x = (3*i-11)*65+2*j;
					M[i][j].y = 450;
				}
			}
		//先画一下
		for(int i=0;i<7;i++)
			drawLine(i);

		//启动线程
		controlRepaint = new Thread(this);
		controlRepaint.start();

		th1 = new Thread1();//Simple Selection Sort
		th2 = new Thread2();//Bubble Sort
		th3 = new Thread3();//Bidirectional Bubble Sort
		th4 = new Thread4();//QuickSort
 		th5 = new Thread5();//ShellSort
		th6 = new Thread6();//HeapSort
		th7 = new Thread7();//MergeSort
//		th8 = new Thread8();

		th1.start();
		th2.start();
		th3.start();
		th4.start();
 		th5.start();
		th6.start();
		th7.start();
//		th8.start();

	}

	public void paint(Graphics g){
		g.drawImage(OffScreen,0,0,this);
	}

	public void update(Graphics g){
		paint(g);
	}

	public void drawLine(int m){
		//公用画线方法
		drawOffScreen.setColor(Color.black);
		for(int j=0;j<80;j++)
			drawOffScreen.fillRect(M[m][j].x,M[m][j].y-M[m][j].num,1,M[m][j].num);
	}

	public void run(){
		while(controlRepaint!=null){
			repaint();

			try{
				controlRepaint.sleep(20);
			}
			catch(Exception e){
			}
		}
	}

	public void start(){

	}

	public void stop(){

	}

	class Thread1 extends Thread{//simple selection sort
		boolean notComplete = true;
		public void run(){
			int min,k,temp;
			while(start && notComplete){
				for(int i=0;i<79;i++){
					min = M[0][i].num;
					k = i;
					for(int j=i;j<80;j++){
						if(M[0][j].num<min){
							min = M[0][j].num;
							k=j;
						}//if
						try{
							drawOffScreen.clearRect(0,0,230,200);
							drawOffScreen.setColor(Color.red);
							drawOffScreen.fillRect(M[0][j].x+1,M[0][j].y-150,1,150);
							drawOffScreen.setColor(Color.blue);
							drawOffScreen.fillRect(M[0][i].x-1,M[0][i].y-150,1,150);
							drawLine(0);
							Thread.sleep(20);
						}
						catch(Exception e){
						}
					}
					temp = M[0][i].num;
					M[0][i].num = M[0][k].num;
					M[0][k].num = temp;//将最大值M[0][k].num与M[0][i].num交换
				}//for
				notComplete = false;
			}//while
		}//run
	}//Thread1

	class Thread2 extends Thread{//bubble sort
		boolean notComplete = true;
		public void run(){
			int temp;
			while(start && notComplete){
			for(int i=0;i<79;i++){
				for(int j=0;j<79-i;j++){
					if(M[1][j].num>M[1][j+1].num){
						temp = M[1][j].num;
						M[1][j].num = M[1][j+1].num;
						M[1][j+1].num = temp;//交换num
					}//if
					try{
						drawOffScreen.clearRect(230,0,200,200);
						drawOffScreen.setColor(Color.red);
						drawOffScreen.fillRect(M[1][j].x-1,M[1][j].y-150,1,150);
						drawOffScreen.setColor(Color.blue);
						drawOffScreen.fillRect(M[1][79-i].x+1,M[1][79-i].y-150,1,150);
						drawLine(1);
						Thread.sleep(20);
					}
					catch(Exception e){
					}
				}
			}//for
			notComplete = false;
		}//while
		}//run
	}//Thread2

	class Thread3 extends Thread{
		boolean notComplete = true;
		boolean exchanged = true;//如果一轮没有交换表明排序已经完成
		public void run(){
			int low,high;
			int i,j;
			int temp;
			low = 0;
			high = 79;
			while(start && notComplete){
				while(low<high && exchanged){
					exchanged = false;
					i = low;
					while(i<high){
						if(M[2][i].num>M[2][i+1].num){
							temp = M[2][i].num;
							M[2][i].num = M[2][i+1].num;
							M[2][i+1].num = temp;
							exchanged = true;//说明有交换
						}//在这下面画线
						try{
							drawOffScreen.clearRect(430,0,200,200);
							drawOffScreen.setColor(Color.red);
							drawOffScreen.fillRect(M[2][i].x-1,M[2][i].y-150,1,150);

							drawOffScreen.setColor(Color.blue);
							drawOffScreen.fillRect(M[2][low].x-1,M[2][low].y-150,1,150);
							drawOffScreen.fillRect(M[2][high].x+1,M[2][high].y-150,1,150);
							drawLine(2);
							Thread.sleep(20);
						}
						catch(Exception e){
						}
						i++;
					}
					high--;
					j=high;
					while(j>low){
						if(M[2][j].num<M[2][j-1].num){
							temp = M[2][j].num;
							M[2][j].num = M[2][j-1].num;
							M[2][j-1].num = temp;
							exchanged = true;//说明有交换
						}//在这下面画线
						try{
							drawOffScreen.clearRect(430,0,200,200);
							drawOffScreen.setColor(Color.red);
							drawOffScreen.fillRect(M[2][j].x+1,M[2][j].y-150,1,150);

							drawOffScreen.setColor(Color.blue);
							drawOffScreen.fillRect(M[2][low].x-1,M[2][low].y-150,1,150);
							drawOffScreen.fillRect(M[2][high].x+1,M[2][high].y-150,1,150);
							drawLine(2);
							Thread.sleep(20);
						}
						catch(Exception e){
						}
						j--;
					}
					low++;
				}
				notComplete = false;
			}//while
		//	drawOffScreen.clearRect(430,0,200,200);
		//	drawLine(2);
		}
	}//Thread3

	class Thread4 extends Thread{
		boolean notComplete = true;
		private	int Partition(int low,int high){
			int pivotkey,temp;
			pivotkey = low;
			temp = M[3][pivotkey].num;
			while(low<high){
				try{

					while(M[3][high].num >= temp && low<high){
						high--;
						drawOffScreen.clearRect(640,0,240,200);
						drawOffScreen.setColor(Color.red);
						drawOffScreen.fillRect(M[3][low].x-1,M[3][low].y-150,1,150);
						drawOffScreen.setColor(Color.blue);
						drawOffScreen.fillRect(M[3][high].x+1,M[3][high].y-150,1,150);

						drawLine(3);
						Thread.sleep(20);//每次移动一下暂停一下
					}
					M[3][low].num = M[3][high].num;
					pivotkey = high;

					while(M[3][low].num <= temp && low<high){
						low++;
						drawOffScreen.clearRect(640,0,240,200);
						drawOffScreen.setColor(Color.red);
						drawOffScreen.fillRect(M[3][low].x-1,M[3][low].y-150,1,150);
						drawOffScreen.setColor(Color.blue);
						drawOffScreen.fillRect(M[3][high].x+1,M[3][high].y-150,1,150);

						drawLine(3);
						Thread.sleep(20);//每次移动一下暂停一下
					}

					pivotkey = low;
					M[3][high].num = M[3][low].num;
				}
				catch(Exception e){
				}
			}
			M[3][pivotkey].num = temp;
			return pivotkey;
		}
		private void QuickSort(int low,int high){
			int p;
			if(low < high){
				p = Partition(low,high);
				QuickSort(low,p-1);
				QuickSort(p+1,high);
			}
			notComplete = false;
		}
		public void run(){
			while(start && notComplete && th4!=null)
			QuickSort(0,79);
		}
	}//Thread4

	class Thread5 extends Thread{
		boolean notComplete = true;
		private void shellInsertion(int delta){
			//shellSort总共用到4轮循环，shellInsertion中出现3轮
			int temp;
			int i,j,k;
			for(k=0;k<delta;k++){
				for(i=k;i<80;i+=delta){
					temp = M[4][i].num;
					if(i==k){
						try{
							Thread.sleep(20);
						}
						catch(Exception e){
						}
					}
					for(j=i;j>k && temp<M[4][j-delta].num;j-=delta){
						M[4][j].num = M[4][j-delta].num;
						//在这里画线
						try{
							drawOffScreen.clearRect(0,250,230,200);
							drawOffScreen.setColor(Color.red);
							drawOffScreen.fillRect(M[4][i].x-1,M[4][i].y-150,1,150);
							drawOffScreen.setColor(Color.blue);
							drawOffScreen.fillRect(M[4][j].x+1,M[4][j].y-150,1,150);
							drawLine(4);
							Thread.sleep(20);
						}
						catch(Exception e){
						}

					}
					M[4][j].num = temp;

				}//插入排序
			}
		}

		private void shellSort(){
			int delta;
			for(delta = M[4].length/3 ; delta>1 ; delta=1+delta/3)
				shellInsertion(delta);
			shellInsertion(1);
			notComplete = false;
		}
		public void run(){
			while(start && notComplete)
				shellSort();
		}
	}//Thread5

	class Thread6 extends Thread{
		boolean notComplete = true;
		private void HeapAdjust(int s,int m){
			//已知mark[s...m]中记录的关键字除mark[s]外均满足堆的定义
			//本函数调整mark[s]的关键字，是mark[s...m]成为一个大顶堆
			int temp;
			int j;
			temp = M[5][s-1].num;

			for(j=2*s;j<=m;j*=2){
				if(j<m && M[5][j-1].num<M[5][j].num)	j++;
				if(temp >= M[5][j-1].num)	break;
				M[5][s-1].num = M[5][j-1].num;
				s = j;
				//在这里画线
				try{
					drawOffScreen.clearRect(230,250,200,200);
					drawOffScreen.setColor(Color.red);
					drawOffScreen.fillRect(M[5][s].x-1,M[5][s].y-150,1,150);
					drawOffScreen.setColor(Color.blue);
					drawOffScreen.fillRect(M[5][j].x+1,M[5][j].y-150,1,150);
					drawLine(5);
					Thread.sleep(20);
				}
				catch(Exception e){
				}
			}
			M[5][s-1].num = temp;
		}

		private void HeapSort(){
			int i;
			int temp;
			for(i=M[5].length/2;i>0;i--)
				HeapAdjust(i,M[5].length);
			for(i=M[5].length;i>1;i--){
				temp = M[5][0].num;
				M[5][0].num = M[5][i-1].num;
				M[5][i-1].num = temp;
				HeapAdjust(1,i-1);
			}
			notComplete = false;
		}

		public void run(){
			while(start && notComplete){
				HeapSort();
			}
		}
	}//Thread6

	class Thread7 extends Thread{
		boolean notComplete = true;

		private void Merge(Material sr[],Material tr[],int i,int m,int n){
			//将sr[i...m]和sr[m+1...n]归并为tr[i...n];
			int j,k ;
			for(j=m+1,k=i;i<=m && j<=n;k++){//将sr中记录由小到大并入tr
				if(sr[i].num<sr[j].num) tr[k].num = sr[i++].num;
				else tr[k].num = sr[j++].num;
				//在这里画线
				try{
					drawOffScreen.clearRect(430,250,200,200);
					drawOffScreen.setColor(Color.red);
				//	drawOffScreen.fillRect(M[6][s].x-1,M[6][s].y-150,1,150);
					drawOffScreen.setColor(Color.blue);
				//	drawOffScreen.fillRect(M[6][t].x+1,M[6][t].y-150,1,150);
					drawLine(6);

					Thread.sleep(20);
				}
				catch(Exception e){
				}
			}
			if(i<=m)	while(i<=m)//将剩余的sr[i...m]复制到tr
							tr[k++].num = sr[i++].num;
			if(j<=n)	while(j<=n)//将剩余的sr[j...n]复制到tr
							tr[k++].num = sr[j++].num;
		}

		private void MergeSort(Material tr1[],int s,int t){
			//将mark[s...t]归并为tr1[s...t],因为mark是全局变量，
			//所以这里就不用参数传地址了
			int m;
			Material tr2[] = new Material[80];

			for(int i=0;i<80;i++)
				tr2[i] = new Material();
			if(s==t)	tr1[s].num=M[6][s].num;
			else{
				m=(s+t)/2;
				MergeSort(tr2,s,m);			//将M[s...m]归并为tr2[s...m]
				MergeSort(tr2,m+1,t);		//将M[m+1...t]归并为tr2[m+1...t]
				Merge(tr2,tr1,s,m,t);  //将tr2[s...m]和tr2[m+1...t]归并为有序的tr1[s...t]
				drawLine(6);
			}
			notComplete = false;
		}

		public void run(){
			while(start && notComplete){
				MergeSort(M[6],0,79);
				drawOffScreen.clearRect(430,250,200,200);
				drawLine(6);
			//	for(int i=0;i<80;i++)
			//	System.out.println(M[6][i].num);
			}
		}
	}//Thread7

}