堆排序实现整理

代码整理：

 

使指定根节点的树最大化：

/**
	 * Make tree max.
	 * 
	 * @param array
	 *            - source array
	 * @param i
	 *            - root node index.
	 * @param length
	 *            - tree length.
	 */
	private static void maxHeapify(int[] array, int i, int length) {
		int left = i * 2;
		int right = i * 2 + 1;
		int largest;
		if (left < length && array[left] > array[i]) {
			largest = left;
		} else {
			largest = i;
		}

		if (right < length && array[right] > array[largest]) {
			largest = right;
		}

		if (largest != i) {
			swap(array, largest, i);
			maxHeapify(array, largest, length);
		}

	}
 /**
	 * Swap two elements in array.
	 * 
	 * @param array
	 *            - source array.
	 * @param j
	 * @param i
	 */
	private static void swap(int[] array, int j, int i) {
		int temp = array[j];
		array[j] = array[i];
		array[i] = temp;
	}

 构建最大树：

/**
	 * Build max heap tree.
	 * 
	 * @param array
	 *            - source array.
	 */
	private static void buildMaxHeap(int[] array) {
		int length = array.length;
		for (int index = length / 2 + 1; index >= 0; index--) {
			maxHeapify(array, index, length);
		}
	}

 

排序函数：(升序)

/**
	 * Heap sort in ASC.
	 * 
	 * @param array
	 *            - source array
	 */
	public static void heapSort(int[] array) {
		buildMaxHeap(array);
		int length = array.length;
		for (int index = length - 1; index > 0; index--) {
			swap(array, index, 0);
			length--;
			maxHeapify(array, 0, length);
		}
	}