排序算法（六 ）堆排序

1.算法思路
  堆排序（Heap-Sort）是一种基于二叉堆的排序算法。即将一个无序序列构成一个最大/最小堆，然后堆顶值与末尾值交换，交换完再做下沉操作再次构建成最大/最小堆，反复循环操作至末尾值指向堆顶结束，便能得到一个有序序列了。
升序：使用最大堆构建。
降序：使用最小堆构建。

说明：以降序为例

1.第一次循环，如“图1 循环-01”所示

图1 循环-01

2.第二次循环，如“图2 循环-02”所示

图2 循环-02

3.第三次循环，如“图3 循环-03”所示

图3 循环-03

...如此反复执行，直至指针指向堆顶，便形成有序序列。

2.复杂度

• 时间复杂度：O(nlogn)。
• 空间复杂度：T(1)。
• 稳定性：堆排序是不稳定算法。

3.代码实现

package Queue;

import java.util.Arrays;

public class HeapSort {

    private int[] array;

    public static void main(String[] args) {
        int[] arr01 = {5, 3, 6, 9, 8, 6, 7, 2, 4, 6, 3};
        HeapSort heapSort = new HeapSort();
        int[] arr = heapSort.sort(arr01);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 开始排序
     * @param array 要进行排序的数组
     * @return 已经排序好的数组
     */
    public int[] sort(int[] array) {
        // 初始化数组全局变量
        this.array = array;
        // 先构建最小堆
        buildHeap();
        // 依次循环置换堆顶堆尾数据并做下沉节点操作
        for (int i = array.length - 1; i > 0; i--) {
            // 先转换再下沉，顺序不可转换
            swap(i);
            downAdjust(0, i);
        }
        return this.array;
    }

    /**
     * 上浮操作
     * @param index 要上浮的数在数组中的下标
     */
//    private void upAdjust(int index) {
//        int childrenIndex = index;
//        int parentIndex = (childrenIndex - 1) / 2;
//        int temp = array[childrenIndex];
//        while (childrenIndex > 0 && temp < array[parentIndex]) {
//            array[childrenIndex] = array[parentIndex];
//            childrenIndex = parentIndex;
//            parentIndex = (parentIndex - 1) / 2;
//        }
//        array[childrenIndex] = temp;
//    }


    /**
     * 下沉节点
     * @param index 要下沉的节点的下标
     * @param length 当前堆的长度
     */
    private void downAdjust(int index, int length) {
        // 先记录父节点及左子节点的下标
        int parentIndex = index;
        int childrenIndex = parentIndex * 2 + 1;
        // 记录父节点的值，用于最后赋值
        int temp = array[parentIndex];
        // 若有左子节点则继续
        while (childrenIndex <= length) {
            // 若有右子节点，且右子节点比左子节点小，则将 childrenIndex 记录为右子节点的下标
            if ((childrenIndex + 1) <= length && array[childrenIndex + 1] < array[childrenIndex]) {
                childrenIndex++;
            }
            // 如果子节点大于父节点，则无需下沉，直接跳出循环
            //  注意：不可以直接 return
            if (array[childrenIndex] >= temp) {
                break;
            }
            // 直接单向赋值，无需做交替操作
            array[parentIndex] = array[childrenIndex];
            // 更新父子节点下标的值，下面两句代码顺序不可相反
            parentIndex = childrenIndex;
            childrenIndex = childrenIndex * 2 + 1;
        }
        // 最后赋值
        array[parentIndex] = temp;
    }

    /**
     * 堆顶堆尾交换
     * @param index 堆尾的下标
     */
    private void swap(int index) {
        int temp = array[0];
        array[0] = array[index];
        array[index] = temp;
    }

    /**
     * 构建最小堆
     */
    private void buildHeap() {
        for (int i = (array.length / 2) - 1; i >= 0; i--) {
            downAdjust(i, array.length - 1);
        }
    }
}