七大排序——堆排序

1、堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为0(nlogn)，它也是不稳定排序。
2、堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
3、每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

4、同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

 5、堆排序的基本思想是:.
（1）将待排序序列构造成一个大顶堆
（2）此时，整个序列的最大值就是堆顶的根节点。
（3）将其与末尾元素进行交换，此时末尾就为最大值。
（4）然后将剩余n-1 个元素重新构造成-一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

1、任意数组其实都可以看做是一个完全二叉树，将数组先调整为最大堆，就是从最后一个非叶子节点开始进行元素下沉操作

[15,19,11,18,14,17,6,3,8,1,9]

 2、不断的交换堆顶元素和最后一个元素的位置，继续进行元素下沉操作，直到剩下一个未排序元素为止，此时整个数组已经有序了

 3、代码实现

package Seven_sorts;

import java.util.Arrays;


public class heap_sort {
    public static void main(String[] args) {
        int[] arr={15,19,11,18,14,17,6,3,8,1,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr){
        //先将数组调整为最大堆
        for (int i = (arr.length-1-1)/2; i >=0; i--) {
            siftDown(arr,i,arr.length);
        }
        //不断交换堆顶元素到数组末尾
        for (int i = arr.length-1; i >0; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    
    private static void siftDown(int[] arr, int i, int length) {
        while (2*i+1arr[j]){
                j++;
            }
            //此时j就是左右子树中的最大值索引
            if (arr[i]>arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i=j;
            }
        }
    }
}