堆排序

定义：

• 堆是一颗完全二叉树；
• 堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。
• 堆中每个结点的子树都是堆树。

数据结构：

C 语言
struct MaxHeap
{
    EType *heap; //存放数据的空间，下标从1开始存储数据，下标为0的作为工作空间，存储临时数据。
    int MaxSize; //MaxSize是存放数据元素空间的大小
    int HeapSize; //HeapSize是数据元素的个数
};
MaxHeap H;

初始化堆

  public static void MaxHeapInit(int[] array) {
        for(int i = array.length/2; i > 0; --i){
            array[0] = array[i];//堆值存储从1开始，使用array[0]暂存
            int child = 2*i;
            while(child < array.length){
                if (child < array.length - 1 && array[child] < array[child+1])
                    child++;
                if(array[0] > array[child])
                    break;
                array[child/2] = array[child];
                child = child*2;
            }
            array[child/2] = array[0];
        }
    }

最大堆中插入结点

• 最大堆中插入节点，先在堆末尾插入该节点，然后按照堆的初始化过程将该节点放入到合适的位置。

C 语言源码
void MaxHeapInsert(MaxHeap &H, EType &x)
{
    if(H.HeapSize==H.MaxSize) return false;    
    int i=++H.HeapSize;
    while(i!=1&&x>H.heap[i/2]){
        H.heap[i]=H.heap[i/2];
        i/=2;
    }
    H.heap[i]=x;
    return true;
}

最大堆中删除结点

• 将最大堆的最后一个节点放到根节点，然后删除最大值，然后再把新的根节点放到合适的位置

实战：

• 堆排序的基本思想：
  利用大顶堆（或者小顶堆也行），将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是使其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

升序排序使用大顶堆，降序排序使小顶堆；
public class Main {
    public static void main(String[] args) {
        int[] array = { 0, 20, 70, 30, 10, 60, 50, 30, 90, 100 };
        String aString = Arrays.toString(array);
        System.out.println("排序前   " + aString);
        heapSort(array);
        aString = Arrays.toString(array);
        System.out.println("排序后  " + aString);
    }

    public static void heapSort(int[] array) {
        for (int i = array.length / 2; i > 0; i--) { // 建堆
            heapAdjust(array, i, array.length - 1);
        }

        for (int i = array.length - 1; i > 1; i--) {
            swap(array, 1, i); //将最大值交换到最后
            heapAdjust(array, 1, i - 1);//将剩余数组更新堆
        }
    }

    public static void heapAdjust(int[] array, int small, int large) {
        int temp = array[small];
        for (int j = small * 2; j <= large; j = j * 2) {
            if (j < large && array[j] < array[j + 1]) {
                j++;
            }
            if (temp >= array[j])
                break;
            array[small] = array[j];
            small = j;
        }
        array[small] = temp;
    }

    public static void swap(int[] array, int small, int large) {
        int temp = array[small];
        array[small] = array[large];
        array[large] = temp;
    }
}