堆排序

public static void heapSort(int [] arr) {
    for(int i = 0; i < arr.length; i++) {
        // 每次建堆都能找出最大的一个元素，并将它与最后一个元素交换
        // 同时排除最后一个元素,这样就定位了一个元素的位置，以此类推
        maxHeap(arr, arr.length - i);
        swap(arr,0,arr.length - i - 1);
    }
}
// 从数组的最后一个元素开始构建
public static void maxHeap(int[] arr,int size) {
    // 从数组末尾开始构建(没有子节点的话也就不需要构建 所以这里从size/2开始构建)，直到第一个元素
    // 这样才保证构建出来的大根堆的根节点就是最大的
    for(int i = size / 2; i >= 0; i--) {
        buildHeap(arr, i, size);
    }
}


// 建堆
public static void buildHeap(int[] arr,int currendRootNode,int size) {
    if(currendRootNode < size) {
        // 左孩子
        int left=currendRootNode * 2 + 1;
        // 右孩子
        int right=currendRootNode * 2 + 2;

        // 将当前节点看成是最大的节点
        int max = currendRootNode;

        if(left < size) {
            // 如果左孩子比根元素要大，记录其位置
            if(arr[left] > arr[max]) {
                max = left;
            }
        }

        if(right < size) {
            // 如果右孩子比根元素要大，记录其位置
            if(arr[right] > arr[max]) {
                max = right;
            }
        }

        // 如果最大的不是根元素，那么就交换
        if(max!=currendRootNode) {
            swap(arr,max,currendRootNode);
            // 继续往下比较
            buildHeap(arr,max,size);
        }
    }
}

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