堆排序

什么是堆排序?
就是通过不断取出最大堆的堆顶元素。取完之后剩下的数据排序满足最大堆之后再次取堆顶元素，重复以上操作最终实现一个又大到小的排序。

我们以数组 int[] arr = {50, 23,22,1,70,24,34,45}为例：
首先我们要让数组满足我们的最大二叉堆的性质，也就是所有的父亲节点都大于等于其子节点。我们通过Heapify来实现，也就是找到最后一个元素的父亲节点，然后从倒数第一个元素的父亲节点递减的执行siftDown操作，完成二叉堆。
siftDown：就是不断和自己的子孩子进行比较，直到大于等于自己的最大子孩子。

第一轮siftDown之后，以上数组变成 {70,50,34,45,23,24,22,1},然后我们让角标0和角标arr.leng-1进行交换，变成了{1,50,34,45,23,24,22,70}

第二轮执行siftDown之后，{50,45,34,1,23,24,22,70},我们让角标0和角标arr.leng-2进行交换。变成了{22,45,34,1,23,24,50,70}

第三轮执行siftDown之后，{45,23,34,1,22,22,50,70},然后我们让角标0和角标arr.leng-3 进行交换，变成了{24,23,34,1,22,45,50,70}

第四轮执行siftDown之后，.......变成了{22,23,24,1,34,45,50,70}
第五轮执行siftDown之后，.......变成了{22,23,1,24,34,45,50,70}
第六轮执行siftDown之后，.......变成了{22,1,23,24,34,45,50,70}
第七轮执行siftDown之后，.......变成了{1,22,23,24,34,45,50,70}

八个元素执行了七轮循环 也就是arr.leng-1次循环

代码实现如下

    public static  void heapSort(int[] arr) {

        for (int i = 0; i < arr.length-1; i++) {
            //从最后一个角标的父亲节点开始重复向上执行，siftDown的操作。
            // 由于每次执行完之后最大值在最后一个角标，所以我们要获取 arr.length-i-1的父亲节点
            for (int j = getParent(arr.length - 1-i); j >= 0; j--) {
                siftDown(arr, j, arr.length - i);
            }
            //执行完下浮操作之后，交换角标0 和arr.length-i-1角标交换。
            int temp = arr[0];
            arr[0] = arr[arr.length-i-1];
            arr[arr.length-i-1] = temp;
        }


    }

    /**、
     * 获取index的左孩子角标
     * @param index
     * @return
     */
    private static int getLeftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取index的父亲角标
     * @param index
     * @return
     */
    private static int getParent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("zero no parent ");
        }
        return (index - 1) / 2;
    }

    /**
     * 获取index的又孩子角标
     * @param index
     * @return
     */
    private static int getRightChild(int index) {
        return index * 2 + 2;
    }

    /**
     *
     * @param array 需要排序的数组
     * @param k endIndex的父亲节点，
     * @param endIndex
     */
    private static void siftDown(int[] array, int k, int endIndex) {

        //如果k角标的左孩子角标没有超过endindex,就继续执行
        while (getLeftChild(k) < endIndex) {
            
            //获取最孩子的角标
            int j = getLeftChild(k);
            //如果j+1<endIndex，表示k有右孩子，如果右孩子大于左孩子，我们要把较大的元素的角标赋值给j
            if (j + 1 < endIndex && array[j + 1]-(array[j]) > 0) {
                j = getRightChild(k);

            }
            //如果角标k的元素大于孩子中最大的值，循环结束，如果小于最大值，则k和j角标交换元素,然后吧j赋值给k,执行下次循环
            if (array[k]-(array[j]) >= 0) {
                break;
            }
            int temp = array[k];
            array[k] = array[j];
            array[j] = temp;
            k = j;
        }
    }