排序算法（java）——— 堆排序

——利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
基本思想：
1.将堆排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
2.将其与末尾元素进行交换，此时末尾就为最大值。
3.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4.如此反复执行，便能得到一个有序序列

package com.xu.Array;
import java.util.Arrays;
//八、堆排序
public class Demo12 {
    public static void main(String[] args) {
        int[] arr=new int[10];
        for(int i=0;i<arr.length;i++){
            arr[i]=(int)(Math.random()*100);
        }
        System.out.println("排序前："+ Arrays.toString(arr));
        //定义开始调整的位置
        int startIndex=(arr.length-1)/2;
        //循环开始调
        for(int i=startIndex;i>=0;i--){
            toMaxHeap(arr,arr.length,i);
        }
        //经过上面的 *** 作后，已经把数组变成了一个大顶堆，把根元素和最后一个元素调换
        for(int i=arr.length-1;i>0;i--){
            int t=arr[0];
            arr[0]=arr[i];
            arr[i]=t;toMaxHeap(arr,i,0);
        }
        System.out.println("排序后 ："+Arrays.toString(arr));
    }
    private static void toMaxHeap(int[] arr,int size,int index) {
        //获取左右字节的索引
        int leftNodeIndex=index*2+1;
        int rightNodeIndex=index*2+2;
        //查找最大节点所对应的索引
        int maxIndex=index;
        if(leftNodeIndex<size&&arr[leftNodeIndex]>arr[maxIndex]){
            maxIndex=leftNodeIndex;
        }
        if(rightNodeIndex<size&&arr[rightNodeIndex]>arr[maxIndex]){
            maxIndex=rightNodeIndex;
        }
        if(maxIndex!=index){
            int t=arr[maxIndex];
            arr[maxIndex]=arr[index];
            arr[index]=t;
            //调换完之后，可能会影响到下面的子树，不是大顶堆，我们还需要再次调换
            toMaxHeap(arr,size,maxIndex);
        }
    }
}