===============
== 大程熙 ==
===============
一个小学生

算法之堆排序学习

堆排序算法重新学习。

选择排序,每一趟从未排序序列中选择出最小元素,将元素放到已排序序列尾部。

选择排序算法有以下几种:

  • 直接选择排序
  • 堆排序

堆排序算法

堆排序则是利用堆这种数据结构进行排序。需要先了解下堆的定义。

堆是一个完全二叉树,每个结点的值都大于等于(或者小于等于)其左右子结点的值。

堆分为大顶堆和小顶堆,大顶堆是每个结点的值都大于等于左右子结点的值,也就是堆顶是最大值。小顶堆是每个节点值都小于等于左右结点的值,也就是堆顶是最小值。一般排序如果是按照从大到小排序(降序)可以使用小顶堆;如果是按照从小到大排序(升序)可以使用大顶堆。

堆可以使用数组来表示,映射到数组后假设数组中索引i为当前结点,则有如下:

  • 左子结点为:2i + 1
  • 右子结点为:2i + 2
  • 父结点为:(i - 1) / 2
  • 最后一个非叶子结点为:array.length / 2 - 1

堆排序算法描述

堆排序算法(升序,大顶堆)描述如下:

  1. 将无序序列构造成大顶堆
  2. 将堆顶元素和未排序序列最后一个元素进行交换
  3. 调整大顶堆,继续2、3步骤

堆排序代码示例

/**
     * 堆排序
     * 1. 将无序序列构造成大顶堆
     * 2. 将堆顶元素和未排序序列最后一个元素进行交换
     * 3. 调整未排序序列的大顶堆后,继循环2、3步
     *
     * 结点索引为i,则左子结点索引为2i + 1,右子结点索引为2i + 2,
     * 父节点索引为(i - 1) / 2
     * 最后一个非叶结点索引为:(array.length / 2) - 1
     * @param source
     */
    public void heapSort(Integer[] source) {

        // 构造大顶堆,从最后一个非叶结点开始
        for (int i = (source.length >> 1) - 1; i >= 0; i--) {
            adjustHeap(source, i, source.length - 1);
        }

        for (int i = source.length - 1; i > 0; i--) {
            // 交换堆顶和最后一个元素
            swap(source, 0, i);

            // 调整剩余未排序序列的大顶堆
            adjustHeap(source, 0, i - 1);
        }

    }

    /**
     * 以start为根的子树调整成大顶堆
     * @param source
     * @param start
     * @param end
     */
    private void adjustHeap(Integer[] source, int start, int end) {
        Integer temp = source[start];

        // 从当前元素的左子结点开始遍历
        for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {
            // 如果左子结点比右子结点小,则将i指向右子结点
            if (i + 1 <= end && source[i] < source[i + 1]) {
                i++;
            }

            // 到这里i指向左右子结点中大的那个结点
            // 比较大的结点和父结点进行比较,如果比父结点大,需要放到父结点位置上去
            if (source[i] > temp) {
                // 比父结点大的元素,放到父结点位置上
                source[start] = source[i];
                start = i;
            } else {
                break;
            }
        }

        // 遍历完后,将temp元素放到最终位置
        source[start] = temp;
    }

    private void swap(Integer[] source, int i, int j) {
        Integer temp = source[i];
        source[i] = source[j];
        source[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.println("before: " + Arrays.asList(array));
        new HeapSort().heapSort(array);
        System.out.println("after: " + Arrays.asList(array));
    }

堆排序算法分析

时间复杂度

  • 时间复杂度为$O(nlog_{2}n)$

空间复杂度

空间复杂度为O(1)

算法的稳定性

堆排序算法是不稳定的。

适用场景

  • 数据较多的时候,可以使用堆排序,堆排序所需的辅助空间少于快排。

参考内容

  • 《数据结构(Java版)》