heapsort.java

包括了5个基本排序过程

public class HeapSort //堆
{
	private double[] unsorted;
	private double[] sorted;
	public HeapSort()
	{
	}
	public HeapSort(double[] temp)
	{
		setdata(temp);
		init();
		sort();
	}
	public void setdata(double[] temp)
	{
		unsorted=new double[temp.length];
		sorted=new double[temp.length];
		for(int i=0;i<temp.length;i++)
			{
				sorted[i]=unsorted[i]=temp[i];
				//System.out.println(sorted[i]);
			}
	}
	public void init()//将unsorted初始化为最大堆
	{
		int currentSize=sorted.length-1;
		  for(int i=(currentSize-1)/2;i>=0;i--)
		  {
		   double y=sorted[i];//父节点
		   
		   int c=2*i+1;//小的子节点
		   while(c<=currentSize)
		   {
		    if(c<currentSize&&sorted[c]<sorted[c+1])c++;
		    if(y>=sorted[c])break;
		    
		    sorted[(c-1)/2]=sorted[c];
		    c=c*2+1;
		   }
		   sorted[(c-1)/2]=y;
		  }

	}
	public void sort()
	{
		for(int j=sorted.length-1;j>=0;j--)
		  {
		   //j相当于最后元素的下标
		   double tem=sorted[0];//最大元素
		   double y=sorted[j];//最后一个元素
		   int i=0,ci=1;//现在从树根开始 根当前接点为i=0;
		   while(ci<=j-1)
		   {
		    if(ci<j-1&&sorted[ci]<sorted[ci+1])ci++;
		    if(y>=sorted[ci])break;
		    sorted[i]=sorted[ci];
		    i=ci;
		    ci=ci*2+1;
		   }
		   sorted[i]=y;
		   
		   
		   sorted[j]=tem;
		  }

	}
	public double[] getresult()
	{
		return sorted;
	}

}