[数据结构与算法]java实现堆排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {27,15,19,18,28,34,65,49,25,37};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void createBigHeap(int[] arr) {
        for (int i = (arr.length-1-1)/2; i >= 0 ; i--) {
            adjustDown(arr,i,arr.length);
        }
    }

    public static void adjustDown(int[] arr,int parent,int len) {
        int child = 2 * parent + 1;
        if (child + 1 < len && arr[child] < arr[child + 1]) {
            child++;
        }
        while (child < len) {
            if (arr[child] > arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    //时间复杂度(不管最好还是最坏)：O(n * log2(n))
    //空间复杂度：O(1)
    public static void heapSort(int[] arr) {
        createBigHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            adjustDown(arr,0,end);
            end--;
        }
    }
}