堆排序

package al;

import java.util.Arrays;

/**
 * 堆排序.
 * 
 * @author chenlb 2008-12-28 下午03:52:53
 */
public class HeapSort {

	private static int parentIdx(int childIdx) {
		return (childIdx - 1) / 2; // 索引从0开始, 注意childIdx=0时返回0
	}

	private static int leftChildIdx(int parentIdx) {
		return parentIdx * 2 + 1;
	}

	/**
	 * 构建大顶堆.
	 * 
	 * @author chenlb 2008-12-28 下午03:52:23
	 */
	private static void buildMaxHeap(int[] datas) {
		int lastIdx = datas.length - 1;
		for (int i = parentIdx(lastIdx); i >= 0; i--) {
			int k = i;
			/* boolean isHeap = false; */
			/* 先比较左边的兄弟，如果不满足再比较父节点 */
			while (/* !isHeap && */leftChildIdx(k) <= lastIdx) {
				int j = leftChildIdx(k);
				if (j < lastIdx) { // 有两个孩子
					if (datas[j] <= datas[j + 1]) { // j+1 比较大, 选择大的
						j++;
					}
				}

				if (datas[k] > datas[j]) { // 父的比较大
					/* isHeap = true; */
					break;
				} else {
					SortUtil.swap(datas, k, j);
					k = j;
				}
			}
		}
	}

	/**
	 * 堆顶改变, 要维护大顶堆.
	 * 
	 * @author chenlb 2008-12-28 下午03:53:04
	 */
	private static void maintainMaxHeap(int[] datas, int lastIdx) {
		int k = 0;
		while (k <= parentIdx(lastIdx)) {
			int j = leftChildIdx(k);
			if (j < lastIdx) { // 有两个孩子
				if (datas[j] <= datas[j + 1]) { // j+1 比较大, 选择大的
					j++;
				}
			}
			if (datas[k] < datas[j]) { // 父结点比较小
				SortUtil.swap(datas, k, j);
				k = j;
			} else {
				break;
			}
		}
	}

	public static int[] sort(int[] datas) {
		buildMaxHeap(datas);
		int lastIdx = datas.length - 1;
		while (lastIdx > 0) {
			SortUtil.swap(datas, 0, lastIdx);
			lastIdx--;
			if (lastIdx > 0) {
				maintainMaxHeap(datas, lastIdx);
			}
		}
		return datas;
	}

	public static void main(String[] args) {
		int[] datas = { 5, 1, 3, 4, 9, 2, 7, 6, 5 };// {2, 9, 3, 7, 8, 6, 4, 5,
													// 0, 1};

		/*
		 * buildMaxHeap(datas); System.out.println(Arrays.toString(datas));
		 */

		sort(datas);
		System.out.println(Arrays.toString(datas));

		// datas = SortUtil.randomDates(10);
		// sort(datas);
		// System.out.println(Arrays.toString(datas));

	}

}