heap-sort

堆排序

1.堆排序是利用堆这种数据结构而设计的一种算法，堆排序是一种选择排序，它的最坏，最好，平均复杂度均为O(nlogn)，它也是不稳定的排序。

2.堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。没有要求结点的左孩子的值和右孩子的值大小关系。

3.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

package sort;

import java.util.Arrays;

/**
 * @Author: Wizard
 * @Date: 2020/5/18 21:16
 */
public class heapSort {
    public static void main(String[] args) {
        //要求将数组进行升序排列
    }

    //编写一个堆排序的方法
    public static void heapSort(int arr[]) {
        int temp = 0;
        System.out.println("堆排序！");


        //  i  第一个非叶子结点
        //  这里的目的是把最大的数交换到堆顶，成为一个大顶堆结构
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
            System.out.println(Arrays.toString(arr));
        }


        /*
        将堆顶元素于末尾元素交换，将最大元素“沉”到数组末端
        重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
         */
        //一共5个数，调整4个数就可以了
        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];//arr[0] 是上面调整后的最大值
            arr[0] = temp;
            adjustHeap(arr, 0, j);
            System.out.println("第"+(arr.length-j)+"次沉"+Arrays.toString(arr));
        }
        System.out.println(Arrays.toString(arr));


        //每次遍历把最大的数（在调整之后的父节点，第一位）沉到数组的末端
        //然后 再调整 把最大的数交换到堆顶（adjustHeap），再沉到数组的末端的位置-1，随着j的递减，末尾的前几个数字逐渐确定（调整的范围减少）

    }


    //将一个数组(二叉树),调整为一个大顶堆

    /**
     * 功能：完成将以 i 对应的非叶子结点的树调整为大顶堆
     * int arr[] = {4,6,8,5,9};   → i = 1 → adjustHeap → 得到{4,9,8,5,6}
     * 再次调用adjustHeap 传入的是 i= 0 → 得到{9,6,8,5,4}
     *
     * @param arr    待调整的数组
     * @param i      表示非叶子结点在数组中的索引
     * @param lenght 表示归多少个元素继续调整，length 是在逐渐的减少
     */
    public static void adjustHeap(int arr[], int i, int lenght) {
        int temp = arr[i];//取出当前元素的值，保存在临时变量，   以 i 作为父节点（局部）
        //开始调整
        //k = i对应的左子节点
        for (int k = 2 * i + 1; k < lenght; k = 2 * i + 1) {
            if (k + 1 < lenght && arr[k] < arr[k + 1]) {
                //说明左子节点的值小于右子节点
                k++;//让 k 指向右子节点
            }
            if (arr[k] > temp) {
                //如果子节点大于父节点
                //就把较大的值赋值给当前节点
                arr[i] = arr[k];
                // ! i指向k 继续循环比较
                i = k; //把i（父节点）指向 k（子节点）。作为父节点继续循环
            } else {
                //如果子节点小于父节点
                //堆排序是从左至右，从下至上
                break;
            }
        }
        //当for循环结束后，已经将以i为父节点的树的最大值，放在了最顶（局部）
        arr[i] = temp;//将temp值放到调整后的位置

        //adjustHeap()方法中依然要循环, 是因为最后在堆排序的时候是从下到上的, 排序中向上调用这个方法时 , i也会往上走, 这时再次调用adjustHeapt
        //这时再次调用adjustHeap方法时, i就不是最后一个非叶子节点了, 会破坏原先已经排序好的大顶堆, 所以需要循环往下将被破坏的大顶堆重新建立起来
    }
}