堆排序

import java.util.Collection;/** from 时 代 J a v a - nowjava.com**/

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Random;

import java.util.TreeMap;


public class Main{

    public static <T extends Comparable<T>> T[] heapSort(T array[]) {

        int heapSize = 0; // heapSize is important to know in determining when

                          // to the recursive calls

        for (int i = 0; i < array.length; i++) {/**来 自 nowjava - 时代Java**/

            if (array[i] == null)

                break;

            heapSize++;

        }

        buildMaxHeap(array, heapSize);


        for (int i = heapSize; i > 1; i--) {

            CollectionsHelper.swapValues(array, 0, heapSize - 1);

            heapSize--;

            maxHeapify(array, 0, heapSize);

        }


        return array;

    }

    private static <T extends Comparable<T>> void buildMaxHeap(T A[],

            int heapSize) {


        int nonLeaves = (A.length / 2) - 1;

        for (int i = nonLeaves; i >= 0; i--) {

            maxHeapify(A, i, heapSize);

        }

    }

    /**

     * Will swap the values between the given input index params

     * 

     * @param array

     * @param index

     * @param otherIndex

     * 

     */

    public static <T> void swapValues(T array[], int index, int otherIndex) {

        T tempVal = array[otherIndex];

        array[otherIndex] = array[index];

        array[index] = tempVal;

    }

    private static <T extends Comparable<T>> void maxHeapify(T array[],

            int index, int heapSize) {


        int leftIndex = getLeftChildIndex(index);

        int rightIndex = getRightChildIndex(index);

        int largestIndex = index;


        if (leftIndex < heapSize

                && array[index].compareTo(array[leftIndex]) == -1)

            largestIndex = leftIndex;


        if (rightIndex < heapSize

                && array[largestIndex].compareTo(array[rightIndex]) == -1)

            largestIndex = rightIndex;


        if (largestIndex != index) {