[数据结构与算法]堆排序步骤详解+源码实现

堆排序步骤，升序排序构建大顶堆，降序排序构建小顶堆
二叉树以数组方式存储有以下特点
? ? 第 i 个节点的左子节点是 2*i+1
? ? ? ? ? ? ? ? 右子节点是 2*i+2
? ? 完全二叉树的最后一个 非叶子节点为 length / 2 - 1
第一步： 将无序数组调整为大顶堆结构
????????调整步骤为 从最后一个非叶子节点开始，构建大顶堆

????????注意： 如果是最后一个非叶子节点，我们只需要调整它为大顶堆结构即可。
?? ??? ?但是，如果是第 n-1个非叶子节点，就需要考虑，它大顶堆后，会影响第n个也就是后面已经是大顶堆的结构，
?? ??? ?我们需要遍历将后面进行微调

?? ??? ?当n个节点都进行大顶堆结构化之后进行第二步
第二步
?? ??? ?大顶堆后，最大的元素始终在第一个位置也就是数组下标为 0 的地方
?? ??? ?我们将最大的数和数组最后一个元素(length-1)进行交换，然后在进行第一步，对被打乱的大顶堆进行调整，这次
?? ??? ?我们就不用从最后一个非叶子节点来进行大顶堆化了，因为我们只改变了根节点，也就是说，我们只需要对第0个非叶子节点大顶堆化就行了。
?? ??? ?每次最大元素和尾部交换以后，下次就和length-2交换，然后大顶堆
?? ??? ?这里length是不断改变的，所以大顶堆的时候，length / 2-1那个最后的非叶子节点也是改变的，这里需要注意

?? ??? ?当调整到length > 0的时候，（length = 0时就剩一个根元素了，不需要调）就排序完成。
-------------------------------------------------------------------------------
?? ??? ?下面补充图解：
?? ??? ??? ?以 数据 dataset = [2, 6, 10, 5, 9, 4, 5] 进行图解步骤演示

?

public class HeapSort {
    /**
     * 构建大顶堆
     * @param dataset
     * @param i 倒数第 k 个非叶子节点
     * @param length
     */
    public static void adjust(int[] dataset,int i,int length){
        //当前节点的左子节点  是否存在左子节点  下一个节点
        for (int k = 2 * i+1; k+1<length;k = 2*i+1){
            // 选举出左右子节点 中较大的节点和当前节点比较
            // 如果存在右子节点，并且右子节点比左子节点大
            if (dataset[k] < dataset[k+1] && k+1<length){
                // 最大数的节点位置 右子节点比左子节点 大 1
                k = k+1;
            }
            // 如果选举出的节点比当前节点还大，就交换，否则两个子节点都没有当前节点大，
            // 就结束，说明该节点后的大顶堆没有再受影响
            if (dataset[k] > dataset[i]){
                // 当前节点和 最大节点交换
                int temp = dataset[i];
                dataset[i] = dataset[k];
                dataset[k] = temp;
                // 继续判断下一个节点
                i = k;
            }else {
                // 否则退出,这里因为后面的都是已经拍好的大顶堆了，没必要继续下去了
                break;
            }
        }
    }
    /*
    将所有大于当前节点的子节点往上移，直到下一个节点不大于，就把源节点放到当前节点。
     */
    public static void sort(int[] dataset){
        // 从最后一个非叶子节点将数组调整为大顶堆
        for (int i = dataset.length/2-1;i>=0;i--){
            adjust(dataset,i,dataset.length);
        }
        int temp = 0;
        for (int length = dataset.length-1;length > 0;length--){
            // 交换
            temp = dataset[0];
            dataset[0] = dataset[length];
            dataset[length] = temp;
            // 只对第 0 个非叶子节点进行大顶堆调整就行了
            adjust(dataset,0,length);
        }
        System.out.println(Arrays.toString(dataset));
    }
}

?