堆排序

堆排序原理：从最后一个树叉结点开始往前，将每个树叉结点所在树修复成大根堆，然后将堆的根结点(最大值)与末尾结点交换，去掉末尾结点，再将余下节点修复成大根堆，再将根结点与末尾结点交换...最后得到由小到大的已排数组。

完全二叉树父子结点索引公式：父结点=i,左孩子=i*2-1,右孩子=i*2
大根堆：父结点大于子节点的完全二叉树

时间复杂度：O(nlogn)，稳定

 

public static <T extends Comparable<T>> int compare(T a, T b) {
    if (a == null){
        return b == null ? 0 : -1;
    }
    if (b == null){
        return 1;
    }
    return a.compareTo(b);
}

 

 

/**
 * @description 如果一直存在孩子节点比根结点大，则将孩子节点往父结点移动
 * @param data
 * @param offset
 * @param end
 */
private static <T extends Comparable<T>> void repareHeap(T[] data, int offset, int end) {
    int child = (offset << 1) + 1;
    int parent = offset;
    T tmp = data[parent];
    while (child < end) {
        //指向数值大的孩子结点
        if (child + 1 < end && compare(data[child], data[child + 1]) < 0) {
            ++child;
        }
        //如果孩子节点比根节点大，移向父结点
        if (compare(tmp, data[child]) < 0) {
            data[parent] = data[child];
            parent = child;
            child = (child << 1) + 1;
        } else {
            child = end;
        }
    }
    data[parent] = tmp;
}

 

 

 

/**
 * @description 堆排序
 * @param data
 */
public static <T extends Comparable<T>> void heapSort(T[] data) {
    if (data == null || data.length < 2){
        return;
    }
    int i, len = data.length;
    //从最后一个树叉结点开始往前，对每个根结点进行一次大根堆修复运算，保证每个树叉结点形成的树都是一个大根堆
    for (i = (len >>>1) - 1; i >= 0; --i) {
        repareHeap(data, i, len);
    }
    T tmp;
    //大根堆的根结点即最大值，和末尾节点交换
    //交换后根结点可能非最大值，需要再对余下节点进行一次大根堆修复运算即可得到完整大根堆
    for (i = len - 1; i > 0; --i) {
        tmp = data[0];
        data[0] = data[i];
        data[i] = tmp;
        repareHeap(data, 0, i);
    }
}