堆排序 –java 实现

一. 堆排序

​ 堆排序 (Heap Sort) 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似齐全二叉树的构造，并同时满足沉积的性质：即子结点的键值或索引总是小于 (或者大于) 它的父节点。

二、堆

什么是堆？
堆是一个树形构造，其实堆的底层是一棵齐全二叉树。而齐全二叉树是一层一层依照进入的程序排成的。依照这个个性，咱们能够用数组来依照齐全二叉树实现堆。
大顶堆与小顶堆
大顶堆原理：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大顶堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。
小顶堆原理：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者，称为小顶堆。小堆堆要求根节点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值。

三、推排序思维

1. 构建初始堆，将待排序列形成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
2. 将堆顶元素与堆尾元素替换，并断开 (从待排序列中移除) 堆尾元素。
3. 从新构建堆。
4. 反复 2~3，直到待排序列中只剩下一个元素(堆顶元素)。

四、图解

五. 代码实现

public class HeapSort {public static void main(String[] args) {List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < 10; i++) {list.add((int) (Math.random() * 100));
        }
        System.out.println("排序前的汇合为：");
        System.out.println(Arrays.toString(list.toArray()));

        heapSort(list);

        System.out.println("排序后的汇合为：");
        System.out.println(Arrays.toString(list.toArray()));
    }

    /**
     * 创立堆，* @param list 待排序列
     */
    private static void heapSort(List<Integer> list) {
        // 创立堆
        for (int i = (list.size() - 1) / 2; i >= 0; i--) {
            // 从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(list, i, list.size());
        }

        System.out.println("dadui 的汇合为：");
        System.out.println(Arrays.toString(list.toArray()));

        // 调整堆构造 + 替换堆顶元素与开端元素
        for (int i = list.size() - 1; i > 0; i--) {
            // 将堆顶元素与开端元素进行替换
            int temp = list.get(i);
            list.set(i, list.get(0));
            list.set(0, temp);

            // 从新对堆进行调整
            adjustHeap(list, 0, i);
        }
    }

    /**
     * 调整堆
     * @param list 待排序列
     * @param parent 父节点
     * @param length 待排序列尾元素索引
     */
    private static void adjustHeap(List<Integer> list, int parent, int length) {
        // 将 temp 作为父节点
        int temp = list.get(parent);
        // 左孩子
        int lChild = 2 * parent + 1;

        while (lChild < length) {
            // 右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && list.get(lChild) < list.get(rChild)) {lChild++;}

            // 如果父结点的值曾经大于孩子结点的值，则间接完结
            if (temp >= list.get(lChild)) {break;}

            // 把孩子结点的值赋给父结点
            list.set(parent, list.get(lChild));

            // 选取孩子结点的左孩子结点, 持续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        list.set(parent, temp);
    }

}