堆排序算法

完全二叉树中的数都可以用数组来表示，本算法的目的就是将数组中的数从小到大排序。

在完全的二叉树的基础上，构建最大二叉堆，然后将最大的元素与尾元素进行交换，将最大的元素放在数组的尾部。

如果要实现从大到小排序，那么只需要修改代码，先构造最小二叉堆就可以了。

完全二叉树的特性：如果父节点的索引为i，

那么他的左节点可以用2*i+1来表示，他的右节点就是2*（i+1）

public class ErChaDuiSorting {
    public static void main(String[] args) {
        TreeNode node1=new TreeNode(22);
        TreeNode node2=new TreeNode(456);
        TreeNode node3=new TreeNode(56);
        TreeNode node4=new TreeNode(58);
        TreeNode node5=new TreeNode(99);
        TreeNode node6=new TreeNode(789);

        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

        int[] kobe=new int[6];
        kobe[0]=node1.val;
        kobe[1]=node2.val;
        kobe[2]=node3.val;
        kobe[3]=node4.val;
        kobe[4]=node5.val;
        kobe[5]=node6.val;

        Method003 kkk = new Method003();
        int[] ints = kkk.sortArray(kobe);
        kkk.PrintArray(ints);

    }
}
class Method003{
    private static int len;
    public static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    public int[] sortArray(int[] nums){
        len=nums.length;
        if(len<1){
            return nums;
        }
        //构建一个最大堆
        buildMaxHeap(nums);
        while(len>0){
            swap(nums,0,len-1);
            len--;
            adjustHeap(nums,0);
            PrintArray(nums);
            System.out.println("------------------");

        }
        return nums;
    }

    //调整  使二叉树变成二叉堆
    private void adjustHeap(int[] nums, int i) {
        int maxIndex=i;
        int left=2*i+1;
        int right=2*(i+1);
        if (leftnums[maxIndex]) {
            maxIndex=left;
        }
        if (rightnums[maxIndex]&&nums[right]>nums[left]) {
            maxIndex=right;
        }
        if(maxIndex!=i){
            swap(nums,maxIndex,i);
            PrintArray(nums);
            adjustHeap(nums,maxIndex);
        }
    }

    //构建一个最大堆
    private void buildMaxHeap(int[] nums) {
        for(int i=(len/2-1);i>=0;i--){
            adjustHeap(nums,i);
        }
        System.out.println("构造完成最大堆");
        PrintArray(nums);
        System.out.println("============================");
    }

    public void PrintArray(int[] kobe) {
        for(int i=0;i