堆排序

时间复杂度O(nlogn)
空间复杂度O(1)

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[800];
        for (int i = 0; i < 800; i++) {
            arr[i] = (int) (Math.random() * 800); // 生成一个[0, 8000000) 数
        }
        heapSort(arr);
    }

    public static void heapSort(int arr[]) {
        int temp = 0;
        int len = arr.length;
        while(len!=1){
            //每次构造大根堆
            for(int i = len/ 2 -1; i >=0; i--) {
                adjustHeap(arr, i, len);
            }
            //把堆的长度减一，把最大值和最后一个值交换
            len--;
            temp = arr[len];
            arr[len] = arr[0];
            arr[0] = temp;
        }
    }
    //调整堆为大根堆
    public  static void adjustHeap(int arr[], int i, int lenght) {
        int temp = arr[i];
        int k = i * 2 + 1;
        if(k+1 < lenght && arr[k] < arr[k+1]) { 
            k++; 
        }
        if(arr[k] > temp) { 
            arr[i] = arr[k]; 
            arr[k] = temp; 
        } 
    }
}