sort.java

1. 用二叉链表保存二叉树 2. 以基于二叉树的先序序列创建立二叉树 3. 按前序、中序、后序遍历二叉树（三选一）

import java.util.Scanner;
class Sort {
	public int r[];
	public final int NUM=8;
	public Sort(){
		r=new int[NUM];
		}
	
	public void Input(){
		Scanner scan=new Scanner(System.in);
		System.out.println("请输入"+NUM+"个整数：");
		for(int i=0;i<NUM;i++){
			r[i]=scan.nextInt();
		}
	}
	
	public void InputInsSort(){
		Scanner scan=new Scanner(System.in);
		r[0]=0;
		System.out.println("请输入"+(NUM-1)+"个整数：");
		for(int i=1;i<NUM;i++){
			r[i]=scan.nextInt();
		}
	}
	
	public boolean InsSort(int[] s){
		int j;
		for(int i=2;i<r.length;i++){
			s[0]=s[i];
			j=i-1;
			while(s[0]<s[j]&&j>0){
				s[j+1]=s[j];
				j--;
			}
			s[j+1]=s[0];			
		}
	return true;	
	}
	
	public boolean Merge(int s[],int low,int high)
	{
		int i=low;
		int mid=(low+high)/2;
		int j=mid+1;
		int k=low;
		int[] temp=new int[high+1];
		while((i<=mid)&&(j<=high))
		{
			if(s[i]<=s[j]){
				temp[k]=s[i];
				i++;
			}
			else{
				temp[k]=s[j];
				j++;
			}
			k++;
		}
		while(i<=mid){
			temp[k]=s[i];
			k++;
			i++;
		}
		while(j<=high){
			temp[k]=s[j];
			k++;
			j++;
		}
		for(int m=low;m<=high;m++){s[m]=temp[m];}
		return true;
	}
	
	
	public boolean MergeSort(int s[],int low,int high) //归并排序
	{		
		if(low<high){
			int mid=(low+high)/2;
			MergeSort(s,low,mid);
			MergeSort(s,mid+1,high);
			Merge(s,low,high);
			}
		return true;
	}
	
	public void sift(int[] s,int i,int m)   //比较大小
	{
		int j=2*i;
		int temp;
		while(j<=m){
			if(j<m&&s[j-1]>s[j])
			j++;
			if(s[i-1]>s[j-1]){
				temp=s[i-1];
				s[i-1]=s[j-1];
				s[j-1]=temp;
				i=j;
				j=2*i;
			}
			else break;			
		}
	}
	
	public boolean HeapSort(int[] s)  //堆排序
	{
		int i;
		int temp;
		for(i=NUM/2;i>=1;i--)
		sift(s,i,NUM);
		for(i=NUM;i>1;i--){
			temp=s[0];
			s[0]=s[i-1];
			s[i-1]=temp;
			sift(s,1,(i-1));
		}
	return true;	
	}
	
	public void displayInsSort(){
		for(int i=1;i<NUM;i++){
			System.out.println(r[i]);
		}
	}

    public void display(){
		for(int i=0;i<NUM;i++){
			System.out.println(r[i]);
		}
	}

}