堆排序（heapsort）

堆排序

堆排序是利用堆结构（特殊的完全二叉树）实现排序的算法，时间复杂度是O（nlogn）。堆排序不稳定。

原理

堆排序要构建一颗完全二叉树（存储在数组，详见： 二叉树的数组存储），这颗二叉树就是堆。堆有大堆和小堆两种（结构类似）。这里以大堆为例。
在最大堆中每个节点都比子节点大，根节点最大，每个分枝都是一个堆，叶子节点天然就是堆。
构成一个堆之后。然后取堆首-重新构建堆-再取… 元素按大到小依次取出（原地排序），完成排序。

---

示例代码如下：

public class Heapsort {
    void sort(int[] arr){
        //建堆，叶子节点已经是堆了，所以从非叶子节点开始建堆
        for(int i = arr.length/2-1; i >= 0; i--){
            create(arr, i, arr.length - 1);
        }

        //取出跟节点（最大）与最后一个节点交换，然后修正堆
        int i = arr.length-1;//i指向堆的末尾
        while(i > 0){
            int k = arr[0];
            arr[0] = arr[i];
            arr[i] = k;

            i--;//减小堆的规模，这样修正堆时，新的堆不包括刚取出的根节点。相当于不断取出最大的元素。依次形成序列（升序）

            create(arr, 0, i);
        }
    }
    //构建、维护堆 （大堆）
    //这里只考虑将给定节点调整到堆的合适位置
    void create(int[] arr, int start, int end){
        int node = start*2 + 1;//左子节点下标
        //如果有子节点则进入，没有就说明要操作的节点是叶子节点，直接结束
        while(node <= end){
            //在两个字节点中挑一个最大的，（如果是小堆，就挑最小的）
            if(node+1 <= end && arr[node+1] > arr[node]){
                node++;
            }
            //比较父节点和子节点，如果父节点大，说明堆是好的（不用交换），return。否则交换节点后向下迭代
            if(arr[start] >= arr[node]){
                return;
            }else{
                int k = arr[start];
                arr[start] = arr[node];
                arr[node] = k;

                //重新设置父子节点下标，向下迭代，直到构成堆。
                start = node;
                node = start*2+1;
            }
        }
    }
}