堆排序算法

堆排序属于不稳定排序，时间复杂度O(nlogn)

    
    public static void heapSort(int[] arr) {
        if (arr == null) return;
        // 构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            // 交换堆顶元素与末尾元素
            swap(arr, 0, i);
            // 调整堆
            adjustHeap(arr, 0, i);
        }

    }

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

    
    private static void adjustHeap(int[] arr, int i, int length) {
        // 取出当前元素
        int temp = arr[i];
        // 从左结节点开始遍历
        for (int l = 2 * i + 1; l < length; l = 2 * l + 1) {
            // 左子结点小于右子结点指向右子结点
            if (l + 1 < length && arr[l] < arr[l + 1]) {
                l++;
            }

            // 大于根结点,将结点值赋值给根结点
            if (arr[l] > temp) {
                arr[i] = arr[l];
                i = l;
            } else {
                break;
            }
        }
        // 将temp值放到最终的位置
        arr[i] = temp;
    }