堆排序Java详细推演和实现-数据结构和算法-09-排序

 堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的 值，称为大顶堆；或者每个结点的值都小于或等于其左右孩 子结点的值，称为小顶堆）。

• 堆排序算法
   堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本 思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根 结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大 值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小 值。如此反复执行，便能得到一个有序序列了。

 我们所谓的将待排序的序列构建成为一个大顶堆，其实就是从下往上、从右到 左，将每个非终端结点（非叶结点）当作根结点，将其和其子树调整成大顶堆

数组：{5, 3, 4, 8, 1, 7, 9, 6, 2}

package com.my.data.structure;

import java.util.Arrays;


public class HeadSort {
        public static int[] arrayList = {5, 3, 4, 8, 1, 7, 9, 6, 2};

    
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    
    public static void headSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            headAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));

        
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr,0,j);
            headAdjust(arr, 0, j);
            //System.out.println(Arrays.toString(arr));
        }
        System.out.println(Arrays.toString(arr));
    }

    
    private static void headAdjust(int[] arr, int i, int length) {
        int temp = arr[i];

        //j为什么是j = 2 * i + 1，i的左子结点
        //j递增为什么是j = j * 2 + 1，这棵树是完全二叉树，当前结点的下标是j,那么
        //  它的左结点一定是j * 2 + 1，右结点一定是j * 2 + 2
        for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
            //i结点的左结点和右结点比较大小
            if (j + 1 < length && arr[j] < arr[j + 1])
                //如果右结点值大于左节点记录下标
                //为啥？因为如果下面代码成立，则需要作为双亲结点，向下筛选
                j++;
            if (arr[j] > temp) {
                arr[i] = arr[j];
                //需要该结点再向下筛选，需要满足每个结点的值都大于或等于其左右孩子结点的值
                i = j;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    public static void main(String[] args) {
        headSort(arrayList);
    }


}

• 运行结果

[9, 8, 7, 6, 1, 5, 4, 3, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9]