Skip to main content
 首页 » 编程设计

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

2022年07月18日45qlqwjy
/** 
 * @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; 
    } 
}

测试代码:

//堆排序
public static void main(String[] args) {
Character[] chars = {'A','H','D','O','E','W','G','T'};
MyHeapSort.sort(chars);
for(int i = 0;i < chars.length;i++){
System.out.print(chars[i] + ", ");
}
System.out.println("over");
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14245673.html