排序算法-堆排序(Heap Sort)-蒲公英云

排序算法-堆排序(Heap Sort)

堆排序法介绍

堆排序是对简单选择排序法的改进算法，堆排序结合完全二叉树的性质，将序列和完全二叉树结合，每次比较都记录了比较结果，始终维护了每轮比较的最大值或者最小值。
在这里插入图片描述
上面两个完全二叉树分别是大顶堆和小顶堆，我们发现大顶堆的每个父结点都比子结点要大，而小顶堆的父结点比每个子结点都要小。

对于堆的定义是：完全二叉树的每个结点的值都要大于或等于其左右子结点的值，称为大顶堆；完全二叉树的每个结点的值都要小于或等于其左右子结点的值，称为小顶堆。

**完全二叉树的性质是堆排序的实现基础，完全二叉树的性质：
对一棵有n个结点的完全二叉树的结点按层编号
1.如果结点i=1，则结点i是根结点；如果i>1，则其父结点是⌊i/2⌋；

如果2i>n，则结点i无左孩子，i为叶子结点，否则2i是其左孩子结点；
如果2i+1>n，则结点i无右孩子结点，否则2i+1是其右孩子。**

堆排序的基本思想是：将待排序的序列构造成一个大(小)顶堆，堆顶的根就是序列的最大(小)值。将堆顶与末尾的结点交换位置，也就是将堆顶的值与序列的末尾元素交换，然后将堆顶到n-1的位置重新构造一个新堆(因为堆顶已经不是最大(小)的了)。反复执行，最终将序列排序完毕。

【构造堆】
下面举个堆构造过程例子：
假定我们有序列：{40,90,10,50,30,70,60,80,20}
在这里插入图片描述

可以看到标了颜色的结点都是有子结点的，也就是说，我们只需要调整这几个父结点就可以构造一个堆了。并且我们发现，⌊n/2⌋就是拥有子结点的父结点数。首先从倒数第二层最右的父结点开始，如图一。比较50小于80，替换位置。
堆构建顺序按照层序排序的倒序进行(从最底层，每层从右到左)，所以图二继续从10结点比较其子结点，10<70，替换位置。
如此反复执行，最终构建成堆。
在这里插入图片描述
最终堆构造完之后的序列如下：

【堆排序】
堆构造完毕之后，就是堆排序了，排序的过程就是堆顶与堆尾交换位置，并不断重新构造新堆的过程：

将堆顶的根结点和末尾结点交换位置，如图一。交换位置之后，将树根到n-1位置重新构成一个新的堆，使其堆顶保持为最大(小)值。接下来与此往复，最终将整个序列排序完毕。
在这里插入图片描述

算法

构造堆算法

public static void main(String[] args) { 
        Integer[] arr = new Integer[]{ 40,90,10,50,30,70,60,80,20};
        for (int i = arr.length/2; i > 0; i--) { 
            heapAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
    }
    /** * 堆调整 * * @param arr 待排序序列 * @param heapAdjustIdx 调整结点下标，注意此处是根据完全二叉树下标来，不是数组的下标。 * @param heapEndIdx 堆尾下标，注意此处是根据完全二叉树下标来，不是数组的下标。 1 ≤ heapEndIdx */
    public static void heapAdjust(Integer[] arr, int heapAdjustIdx, int heapEndIdx) { 
        //特别说明，由于数组下标从0开始，而完全二叉树编号从1开始，所以使用二叉树编号从数组中取值需-1。
        int temp = arr[heapAdjustIdx - 1];//暂存调整结点值
        for (int i = heapAdjustIdx * 2; i <= heapEndIdx; i = i * 2) { // 根据完全二叉树性质，结点i的左子节点为i*2
            //变量i为调整结点的左右子结点下标
            if (i < heapEndIdx && arr[i - 1] < arr[i]) {  //如果左子结点小于右子结点；i < endIdx防止数组越界
                i++;//左子结点+1变为右子结点下标
            }
            if (temp >= arr[i - 1]) { //如果当前调整结点不小于它的子结点，则不需要交换数据直接跳出循环
                break;
            }
            arr[heapAdjustIdx - 1] = arr[i - 1];//交换数据
            heapAdjustIdx = i; //将调整结点下标更改为的替换子结点下标，继续循环调整
        }
        arr[heapAdjustIdx - 1] = temp; //将原本暂存的结点值插入到最终位置
    }

排序算法

public static void main(String[] args) { 
        Integer[] arr = new Integer[]{ 40,90,10,50,30,70,60,80,20};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /** * 堆排序 * * @param arr 待排序列表 */
    public static void heapSort(Integer[] arr) { 
        for (int i = arr.length / 2; i > 0; i--) {  //此处除2是只需要调整有子结点的父结点
            //构造堆
            heapAdjust(arr, i, arr.length);
        }
        for (int i = arr.length; i > 1; i--) { 
            //交换堆顶结点和堆末尾的值
            Integer temp = arr[i - 1];
            arr[i - 1] = arr[0];
            arr[0] = temp;
            //重新调整根至n-1位置的二叉树使其维持堆的性质(堆顶最大)
            heapAdjust(arr, 1, i - 1);
        }
    }