堆排序

在开始堆排序之前，先补充几个知识点

• 这里的堆（二叉堆），指得不是堆栈的那个堆，而是一种数据结构。
  堆可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示，每一个结点对应数组中的一个元素。
• 最大堆
  二叉堆一般分为两种：最大堆和最小堆。
  堆中每个父节点的元素值都大于等于其孩子结点（如果存在）,这样的堆就是一个最大堆
  因此，最大堆中的最大元素值出现在根结点(堆顶)。

堆排序的思想

1. 将长度为 n 的待排序的数组进行堆有序化，构造成一个大顶堆
2. 将根节点与尾节点交换并输出此时的尾节点（此时尾节点是未出堆节点中最大值）
3. 将剩余的 n-1 个节点重新进行堆有序化
4. 重复2、3，直至构造成一个有序序列

我们二叉堆一开始如下图

图0

进行堆的有序化调整

在构造有序堆时，我们开始只需要扫描一半的元素（n/2-1 ~ 0）即可，
因为 (n/2-1)~0 的节点才有子节点，如上图0，n=8, (n/2-1) = 3 即 3 2 1 0 这个四个节点才有子节点
将 3、2、1、0 这四个节点从下到上、从右到左与其子节点进行比较调整成最大堆，过程如下

QQ20170919-154812.png QQ20170919-155101.png QQ20170919-155210.png QQ20170919-155306.png

上几张图很清晰，调整堆后

QQ20170919-155403.png

尾节点与根节点交换，再将此时的尾节点输出。之后再将剩余的 (n-1) 个节点进行堆有序化。如下几图

QQ20170919-155527.png QQ20170919-161943.png QQ20170919-162409.png QQ20170919-162850.png QQ20170919-163206.png QQ20170919-163558.png

......

QQ20170919-164543.png

代码实现

public class HeapSort {
    private static void heapSort(int[] arr) {
        int len = arr.length -1;
        for(int i = len/2 - 1; i >=0; i --){ //堆构造
            heapAdjust(arr,i,len);
        }
        while (len >=0){
            swap(arr,0,len--);    //将堆顶元素与尾节点交换后，长度减1，尾元素最大
            heapAdjust(arr,0,len);    //再次对堆进行调整
        }
    }

    public static void heapAdjust(int[] arr, int i, int len){
        int left, right, j;
        while((left = 2*i+1) <= len) {    //判断当前父节点有无左节点（即有无孩子节点，left为左节点）
            right = left + 1;  //右节点
            j = left;   //j"指针指向左节点"
            if(j < len && arr[left] < arr[right]) { //右节点大于左节点
                j ++;     //当前把"指针"指向右节点
            }
            //将父节点与孩子节点交换（如果上面if为真，则arr[j]为右节点，如果为假arr[j]则为左节点）
            if(arr[i] < arr[j]) {
                swap(arr, i, j);
            }
            else { //说明比孩子节点都大，直接跳出循环语句
                break;
            }
            i = j;
        }
    }
    public static void swap(int[] arr, int i, int len){
        int temp = arr[i];
        arr[i] = arr[len];
        arr[len] = temp;
    }
    public static void main(String[] args) {
        int array[] = {20,50,20,40,70,10,80,30,60};
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        heapSort(array);
        System.out.println("\n排序之后：");
        for(int element : array){
            System.out.print(element+" ");
        }
    }
}