Java实现堆排序(Heapsort)实例代码

import java.util.arrays;

public class heapsort {

    public static void heapsort(datawraper[] data){
        system.out.println("开始排序");
        int arraylength=data.length;
        //循环建堆
        for(int i=0;i<arraylength-1;i++){
            //建堆
            buildmaxheap(data,arraylength-1-i);
            //交换堆顶和最后一个元素
            swap(data,0,arraylength-1-i);
            system.out.println(arrays.tostring(data));
        }
    }

    private static void swap(datawraper[] data, int i, int j) {
        // todo auto-generated method stub
        datawraper tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
    //对data数组从0到lastindex建大顶堆
    private static void buildmaxheap(datawraper[] data, int lastindex) {
        // todo auto-generated method stub
        //从lastindex处节点（最后一个节点）的父节点开始
        for(int i=(lastindex-1)/2;i>=0;i--){
            //k保存正在判断的节点
            int k=i;
            //如果当前k节点的子节点存在
            while(k*2+1<=lastindex){
                //k节点的左子节点的索引
                int biggerindex=2*k+1;
                //如果biggerindex小于lastindex，即biggerindex+1代表的k节点的右子节点存在
                if(biggerindex<lastindex){
                    //若果右子节点的值较大
                    if(data[biggerindex].compareto(data[biggerindex+1])<0){
                        //biggerindex总是记录较大子节点的索引
                        biggerindex++;
                    }
                }
                //如果k节点的值小于其较大的子节点的值
                if(data[k].compareto(data[biggerindex])<0){
                    //交换他们
                    swap(data,k,biggerindex);
                    //将biggerindex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    k=biggerindex;
                }else{
                    break;
                }
            }
        }
    }

    public static void main(string[] args) {
        // todo auto-generated method stub
        datawraper [] data={
                new datawraper(21, ""),
                new datawraper(30, ""),
                new datawraper(49, ""),
                new datawraper(30, "*"),
                new datawraper(16, ""),
                new datawraper(9, ""),

        };
        system.out.println("排序之前：\n"+arrays.tostring(data));
        heapsort(data);
        system.out.println("排序之后：\n"+arrays.tostring(data));
    }

}

结果：

排序之前：
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 21, 30*, 16, 49]
[16, 30*, 21, 9, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
排序之后：
[9, 16, 21, 30*, 30, 49]