排序算法：堆排序

堆

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值；
2. 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

例如：

构建堆

数组和堆的特点

1. 使用一维数组来表示一个堆，下标从0~n，0表示堆顶
2. 如果一个节点的下标为x，那么左子节点的下标为 2x+1，右子节点的下标为2x+2
3. 如果一个节点的下标为x，那么父节点的下标为(x-1)/2

堆化

在一个已经是最大堆（或者最小堆）的末尾插入一个数据，有可能会打破这个最大堆（或者最小堆）

如下图，在一个最大堆末尾插入一个14的数据，就打破了这个最大堆。这时需要进行堆化处理。

处理方式就是，用这个插入的节点和其父节点对比，如果比父节点大，则互相交换。

交换后再继续和其父节点比较，直至堆顶。

构建堆

由于堆的节点和数组下标有着明显的对应特征，所以构建一个堆只需要固定的几个临时变量，空间复杂度只有O(1)。

构建一个堆也比较简单：

1. 首先认为下标0的数据为堆顶
2. 接着认为向这个最大堆（或者最小堆）的末尾（首次下标是1）插入数据
3. 处理这个新插入的数，使数据堆化
4. 重复2~3的步骤，直至数组最后一个元素

需要注意的是：如果要升序排序，则需要构建最大堆，如果要降序排序，则需要构建最小堆

排序

排序步骤也比较简单，就是在执行剔除堆顶的操作

1. 交换堆顶（下标为0）的数据和数组最后一个（首次下标为n）的数据，此时最后一个数据是已升序排列完的数据
2. 由于步骤1，导致打破了最大堆（或者最小堆），执行堆化操作
3. 再重复1~2 直至整个堆只剩下堆顶一个数据为止

示意图

时间复杂度和空间复杂度

堆的构建时间复杂度：O(n²)
排序时间复杂度：O(nlogn)

稳定性

由于对序列跳跃式维护堆的结构性质，相同值顺序无法得到保障，所以堆排序是不稳定的。

代码

    public void sort(int[] nums){
        buildHeap(nums);
        int point = nums.length - 1;
        while(point > 0){
            int temp = nums[0];
            nums[0] = nums[point];
            nums[point] = temp;
            heapity(nums,point);
            point--;
        }
    }

    private void heapity(int[] nums, int point) {
        int index = 0;
        while(index <= point){
            int left = 2 * index + 1;
            int right = left +1;
            if(left >= point){
                //超出界限
                return;
            }else if(right >= point){
                //右子节点超出边界
                if(nums[left] > nums[index]){
                    int temp = nums[left];
                    nums[left] = nums[index];
                    nums[index] = temp;
                    index = left;
                }else{
                    return;
                }
            }else{
                if(nums[left] >= nums[right] && nums[left] > nums[index]){
                    int temp = nums[left];
                    nums[left] = nums[index];
                    nums[index] = temp;
                    index = left;
                }else if(nums[right] >= nums[left] && nums[right] > nums[index]){
                    int temp = nums[right];
                    nums[right] = nums[index];
                    nums[index] = temp;
                    index = right;
                }else{
                    return;
                }
            }
        }
    }

    private void buildHeap(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            buildHeap(nums,i);
        }
    }

    private void buildHeap(int[] nums,int index) {
        while(index > 0 ) {
            int parentIndex = (index-1) / 2;
            if (nums[parentIndex] < nums[index]) {
                int temp = nums[parentIndex];
                nums[parentIndex] = nums[index];
                nums[index] = temp;
                index = parentIndex;
            } else {
                return;
            }
        }
    }