heapsort.java

来自「这是Java的模式编程」· Java 代码 · 共 47 行

package Strategy;

import java.lang.Comparable;

public class HeapSort extends SortStrategy
{
	private static int leftChild(int i)
	{
		return 2*i + 1;
	}
	private static void percDown(Comparable [] a,int i,int n)
	{
		int child;
		Comparable tmp;
		for(tmp = a[i];leftChild(i) < n;i = child)
		{
			child = leftChild(i);
			if(child != n-1 && a[child].compareTo(a[child + 1]) < 0)
			child ++;
			if(tmp.compareTo(a[child]) < 0)
			a[i] = a[child];
			else
			   break;
		}
		a[i] = tmp;
	}
	public void sort(Comparable [] a)
	{
		for(int i = a.length/2; i >= 0;i --)
			percDown(a,i,a.length);
		for(int i = a.length - 1;i > 0;i --)
		{
			swapReferences(a,0,i);
			percDown(a,0,i);
		}
		printInfor("HeapSort");
	    printArray(a);
	    	
	}
	private static void swapReferences(Comparable [] a,int m,int n)
	{
		Comparable tmp;
		tmp = a[m];
		a[m] = a[n];
		a[n] = tmp;
	}
}