排序算法 --- 堆排序

1. 堆排序介绍：

• 堆排序是利用“堆”这种数据结构设计的，也是一种选择排序，时间复杂度为O(nlogn)，属于不稳定排序。
• 堆，其实就是具有某些特征的完全二叉树。特点就是：每个节点的值都大于其左右孩子节点的值，这样的叫大顶堆；反之叫小顶堆。

大顶堆

如果我们以图中黑色数字作为索引将值依次存到数组里，那么数组就是：

50, 45, 40, 20, 26, 35, 30, 10, 15

可以发现，arr[i] > arr[2*i + 1]，arr[i] > arr[2*i + 2]。

在用堆排序的时候，如果要升序，那就使用大顶堆，如果要降序，那就使用小顶堆。··

2. 排序思想：

• 将待排序列构造成一个最大堆。不需要真正地构建二叉树，之前说了二叉树的顺序存储，这里就派上用场了；

• 此时，整个序列的最大值就是堆顶的根节点；

• 将堆顶元素与末尾元素进行交换，此时末尾元素就是最大值；

• 将剩余的(n - 1)个元素，重新构造成一个堆，如此反复执行……

3. 代码实现：

首先写个方法，将树调整成大顶堆，具体步骤看代码注释：

/**
* 把以index为父节点的子树调整成大顶堆
* @param arr 数组
* @param index 非叶子节点的索引
* @param length 对多少个元素进行调整
*/
private static void buildHeap(int[] arr, int index, int length) {
    // 保存index对应的值，其实就是要调整子树的父节点的值
    int temp = arr[index];
    // 开始调整，i就是index节点的左子节点
    for (int i=(index * 2 + 1); i<length; i = (i * 2 + 1)) {
        // 如果左子节点小于右子节点，那就让i指到右子节点
        if (i + 1 < length && arr[i] < arr[i+1]) {
            i++;
        }
        // 经过上面操作，arr[i]就是最大的子节点
        if (arr[i] > temp) {
            // 如果最大子节点的值比父节点更大，就把这个子节点的值赋给父节点
            arr[index] = arr[i];
            // 然后就以刚才那个最大子节点为父节点，再循环进行调整
            index = i;
        } else {
            break;
        }
    }
    // 循环结束，就是调整结束，要把刚才保存的父节点的值赋给当前节点，这才完成了父节点与子节点值的交换
    arr[index] = temp;
}

然后就可以写排序方法了，首先调用一次调整大顶堆的方法，然后将堆顶元素放到最后，此时最后那个元素就是最大的了，然后再进行调整，就可以少调整一个数了，具体代码如下：

public static void sort(int[] arr) {
    // 遍历数组，找到非叶子节点，对以非叶子节点为父节点的子树进行调整
    // (arr.length / 2 - 1)就可以找到完全二叉树的最后一个非叶子节点
    for(int i=(arr.length / 2 - 1); i>=0; i--) {
        buildHeap(arr, i, arr.length);
    }
    // 调整成大顶堆后，让堆顶元素与末尾元素进行交换，此时末尾元素就是最大值
    int temp;
    for(int j=arr.length-1; j>0; j--) {
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        // 交换完后，将剩余的(n-1)个元素再调整成大顶堆
        buildHeap(arr, 0, j);
    }
}