堆排序（Java版）

堆排序的原理是先构造一个大顶堆，每次弹出堆中一个最大元素填充到数组倒数第N的位置（逆序），即可将数组由小到大进行排序。

堆排序的平均时间复杂度为O(nlogn)， 最好的时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。

/**
 * Created by lkmc2 on 2018/3/8.
 * 堆排序
 */

//堆结构
class MaxHeap {
    private int[] data; //该数组从1开始使用，0不使用
    private int count; //数组当前存值的数量
    private int capacity; //数组总长度

    public MaxHeap(int capacity) {
        this.data = new int[capacity + 1]; //数组的0下标不用，从1开始存值
        this.count = 0;
        this.capacity = capacity;
    }

    public MaxHeap(int[] arr, int n) {
        this.data = new int[n + 1];
        this.capacity = n;
        for (int i = 0; i < n; i++)
            data[i + 1] = arr[i];

        this.count = n;

        //从第一个非叶子节点的父元素开始进行shiftDown操作
        //该父元素的位置为数组当前存值的长度的二分之一，即 count / 2
        for (int j = count / 2; j >= 1; j--)
            shiftDown(j); //将处于下标为j的元素向下移动到正确的位置
    }

    //取出优先级最大的一个元素，也就是下标为1的元素，并把最后一个元素放到下标为1的地方，
    // 然后位置的元素不断和下面的元素比较，直到找到合适的位置
    public void shiftDown(int k) {
        while (2 * k <= count) {
            int j = 2 * k; //在此轮循环中，data[k]和data[j]交换位置

            if (j + 1 <= count && data[j + 1] > data[j])  //右节点比左节点值大
                j += 1; //将j坐标移动到右节点

            if (data[k] > data[j]) //该节点比左节点和右节点的值都大，结束循环，调整结束
                break;

            int temp = data[k]; //该节点与左节点或右节点交换
            data[k] = data[j];
            data[j] = temp;

            k = j; //更新该节点坐标
        }
    }

    public void shiftUp(int k) { //插入元素后，该元素与父节点比较，大于父节点则交换位置
        while (k > 1 && data[k / 2] < data[k]) { // k/2 表示父节点的坐标，父节点小于该元素
            int temp = data[k / 2]; //交换该元素与父节点的值
            data[k / 2] = data[k];
            data[k] = temp;

            k /= 2; //更新交换后的坐标
        }
    }

    void insert(int item) { //插入元素
        if (count + 1 > capacity) return;

        data[count + 1] = item; //添加新元素到数组
        count++;
        shiftUp(count); //与父节点比较找到该元素的正确位置
    }

    int extractMax() { //取出最大值
        if (count <= 0) return -1;
        int result = data[1]; //获取第一个元素的位置

        int temp = data[1]; //交换第一个元素与最后一个元素的位置
        data[1] = data[count];
        data[count] = temp;

        count--;
        shiftDown(1); //将处于下标为1的元素向下移动到正确的位置
        return result;
    }

    int size() { //获取当前数组中元素个数
        return count;
    }

    boolean isEmpty() { //获取数组是否为空
        return count == 0; 
    }
}

public class HeapSort {

    public static void heapSort1(int[] arr, int n) { //堆排序1（从小到大）
        MaxHeap maxHeap = new MaxHeap(n);
        for (int i = 0; i < n; i++)
            maxHeap.insert(arr[i]); //将数组中的值插入堆

        for (int j = n - 1; j >= 0; j--)
            arr[j] = maxHeap.extractMax(); //取出最大值，存回数组
    }

    //堆排序2（从小到大，使用Heapify，效率比堆排序1高）
    public static void heapSort2(int[] arr, int n) { 
        MaxHeap maxHeap = new MaxHeap(arr, n);

        for (int j = n - 1; j >= 0; j--)
            arr[j] = maxHeap.extractMax(); //取出最大值，存回数组
    }

    public static void main(String[] args) {
        int[] arr1 = {88,34,18,47,83,79,20};
        heapSort1(arr1, arr1.length);
        printInfo(arr1);

        int[] arr2 = {88,34,18,47,83,79,20};
        heapSort2(arr2, arr2.length);
        printInfo(arr2);
    }

    public static void printInfo(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

堆排序运行结果