HeapSort

what

sorting using the features of MaxHeap or MinHeap(from which you can get the max or min value from the root node of the heap)

排序过程process of the sorting

1. 首先构建最大（小）堆，
2. 堆首和堆尾互换
3. 堆的尺寸缩小1， 调到用shift_down(0), 把新的数组顶端数据调整到响应的位置。
4. 重复2，直到堆尺寸为1.

   /**
        * 堆排序，先构造一个大顶堆或者小顶堆，利用构造堆，每次找到当前子数组中最大或者最小的值，完成排序
        *
        * */
       public int[] sort(int[] sourceArray) {
   
           int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
   
           int len = arr.length;
   
           buildMaxHeap(arr, len);
           System.out.println(Arrays.toString(arr));
           for (int i = len - 1; i > 0; i--) {
               swap(arr, 0, i);
               len--;
   //            System.out.println(Arrays.toString(arr));
               heapify(arr, 0, len);
           }
           return arr;
       }

构建堆原理与方法

利用堆的特性，数组中元素下标i，可以找到它的左右子节点的下标为i * 2 + 1 和 i * 2 + 2。
从数组的中间索引开始，递减的顺序，计算找到左右子节点的位置，然后对比节点大小，转换成符合条件的状态（大顶堆，就让左右节点中最大的值替换为当前节点，小顶堆相反）。如果发生了替换，就递归向下将替换下去的这个节点再对比左右节点做这个堆化的操作。 因为这个堆化的过程顺序是从初始数组的中间索引开始的，也就是其左右子树已经是最底层的叶子节点。所以按照这个顺序来堆化，就保证了整棵树可以完全的堆化成符合条件（大顶堆，左右子节点小于当前节点，小顶堆相反）的样子。

/**
     * 方法名： 构建最大堆
     * 功能： 从中间节点开始扫描，这样就可以保证数组中所有的元素都参与判断了一遍，而且是从堆的最底部开始判断
     * */
private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
}

/**
     *  方法名： 堆化
     *  功能： 将当前节点作为根节点进行堆化，不断的递归进行， 将当前
     * */
private void heapify(int[] arr, int i, int len) {

//        System.out.println(Arrays.toString(arr) + " 进入堆化" );
//      寻找当前节点的左右子节点，因为是最大堆，所以要让当前节点i的值最大
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
//        System.out.println("当前节点为 " + arr[i]);
//        if (left < arr.length && right < arr.length) {
//            System.out.println("当前节点左节点为 " + arr[left]);
//            System.out.println("当前节点右节点为 " + arr[right]);
//        }
//        判断如果左右节点如果比当前节点值大，就交换
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }
//       如果发生了交换，那么将该节点的交换过的这个节点在进行堆化，递归的进行下去
        if (largest != i) {
//            if (largest == left) {
//                System.out.println(Arrays.toString(arr) + " 交换了左节点");
//            } else {
//                System.out.println(Arrays.toString(arr) + " 交换了右节点");
//            }
            swap(arr, i, largest);

            heapify(arr, largest, len);
        }
//        System.out.println(Arrays.toString(arr) + " 完成堆化");
    }