java算法之自定义堆排序：从小到大排序

/** 
 * @desc: 自定义堆排序：从小到大排序 
 * @author: 毛会懂 
 * @create: 2021-01-06 14:50:00 
 **/ 
public class MyHeapSort<T> { 
    public static void sort(Comparable[] source){ 
        //创建堆 
        Comparable[] heap = createHeap(source); 
        //堆排序 
        int size = heap.length-1; 
        while (size > 0){ 
            //交换堆第一个元素和最后一个元素 
            exec(heap,1,size); 
            size--; 
            //下沉第一个元素 
            sink(heap,1,size); 
        } 
        System.arraycopy(heap,1,source,0,source.length); 
    } 
 
    //堆的构造，最直观的想法就是另外再创建一个新数组，然后从左往右遍历原数组，每得到一个元素后，添加 
    //到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。 
    //上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组 
    //0~length-1的数据拷贝到新数组的1~length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后 
    //对扫描到的每一个元素做下沉调整即可。 
    private static Comparable[] createHeap(Comparable[] source){ 
        Comparable[] temp = new Comparable[source.length +1]; 
        System.arraycopy(source,0,temp,1,source.length); 
        //叶子节点不需要下沉 
        for(int i = temp.length / 2;i >=1;i--){ 
            sink(temp,i,source.length); 
        } 
        return temp; 
    } 
 
    //下沉 
    private static void sink(Comparable[] temp,int i,int size){ 
        while (2 * i <= size){ 
            int max; 
            if(2 * i + 1 <= size) { 
                if (great(temp, 2 * i, 2 * i + 1)) { 
                    max = 2* i; 
                }else{ 
                    max = 2 * i + 1; 
                } 
            }else{ 
                max = 2* i; 
            } 
            if(great(temp,max,i)){ 
                exec(temp,max,i); 
            } 
            i = max; 
        } 
    } 
 
    //比较两个元素的大小(arr[i]大，返回True) 
    private static Boolean great(Comparable[] arr, int i,int j){ 
        return arr[i].compareTo(arr[j]) > 0; 
    } 
 
    //交换两个元素位置 
    private static void exec(Comparable[] arr, int i,int j){ 
        Comparable t = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = t; 
    } 
}