学步园

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的过程是：

1.        建立一个堆

2.        把堆首（最大值）和堆尾互换

3.        把堆的尺寸缩小1，目的是把新的数组顶端数据调整到相应位置

4.        重复步骤2，直到堆的尺寸为1

要知道构建堆，就必须了解二叉树的模型。如图：

构建大根堆步骤，如图：

第一步：首先我们发现，这个堆中有2个父节点(2,,3);

第二步：比较2这个父节点的两个孩子（4，5），发现5大。

第三步：然后将较大的右孩子（5）跟父节点（2）进行交换，至此3的左孩子堆构建完毕，

如图：

第四步：比较第二个父节点（3）下面的左右孩子（5，1），发现左孩子5大。

第五步：然后父节点（3）与左孩子（5）进行交换，注意，交换后，堆可能会遭到破坏，

必须按照以上的步骤一，步骤二，步骤三进行重新构造堆。

最后构造的堆如下:

第二：输出大根堆。

至此，我们把大根堆构造出来了，那怎么输出呢？我们做大根堆的目的就是要找出最大值，

那么我们将堆顶（5）与堆尾（2）进行交换，然后将（5）剔除根堆，由于堆顶现在是（2），

所以破坏了根堆，必须重新构造，构造完之后又会出现最大值，再次交换和剔除，最后也就是俺们

实现代码：

public class HeapSort {
	/***
	 * 构建堆
	 * @param array 待排序的集合
	 * @param parent 父节点索引
	 * @param length 输出根堆时剔除最大值使用
	 */
	public static void heapAdjust(int[] array, int parent, int length) {
		// temp保存当前父节点
		int temp = array[parent];

		// 得到左孩子
		int child = 2 * parent + 1;
		while (child < length) {
			// 如果parent有右孩子，则要判断左孩子是否小于右孩子
			if (child + 1 < length && array[child] < array[child + 1])
				child++;

			// 父亲节点大于子节点，就不用做交换
			if (temp >= array[child])
				break;

			// 将较大子节点的值赋给父亲节点
			array[parent] = array[child];

			// 然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
			parent = child;

			// 找到该父亲节点较小的左孩子节点
			child = 2 * parent + 1;
		}
		// 最后将temp值赋给较大的子节点，以形成两值交换
		array[parent] = temp;
	}

	//堆排序
	public static void heapSort(int[] array) {
		// list.length/2-1:就是堆中父节点的个数
		for (int i = array.length / 2 - 1; i >= 0; i--) {
			heapAdjust(array, i, array.length);
		}

		// 最后输出堆元素
		for (int i = array.length - 1; i > 0; i--) {
			// 堆顶与当前堆的第i个元素进行值对调
			int temp = array[0];
			array[0] = array[i];
			array[i] = temp;

			// 因为两值交换，可能破坏根堆，所以必须重新构造
			heapAdjust(array, 0, i);
		}
	}
	
	public static void main(String[] args) {
		System.out.println(5/2);
		int[] array = { 2, 5, 1, 8, 9, 3 };
		System.out.println("排序前：" + Arrays.toString(array));
		heapSort(array);
		System.out.println("排序后：" + Arrays.toString(array));

	}

}

运行结果：

排序前：[2, 5, 1, 8, 9, 3]

排序后：[1, 2, 3, 5, 8, 9]