【排序】堆排序

/**
	 * 堆排序
	 * 
	 * @param a
	 * @param n
	 */
	public static void heapSort(int[] a, int n) {
		int i;
		int temp;
		for (i = n / 2; i >= 1; i--) { // 建立初始堆
			sift(a, i, n);
		}
		for (i = n; i >= 2; i--) {
			// 以下3句换出了根结点中元素，将其放入最终位置
			temp = a[1];
			a[1] = a[i];
			a[i] = temp;
			sift(a, 1, i - 1); // 在减少了1个元素的无序序列中进行调整
		}
	}

	/**
	 * 本函数完成对在数组a[low]到a[high]范围内在位置low上的结点进行调整
	 * 
	 * @param a
	 * @param low
	 * @param high
	 */
	public static void sift(int[] a, int low, int high) {
		int i = low;
		int j = 2 * i;
		int temp = a[i];
		while (j <= high) {
			if (j < high && a[j] < a[j + 1]) // 若右孩子较大，则把j指向右孩子
				j++; // j变为2*i+1

			if (temp < a[j]) {
				a[i] = a[j]; // 将a[j]调整到双亲结点的
				i = j; // 修改i和j的值，以便继续向下调整
				j = 2 * i;
			} else {
				break; // 调整结束
			}
		}
		a[i] = temp; // 被调整结点的值放入最终位置
	}