堆排序

明确一点：这里是使用二叉堆进行的排序，而二叉堆在内存中的表现形式是一个数组，但并不是所有的数组都是堆。堆排序也属于选择排序。

/**
 * 堆排序
 * 
 * 构造大堆 (找最大元素)
 * 让最大元素下沉 
 * 继续构建大堆 (每一次构造大堆都是为了找当前数组的最大值)
 * 重复以上步骤
 * 
 *
 */
public class HeapSort {

    public void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // 对无序数组第一次构建大堆
        buildMaxHeap(array);
        // 第一次大堆构建完成，则堆中的根节点就是当前数组的最大元素，即为数组中的第一个元素
        for (int lastIndex= array.length - 1; lastIndex >= 0; lastIndex--) {
            // 把最大的元素放到数组的最后，就是和最后一个元素交换位置
            swap(array, lastIndex, 0);
            // 得到了当前数组的最大元素，此时继续对数组中剩下的i个元素构建大堆
            buildMaxHeap(array, lastIndex, 0);
        }
        dispaly(array);
    }

    // 第一次创建大堆时使用
    private void buildMaxHeap(int[] array) {
        // halfIndex代表二叉堆的非叶子节点，如果非叶子节点存在左右子节点
        // 那么，左节点在数组中的下标位 2*i+1，右节点的为 2*i+2
        // 所以只需遍历数组的一半就可以得到数组的所有元素
        int halfIndex = (array.length - 1) / 2;
        // 由于构造大堆先从最后一个非叶子节点开始往前遍历比较好
        for (int parentIndex = halfIndex; parentIndex >= 0; parentIndex--) {
            buildMaxHeap(array, array.length, parentIndex);
        }
    }

    /**
     * @param length
     *          代表当前构造大堆的数组长度
     * @param parentIndex
     *          代表非叶子节点
     */
    private void buildMaxHeap(int[] array, int length, int parentIndex) {
        int lChildIndex = 2 * parentIndex + 1;
        int rChildIndex = 2 * parentIndex + 2;
        
        // 用当前的父节点和它的左右子节点比较找出最大的元素
        int largestIndex = parentIndex;
        
        // 比较左节点
        if (lChildIndex < length && array[largestIndex] < array[lChildIndex]) {
            largestIndex = lChildIndex;
        }
        
        // 比较右节点
        if (rChildIndex < length && array[largestIndex] < array[rChildIndex]) {
            largestIndex = rChildIndex;
        }

        // 如果最大的元素在左节点或右节点上，就把最大元素和父节点交换，然后继续进行大堆构造
        if(parentIndex != largestIndex) {
            // 交换位置，在堆中可看成父节点下沉
            swap(array, largestIndex, parentIndex);
            // 继续构造大堆，由于刚才的父节点就下沉了一次，所以它在数组中的索引位置即为largestIndex
            buildMaxHeap(array, length, largestIndex);
        }
        
    }
    
    // 元素交换
    private void swap(int[] array, int largestIndex, int parentIndex) {
        int temp = array[parentIndex];
        array[parentIndex] = array[largestIndex];
        array[largestIndex] = temp;
    }

    
    public void dispaly(int[] array) {
        for (int x : array) {
            System.out.print(x + " ");
        }
    }
    
    public static void main(String[] args) {
        int[] array = {1,3,4,3,8,3,2,6,7,4,9,10,0,-1,-7,4,2,9,7,20};
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(array);
        // -7 -1 0 1 2 2 3 3 3 4 4 4 6 7 7 8 9 9 10 20 
    }

}