Java排序算法之 —— 堆排序

package algorithm.sort;

/**
 * 堆排序算法：首先建立最大堆，因为最大元素在根A[0]，所以将其与最后一个元素交换
 * 然后去除最后一个节点，重新调整最大堆，循环此过程
 * @author Administrator
 *
 */
public class HeapSort {
	
	//堆排序
	public void heapSort(int[] a) {
		int heapSize =  a.length;
		//建立最大堆
		buildMaxHeap(a, heapSize);
		//从最后一个元素开始循环
		for (int i = a.length-1; i > 0; i--) {
			//交换最大元素与最后一个元素
			exchange(a, i, 0);
			//重新调整根节点为最大堆
			keepMaxHeapify(a, 0, --heapSize);
		}
		
	}
	
	//给定一个数组，建立最大堆
	public void buildMaxHeap(int[] a, int heapSize) {
		//对数中每一个不是叶节点的节点调用
		for (int i = heapSize/2; i>=0; i--) {
			keepMaxHeapify(a, i, heapSize);
//			keepMaxHeapifyNoRecurisive(a, i, heapSize);
		}
	}
	
	//保持最大堆性质，使以i为根的子树为最大堆（采用递归方法）
	public void keepMaxHeapify(int[] a, int i, int heapSize) {
		int left = left(i);
		int right = right(i);
		
		int largest = i;
		if (left < heapSize && a[left] > a[i]) {
			largest = left;
		}		
		if (right < heapSize && a[right] > a[largest]) {
			largest = right;
		}
		
		if (largest != i) {
			exchange(a, largest, i);
			keepMaxHeapify(a, largest, heapSize);
		}
	}
	
	//非递归方法保持最大堆性质
	public void keepMaxHeapifyNoRecurisive(int[] a, int i, int heapSize) {		
		int largest = i;
		
		while (largest < heapSize) {
			int left = left(i);
			int right = right(i);
			if (left < heapSize && a[left] > a[i]) {
				largest = left;
			}			
			if (right < heapSize && a[right] > a[largest]) {
				largest = right;
			}
			
			if (largest == i) break;
			exchange(a, largest, i);
			i = largest;
		}
	}
	//父节点（考虑java中下标从0开始）
	public int parent(int i) {
//		return (i-1) / 2;
		return (i-1) >> 1;	//二进制计算法
	}
	
	//左孩子
	public int left(int i) {
//		return i * 2 + 1;
		return (i << 1)+1;
	}
	
	//右孩子
	public int right(int i) {
//		return (i + 1) * 2;
		return (i + 1) << 1;
	}
	
	//交换元素
	public void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	//打印数组
	public void printArr(String str, int[] a) {
		System.out.print(str + "\t");
		for(int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	
	//测试数组
	public static void main(String[] args) {
		int[] a = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

		HeapSort hs = new HeapSort();
		
		hs.printArr("原始数组为：", a);
		hs.buildMaxHeap(a, a.length);
		hs.printArr("建立最大堆为：", a);
		hs.heapSort(a);
		hs.printArr("堆排序后为：", a);

	}

}

//output~
原始数组为： 4 1 3 2 16 9 10 14 8 7
建立最大堆为： 16 14 10 8 7 9 3 2 4 1
堆排序后为： 1 2 3 4 7 8 9 10 14 16