sort.java

1. 实现插入排序； 2. 实现归并排序； 3. 实现堆排序

1.    实现插入排序；

2.    实现归并排序； 

3.    实现堆排序，包括建堆过程；（三种排序在一个程序中实现） 

//    Sort.java
public class Sort {
 public int a[]=new int[]{9,5,6,10,7,3,8,1};
 public int b[]=new int[]{9,5,6,10,7,3,8,1};
 public int c[]=new int[]{9,5,6,10,7,3,8,1}; 

 public void sort(int[] data) {    //插入排序
     for(int i=data.length/2; i>2; i/=2){
        for(int j=0; j<i; j++){
           insertSort(data,j,i); 
        }
     }
     insertSort(data,0,1); 
 }
 private void insertSort(int[] data, int start, int inc) {
     int temp; 
     for(int i=start+inc; i<data.length; i+=inc){
        for(int j=i; (j>=inc)&&(data[j]<data[j-inc]); j-=inc){
           temp=data[j]; 
           data[j]=data[j-inc];
           data[j-inc]=temp; 
        }
     }
 }
   public void mergeSort(int a[],int low,int high){     //归并排序
    if(low<high){
     int mid=(low+high)/2;
     mergeSort(a,low,mid);
     mergeSort(a,mid+1,high);
     Merge(a,low,high);
    }
   }
  public int[] Merge(int r[],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(r[i]<=r[j]){
      temp[k]=r[i];
      ++i;
     }
     else{
      temp[k]=r[j];
     ++j;
     }
     ++k;
    }
    while(i<=mid){
     temp[k]=r[i];
     k++;
     i++;
    }
    while(j<=high){
     temp[k]=r[j];
     k++;
     j++;
    }
    for(int n=low;n<=high;n++)
     r[n]=temp[n];
    return r;
   }
 public void sift(int r[], int i,int m){ 
  int temp;
  int j;
  j=2*i;
  while(j<=m){
   if(j<m&&r[j]<r[j+1])
    j++;
   if(r[i]<r[j]){
   temp=r[i];
   r[i]=r[j];
   r[j]=temp;
   i=j;
   j=2*i; 
   }
   else
    break;
  }
 }
 public void HeapSort(int[] r){     //堆排序
  int i;
  int temp;
  for(i=r.length/2;i>=0;i--)
   sift(r,i,r.length-1);
  temp=r[0];
  r[0]=r[r.length-1];
  r[r.length-1]=temp; 

  for(int last=r.length-2;last>0;last--){
   sift(r,0,last);
    temp=r[0];
    r[0]=r[last];
    r[last]=temp;  
  }
 }
}