算法描述：对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩下一个元素时为止。

package sorting;

/**

 * 堆排序

 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(1);不稳定;较复杂

 * @author zeng

 *

 */

public class HeapSort {

	public static void heapSort(int[] a) {

		int i;

		int len = a.length;

		// 构建堆

		for (i = len / 2 - 1; i >= 0; i--)

			heapAdjust(a, i, len - 1);

		//交换堆顶元素与最后一个元素的位置

		for (i = len - 1; i > 0; i--) {

			int tmp = a[0];

			a[0] = a[i];

			a[i] = tmp;

			heapAdjust(a, 0, i - 1);

		}

	}

	public static void heapAdjust(int[] a, int pos, int len) {

		int child = 2 * pos + 1;

		int tmp = a[pos];

		while (child <= len) {

			if (child < len && a[child] < a[child + 1])

				child++;

			if (a[child] > tmp) {

				a[pos] = a[child];

				pos = child;

				child = 2 * pos + 1;

			} else

				break;

		}

		a[pos] = tmp;

	}

	public static void main(String[] args) {

		int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };

		heapSort(a);

		for (int i : a)

			System.out.print(i + " ");

	}

}