堆排序

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(nlogn)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(nlogn)
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定

原理

       堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构（通常堆是通过一维数组来实现的），并同时满足堆的性质：即子结点的键值总是小于（或者大于）它的父节点。

步骤

1. 创建一个堆
2. 把堆顶元素(最大值)和堆尾元素互换
3. 把堆的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
4. 重复步骤2，直到堆的尺寸为1

代码实现

public class HeapSort {

    // 堆大小
    private int heapsize;

    // 堆调整函数(这里使用的是最大堆)
    private void heapify(Integer a[], int i)
    {
        // 左孩子索引
        int leftchild = 2 * i + 1;
        // 右孩子索引
        int rightchild = 2 * i + 2;
        // 选出当前结点与左右孩子之中的最大值
        int largest;

        if (leftchild < heapsize && a[leftchild] > a[i]){
            largest = leftchild;
        }
        else{
            largest = i;
        }

        if (rightchild < heapsize && a[rightchild] > a[largest]) {
            largest = rightchild;
        }

        if (largest != i)
        {
            // 把当前结点和它的最大(直接)子节点进行交换
            Tool.exchange(a, i, largest);
            // 递归调用，继续从当前结点向下进行堆调整
            heapify(a, largest);
        }
    }

    // 建堆函数
    private void buildheap(Integer a[], int n)
    {
        heapsize = n;
        // 对每一个非叶结点
        for (int i = heapsize / 2 - 1; i >= 0; i--) {
            // 不断的堆调整
            heapify(a, i);
        }
    }

    public void heapsort(Integer a[], int n)
    {
        buildheap(a, n);
        for (int i = n - 1; i >= 1; i--)
        {
            // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
            Tool.exchange(a, 0, i);
            // 从堆中去掉最后一个元素
            heapsize--;
            // 从新的堆顶元素开始进行堆调整
            heapify(a, 0);
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        HeapSort sort = new HeapSort();
        sort.heapsort(a,a.length);
        System.out.println("array by HeapSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果

array by HeapSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]