排序算法-堆排序

思路

        堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。       

        我们先将要排序的数据建成堆，然后通过下图所示的步骤进行排序

         特性总结：

        1. 堆排序使用堆来选数，效率就高了很多。

        2. 时间复杂度：O(N*logN)

        3. 空间复杂度：O(1)

        4. 稳定性：不稳定

代码及注释

        

public class HeapSort {
    public static void heapSort(int[]arr){
        //先将数组中的数据创建成堆
        //由于要进行升序排序，所以要创建大根堆
        createBigHeap(arr);
        //此时数组中的数据已经是大根堆了
        //由于大根堆堆顶的数是最大的，所以可以将堆顶的数换到数组最后，然后再将其余的数据转换为大根堆，继续同样的操作
        int length=arr.length;
        for(int i=1;i
            int end=length-i;
            swap(arr,0,end);
            siftDown(arr,0,end);
        }
    }
 
    private static void createBigHeap(int[]arr){
        //要对拥有子树的节点进行向下调整
        int length=arr.length;
        //遍历所有拥有子树的节点
        for(int i=(length-1-1)/2;i>=0;i--){
            //对父节点向下调整（用两个子树的最大值与父节点的值进行比较，如果父节点小，则交换父节点与子节点）
            siftDown(arr,i,length);
        }
    }
    //向下调整
    //调整根节点parent所在的树，使成为大根堆
    private static void siftDown(int[]arr,int parent,int end){
        //获得父节点parent左子树的下标child
        int child=parent*2+1;
        //child没有超过范围，表示当前的parent确实是父节点
        while (child
            //子节点和父节点交换有以下3种情况
            //1.没有右孩子，此时就比较左孩子与父节点的大小，左孩子大，就交换
            //2.有右孩子，此时比较左孩子与右孩子的大小，要是左孩子大，就比较左孩子与父节点的大小，还是左孩子大，就交换
            //3.有右孩子，此时比较左孩子与右孩子的大小，要是右孩子大，就比较右孩子与父节点的大小，还是右孩子大，就交换
            //判断child此时应该指向左孩子还是右孩子，child一开始指向的是左孩子，经过判断后，child会指向比较大的那个孩子
            if(child+11]){
                child=child+1;
            }
            //判断比较大的子孩子与父节点之间的大小关系
            if(arr[child]>arr[parent]){
                swap(arr,child,parent);
            }
 
            //可能交换后对于下一层的树还是不合适，就还要继续进行向下调整
            parent=child;
            child=parent*2+1;
        }
    }
 
    public static void swap(int[] arr,int m,int n) {
        int tmp=arr[m];
        arr[m]=arr[n];
        arr[n]=tmp;
    }
}