（三）堆排序

佚名 5年前 (2019-05-14) 随笔 760人围观抢沙发百度已收录

思想：
每次构建一个最大堆，然后最大堆的顶为最大元素，然后将最大元素放置数组尾部。此为一个循环
然后将剩余的N-1个元素再次构建最大堆，...以此类推


public class Sort3 {
    public static void main(String[] args) {
        int[] array = {3, 1, 5, 7, 2, 4, 9, 6, 3};
        int length = array.length;
        maxHeapSort(array, length);
    }

    private static void maxHeapSort(int[] array, int length) {
        for(int i=0;i<length;i++){
            
            adjustHeap(array, length-i);

            int tmp = array[0];
            array[0]=array[length-i-1];
            array[length-i-1] = tmp;
        }

    }

    //  此为构建一个大顶堆的过程
    private static void adjustHeap(int[] array, int length) {
        // 先将最后一个子树（parentIndex=length/2-1）构建为大顶堆，然后依次往前推
        for (int i = length / 2 - 1; i >= 0; i--) {
            int parentIndex = i;
            int parent = array[parentIndex];
            int theOneIndex = parentIndex * 2 + 1;
            // 在子树已经是大顶堆的情况下，构建此树的大顶堆
            while (theOneIndex < length) {
                if (theOneIndex + 1 < length && array[theOneIndex] < array[theOneIndex + 1]) {
                    theOneIndex = theOneIndex + 1;
                }
                if (array[theOneIndex] > parent) {
                    array[parentIndex] = array[theOneIndex];
                    array[theOneIndex] = parent;

                    parentIndex = theOneIndex;
                    theOneIndex = 2 * parentIndex + 1;
                } else {
                    break;
                }
            }
        }
    }
}