最大堆排序

package com.lilei.geotools.app_geotools;

import java.util.Random;


public class MaxHeapSort {

	public static void main(String[] args) {

		int[] array = new int[10000000];
		for (int i = 0; i < array.length; i++)
			array[i] = new Random().nextInt(1000);
		
		long start = System.currentTimeMillis();

		sort(array);
		System.out.println(System.currentTimeMillis()-start);

	}

	public static void sort(int[] array) {

		// 首次构建最大堆
		for(int i=0;i<array.length;i++)
		firstHeap(array, i);

		for (int i = array.length - 1; i > 0; i--) {
			swap(array, 0, i);
			secondHeapSort(array, 0, i-1);
		}

	}

	static void secondHeapSort(int[] array, int p, int end) {
		if (p > end)
			return;

		int left = p * 2 + 1;
		int right = left + 1;

		if (right <= end) {
			
			if (array[p] < array[left] || array[p] < array[right]){
				if (array[left] > array[right]){
					swap(array, p, left);
					secondHeapSort(array, left, end);
				}else{
					swap(array, p, right);
					secondHeapSort(array, right, end);
				}
			}
			
			
		} else if (left <= end) {
			if (array[p] < array[left]) {
				swap(array, p, left);
				secondHeapSort(array, left, end);
			}
		}
	}

	static void firstHeap(int[] array, int p) {

		if (p >= array.length)
			return;

		int left = p * 2 + 1;
		int right = left + 1;
		firstHeap(array, left);
		firstHeap(array, right);

		int s = left;

		if (right < array.length) {

			if ((array[p] < array[left] || array[p] < array[right])) {
				if (array[left] < array[right])
					s = right;

				swap(array, s, p);
			}
		} else if (left < array.length) {
			if (array[s] > array[p])
				swap(array, s, p);

		}
	}

	static void swap(int[] array, int s, int p) {
		int tmp = array[p];
		array[p] = array[s];
		array[s] = tmp;
	}

}