排序算法，堆排序

相信大家都听说堆排序吧，二叉树在大学期间大家应该都学过，不过按照我当时那个状态，是完全没听懂。

这都好多年了，我觉得再不弄懂二叉树排序，我怕是死都不能瞑目了。

首先，要想要排序，得有一个数组，biu~

这个数组大家看到了，是一个无序数组，要想用堆排序，首先让它变成一个堆

一、初始化堆

1、从左往后，先取出 8

、

2、然后取出3 ，放在8的左下方

3、取出2放在8的右下方

4、取出9放在3的做下方

5、但是9大于3所以3和9交换位置

6、但是9又大于8，8和9再次交换位置

7、这样就可以了，继续取数组。把1取出来放在3的右侧，8的右下方

8、取出4放在2的左下方

9、但是4比2大，同理，继续交换位置

10、取6放在4的右下侧，但是6大于4

11、交换位置

经过11步，我们看到，已经得到一个稳定堆了，这个堆有什么特征呢？

二叉树的父节点比左右两个子节点大

如果把元素的位置都用红色序号标记，那么的要如下图

最后的出公式：

arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]

二、堆排序

现在我们得到一个稳定堆了之后，我们还得要一个新数组，我们就可以开始排序了：

1、取出位置一（4）和位置七（9）进行交换，然后将数字9存到最后一位，下次遍历不会再包含9

得出：

2、可以看出，在9和4进行了交换后，这个堆（排除9）就不是一个稳定堆了，因为不满足，初始化堆的时候：二叉树的父节点比左右两个子节点大

那么将进行第二轮交换。

从4开始我们把8和4进行交换后，发现堆又稳定了

那么,把位置一（8）和位置六（2）进行交换，然后将数字8存到最后一位，下次遍历不会再包含8,9

就这样循环第一步，第二步，就可以得到一个从小到大的数组：

最后附上代码（递归方式）：

/**
 * @Description :
 * @Author :付亚东
 * @Date :2020/3/13
 **/
public class Test {
    public static void main(String[] args) {
        int[] arr= {8,3,2,9,1,4,6};
        initHeap(arr);
        sortHeap(arr);
        System.out.println("-------");
        for (int a:arr) {
            System.out.print(a);
        }
        System.out.println("");
        System.out.println("-------");
    }

    /***
     * 初始化堆，稳定堆，这个方法是第一大步
     * @param arr
     */
    public static void initHeap(int[] arr){
        //将数组先转换成一个堆，就是上边的图一
        //因为最后一层的借点没有子节点，所以直接从倒数第二行的最后一个节点开始，也就是图一的2
        for(int i=(arr.length-2)/2;i>=0;i--){
            swapHeap(arr,i,arr.length-1);
        }
    }

    /***
     * 这个方法是第二大步
     * @param arr
     */
    public static void sortHeap(int[] arr){
        //将堆顶的那个数字和最后一个数字交换
        for (int i=arr.length-1;i>0;i--){
            swapLocation(arr,0,i);
            //继续交换，从堆顶开始（父节点也就是0）,i-1代表排除已经交换过位置的
            swapHeap(arr,0,i-1);
        }
    }


    /***
     * 堆排序
     * @param arr
     * @param parent
     * @param length
     */
    public static void swapHeap(int[] arr,int parent,int length){
        //这是传进来的节点的左子节点
        int leftChiledLocation = (parent<<1)+1;
        //这是传进来的节点的右子节点
        int rightChiledLocation = leftChiledLocation+1;
        //临时当做父节点最大
        int maxChildLocation=leftChiledLocation;
        // 左子节点索引超出计算范围，直接返回。
        if(leftChiledLocation>length) return;

        //查出两个子节点比较大的哪一个，赋值给maxChild
        if(rightChiledLocation<=length && arr[leftChiledLocation]<arr[rightChiledLocation]){
            maxChildLocation = rightChiledLocation;
        }
        //然后判断两个子节点大的那一个，和自己本身比较，如果比自己（父节点）大，就交换位置,若“<”这是从大到小
        if(arr[maxChildLocation]>arr[parent]){
            swapLocation(arr,maxChildLocation,parent);
            //然后把换好的位置，也就是左节点或者右节点，继续往下查找
            swapHeap(arr,maxChildLocation,length);
        }
    }

    /***
     * 交换数组位置
     * @param arr
     * @param a
     * @param b
     */
    public static void swapLocation(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

}