heapsortimp.java

用JAVA实现排序等简单算法的演示

package algorithmImp;

public class HeapSortImp extends SortAlgorithmImp {

	/**
	 * 按照堆排序算法对数组 data 进行排序
	 */
	public void sorting() {
		createHeap(data.length);			// 先建堆
		for (int index = data.length-1; index >= 0; index--) {
			//	堆中的第一个元素即根元素是未排序元素中的最大元素，将其交换到 index 处
			swap(0, index);
			// 对未排序的元素(从 0 到 index-1）进行堆调整，以找出最大元素放在 data[0]
			adjust(0, index);
		}
		
	}

	/**
	 * 对从 rootIndex 处开始，长为 length 的数组进行堆调整，使得将该数组看作二叉树时，任意子树的根
	 * 节点的整数数值都大于它的两个儿子节点的整数数值
	 * @param rootIndex 子树的根
	 * @param length 数组长度
	 */
	protected void adjust(int rootIndex, int length) {
		// 从根节点开始调整
		select(rootIndex);		
		// 根节点的儿子是 2 * rootIndex + 1 和 2 * rootIndex + 2 ，因为Java语言的数组下标从 0 开始
		// 显然下标为0的元素的儿子是 1 和 2，依次类推，节点 i 的儿子是 2 *i + 1 和 2 * i + 2
		int childIndex = 2 * rootIndex + 1;		
		while (childIndex < length) {
			// 找出两个儿子节点中整数数值大的那个儿子节点
			if (childIndex < length-1 && compare(childIndex+1, childIndex)) childIndex = childIndex + 1;
			// 将当前待调整（即决定要放在何处）的节点与儿子节点(childIndex)比较
			if (compareSelectedWith(childIndex)) {
				// 如果当前待调整节点已经大于儿子节点，则将待调整节点放在当前节点处，即childIndex 的
				// 父亲节点，它在 (childIndex-1)/2 处
				if (getSelectedIndex() != (childIndex-1)/2) placeSelectedData((childIndex-1)/2);
				return;
			}
			// 当前待调整节点小于儿子节点，将儿子节点上移，待调整节点继续与下层节点进行比较
			moveElement(childIndex, (childIndex-1)/2);
			// childIndex 走向儿子节点，以便与待调整节点比较
			childIndex = 2 * childIndex + 1;
		}
		// 当 childIndex >= length 时，已经无儿子节点可比较，因此直接放在当前节点处，当前节点仍由
		// (childIndex-1)/2 计算出来。
		if (getSelectedIndex() != (childIndex-1)/2) placeSelectedData((childIndex-1)/2);
	}
	
	protected void createHeap(int length) {
		// 将长度为 length 的数组建堆只要以 (length-1)/2 开始不断调整即可。
		// 从 (length-1)/2 开始，是因为只有从这一节点开始才有儿子节点
		for (int index = (length-1)/2; index >= 0; index--) adjust(index, length);
	}
}