堆排序

        堆排序是利用堆的性质进行的一种选择排序。堆排序的平均时间复杂度是O(nlogn),最坏情况的时间复杂度O(nlogn)。堆排序也是一种不稳定的排序算法。

        堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]，即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆排序的基本思想:
        1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
        2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
        3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序的java实现，以int型数组为例：

public class HeapSort {
	/**
	 * 堆排序，调整无序序列，使其满足堆结构
	 * 
	 * @param array
	 * @param length
	 */
	public static void initHeap(int[] array, int length) {
		// p_node=length/2得到该树中非叶子节点数,p_node-1获得飞叶子节点的索引值
		for (int p_node = length / 2; p_node > 0; p_node--) {
			adjustHeap(array, p_node - 1, length);
		}
	}
	/**
	 * 调整每个父节点与其子节点的位置关系,把最小或者是最大的元素作为父节点
	 * 
	 * @param array
	 *            要排序的数组
	 * @param index
	 *            当前数组中的最后一个飞叶子节点的索引值
	 * @param length
	 *            无序序列的长度
	 */
	public static void adjustHeap(int[] array, int index, int length) {
		int max;
		// 判断父节点的孩子数
		if ((index + 1) * 2 <= length - 1) {// 有两个孩子时
			int left = array[2 * index + 1];
			int right = array[2 * index + 2];
			// 找出左右孩子中最大的
			if (left > right) {
				max = left;
				if (max > array[index]) {
					exchange(array, index, 2 * index + 1);
				}
			} else {
				max = right;
				if (max > array[index]) {
					exchange(array, index, 2 * index + 2);
				}
			}
		} else {// 只有左孩子
			int left = array[2 * index + 1];
			if (left > array[index]) {
				exchange(array, index, 2 * index + 1);
			}
		}
	}
	/**
	 * 交换数组中两个元素的值
	 * 
	 * @param array
	 *            要进行交换元素值的数组
	 * @param i
	 *            要进行交换的数组元素的索引
	 * @param j
	 *            要进行交换的数组元素的索引
	 */
	public static void exchange(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	public static void print(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ",");
			if (i == array.length - 1) {
				System.out.println();
			}
		}
	}

	/**
	 * 堆排序
	 * 
	 * @param array
	 */
	public static void heapSort(int[] array) {
		int length = array.length;
		while (length > 0) {
			initHeap(array, length);// 调整无序序列
			exchange(array, 0, length - 1);// 把整理好的序列的首尾值交换
			length--;// 无序序列长度减1
		}
	}