算法导论---堆排序Java代码实现

package Search;

//堆排序算法实现

public class HeapSort1 {

public static void main(String[] args) {

	int arr[] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };

	HeapSort1 hs1 = new HeapSort1();
	
	hs1.HeapSort(arr,arr.length);
	hs1.Print(arr);
}


//节点i的父亲节点是i/2
public int Parent(int i) {
	return i / 2;
}

//节点i的左孩子2i
public int Left(int i) {
	return 2 * i;
}

//节点i的右孩子2i+1
public int Right(int i) {
	return 2 * i + 1;
}


//维护堆的性质，使之永远保持是一个最大堆
public void MaxHeapify(int arr[], int i,int heapsize) {
	int largest = 0;//记录最大的节点，使之放在根节点
	int l = Left(i);
	int r = Right(i);
	if (l <= heapsize-1 && arr[l] > arr[i]) {
		largest = l;
	} else
		largest = i;
	if (r <= heapsize-1 && arr[r] > arr[largest]) {
		largest = r;
	}
	if (largest != i) {
		int temp = arr[i];
		arr[i] = arr[largest];
		arr[largest] = temp;
		MaxHeapify(arr,largest,heapsize);
	}

}


//维护堆的性质，使之永远保持是一个最小堆
           

// public void MinHeapify(int arr[], int i,int heapsize) {

// int smallestest = 0;//记录最小的节点，使之放在根节点

// int l = Left(i);

// int r = Right(i);

// if (l <= heapsize-1 && arr[l] <arr[i]) {

// smallestest = l;

// } else

// smallestest = i;

// if (r <= heapsize-1 && arr[r] < arr[smallestest]) {

// smallestest = r;

// }

// if (smallestest != i) {

// int temp = arr[i];

// arr[i] = arr[smallestest];

// arr[smallestest] = temp;

// MaxHeapify(arr,smallestest,heapsize);

// //MinHeapify(arr,smallestest,heapsize);

// }

//

// }

//建队

public void BuildMaxHeap(int arr[],int heapsize) {

for (int i =(arr.length-1 )/ 2 ; i >= 0; i–) {

MaxHeapify(arr,i,heapsize);

//MinHeapify(arr,i,heapsize);

}

}

//排序算法
public void HeapSort(int arr[], int heapsize) {
	BuildMaxHeap(arr,heapsize);
	for (int i = arr.length-1; i > 0; i--) {
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		heapsize = heapsize - 1;
		MaxHeapify(arr,0,heapsize);
		//MinHeapify(arr,0,heapsize);
	}

}


//打印
public void Print(int arr[]) {
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i]+" ");
	}
}
           

}