排序算法之堆排序

一：概述

堆排序是在二叉堆的基础上实现的，如果想要学习堆排序，就得掌握二叉堆。二叉堆的特性是：最大堆的堆顶是整个堆中最大的元素。最小堆的堆顶是整个堆中最小的元素。

二：具体说明

<1>以最大堆为例讲述

如果要删除一个最大堆的堆顶(并不是完全删除，而是跟末尾的节点交换位置)，经过自我调整，第2大元素就会被交换上来，成为最大堆的新堆顶。

如上图所示，在删除值为10的堆顶节点后，经过调整，值为9的新节点就会顶替上来，在删除值为9的堆顶节点之后，经过调整。值为8的新节点就会顶替上来....由于二叉堆的这个特性，每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合，过程如下：

《1》删除节点9，节点8成为新堆顶。

《2》删除节点8，节点7成为新堆顶。

《3》删除节点7，节点6成为新堆顶。

《4》删除节点6，节点5成为新堆顶。

《5》删除节点5，节点4成为新堆顶。

《6》删除节点4，节点3成为新的堆顶。

《7》删除节点3，节点2成为新堆顶。

到此为止，原本的最大二叉堆已经变成了一个从小到的有序集合。之前说过，二叉堆实际存储在数组中，数组中的元素排列如下。

因此堆排序的算法步骤为：

• 把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
• 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

<2>代码实现

/**
     * “下沉”调整
     *
     * @param array       待调整的堆
     * @param parentIndex 要“下沉”的父节点
     * @param length      堆的有效长度
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        // temp保存父节点的值，用于最后的赋值
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子大于左孩子的节点值，则定位到右孩子
            if (childIndex + 1 > length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，则直接跳出
            if (temp >= array[childIndex])
                break;
            // 无须真正交换，单项赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
          array[parentIndex] = temp;
    }

    /**
     * 堆排序(升序)
     * @param array 待调整的堆
     */
    public static void heapSort(int[] array) {
        // 1.把无序数组构建成最大堆
        for(int i = (array.length-2)/2; i >= 0; i-- ) {
         downAdjust(array, i, array.length);
        }
        System.out.println(Arrays.toString(array));
        // 2.循环删除堆顶元素，移到集合的尾部，调整堆产生新的堆顶
        for(int i = array.length - 1; i > 0; i-- ) {
           //  最后一个元素和第一个元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
           // "下沉"调整最大堆
           downAdjust(array, 0, i);
        }
    }

    public static void main(String[] args) {
            int[] arr = new int[] {1, 3, 23, 6, 5, 7, 8, 9, 10, 0, 23, 56, 100};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
    }
}

对于上述这个算法，它的空间复杂度是O(1)，因为并没有额外开辟集合空间。

时间复杂度的分析：

二叉堆的节点“下沉”调整(downAdjust)方法是堆排序的算法基础.这个调节操作本身的时间复杂度是O(logn)。

堆排序的算法步骤：

1. 把无序的数组构建成二叉堆。
2. 循环删除堆顶元素，并将该元素移动到集合的尾部，调整堆产生的新的堆顶。

• 第一步：把无序的数组构建成二叉堆。这一步的时间复杂度是O(n).
• 第二步：需要进行n-1次循环。每次循环调用一次downAdjust方法，所以第2步的计算规模是(n -1)xlogn。时间复杂度是O(nlogn)
• 两个步骤是并列关系哦，所以整体的时间复杂度是O(nlogn)。

<3>堆排序和快速排序的区别和联系

相同点：堆排序和快速排序的平均时间复杂度O(nlogn)，并且都是不稳定排序。

不同点：快速排序的最坏时间复杂度是O(n^2)，而堆排序的最坏时间复杂度稳定在O(nlogn).

此外，快速排序递归和非递归方法的平均时间复杂度都是O(logn)。而堆时间的空间复杂度是O(1)。