[数据结构与算法]堆排序(java)

堆排序

• 1、把数组的每个数当作最后一个，按大根堆排序位置往前交换位置，然后此时的结构满足大根堆。
• 2、接着把大根堆堆顶和最后一个交换位置，交换完，对最后一个位置不作处理，它就是全场最大的。
• 3、但是此时第一个数是来自最后的位置，接着又需要继续往下排序交换，完成堆化操作。
• 4、如此往返，每次确定一个最大的放数组后面不动。

时间复杂度O(N*logN)
空间复杂度O(1)

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1,5,6,3,4,7};
        for (int i = 0; i < arr.length; i++) {//O(N)
            heapInsert(arr,i);//O(logN)
        }
        int heapSize=arr.length;
        //先把最大一个换到末尾，然后不动
        swap(arr,0,--heapSize);
        //每次下去换完就减1，直到size=0
        while (heapSize>0){//O(N)
            //从0到heapSize-1的位置上换，heapSize含义是到达不了的位置
            heapify(arr,0,heapSize);//O(logN)
            swap(arr,0,--heapSize);
        }
       
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void heapInsert(int[] arr,int i){
        while (arr[i]>arr[(i-1)/2]){
            swap(arr,i,(i-1)/2);
            i=(i-1)/2;
        }
    }
    
    //某个数在i位置，能否往下
    public static void heapify(int[] arr,int i,int heapSize){
        int leftChild = 2*i+1;//左孩子下标
        while (leftChild<heapSize){//下方还有孩子
            //比较哪个孩子大，如果有右孩子，且右孩子比左孩子大，把右孩子下标最为最大下标
            //如果没有右孩子，直接就是左孩子
            int largest= leftChild+1<heapSize && arr[leftChild+1]>arr[leftChild]
                    ?leftChild+1:leftChild;
            //父亲和孩子比较谁最大，赋值下标给largest
            largest = arr[largest]>arr[i]?largest:i;
            //如果父亲最大，那下面不用再比较了。
            if (largest==i){
                break;
            }
            //如果是孩子大，孩子和父亲交换
            swap(arr,largest,i);
            //父亲往下走
            i=largest;
            //左孩子也往下走
            leftChild = 2*i+1;
        }

    }


    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j]=temp;
    }
}