java实现的堆排序

堆的概念

Heap:

1. 必须是一个完全二叉树
2. 满足parent > children,每个结点都是

堆排序

• 完成堆排序，首先使得该序列满足堆的特征，首先heapify,使之成为堆，然后每次拿出堆顶的最大元素放于堆末尾与堆末尾交换，堆末尾的元素然后不加入下次最大值的选取。然后堆顶元素heapify,构建堆，堆顶又得出了最大值，类似于选择排序，但是比较的次数比选择排序要少很多，大批量的数据的时候，最坏情况也只是N*log（N）
• 自定义待比较元素的比较规则，可以生成非递增和非递减序列，比较灵活，实现了代码复用

Sort.java

public abstract class Sort <T extends Comparable<T>>{
    public abstract void sort(T[] nums);

    protected boolean less(T v, T w){
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a, int i, int j){
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

HeapSort.java

import a.b.c.sort.Sort;
// 这个堆排序索引为0的位置不放元素
public class HeapSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        // 这步用来构建一个堆
        for(int k = N/2; k >= 1; k--)
            sink(nums,k,N);
        // 这步每次得到一个最大值，把堆顶放在末尾
        while(N > 1){
            swap(nums,1, N--);
            sink(nums,1, N);
        }
    }

    private void sink(T[] nums,int k,int N){
        while(2 * k <= N){
            int j = 2 * k;
            if(j < N && less(nums,j,j+1))
                j++;
            if(!less(nums,k,j))
                break;
            swap(nums,k,j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i,int j){
        return nums[i].compareTo(nums[j]) < 0;
    }
}

测试|Cat.java

public class Cat implements Comparable<Cat>{
    private int age;
    private String name;
    public Cat(int age,String name){
        this.age = age;
        this.name = name;
    }
    @Override
    public int compareTo(Cat cat) {
        return cat.age - this.age ; //非递增排序
    }

    @Override
    public String toString() {
        return "Cat{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

测试|Test.java

import a.b.c.sort.Cat;

public class Test {
    // 根据上述对应的索引映射规则，索引0位置不应放入实际元素
    public static void main(String[] args) {
        Cat[] cats = {
                null,
            new Cat(2,"花花"),
            new Cat(11,"老猫"),
            new Cat(4,"MIao猫"),
            new Cat(1,"啊该奥"),
            new Cat(3,"dakka")
        };
        System.out.print("[");
        for (int i = 0; i < cats.length; i++) {
            if(i<cats.length - 1)
                System.out.print(cats[i] + ",");
            else
                System.out.print(cats[i]);
        }
        System.out.println("]");
        new HeapSort<Cat>().sort(cats);
        // 堆排序后
        System.out.println("堆排序后");
        System.out.print("[");
        for (int i = 0; i < cats.length; i++) {
            if(i<cats.length - 1)
                System.out.print(cats[i] + ",");
            else
                System.out.print(cats[i]);
        }
        System.out.print("]");
    }
}

结果