十大经典排序算法-堆排序

编程算法

发布日期: 2020-11-09

文章字数: 848

阅读时长: 3 分

前言

本文重点讲解十大经典排序算法的堆排序

要点

堆排序是由1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特.弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明。
堆排序（Heap Sort），是指利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质。
堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

基本思想

将待排序序列构造成一个大顶堆（或小顶堆），此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。

基本操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

代码实现

以下代码由java实现

public class HeapSort {

    /**
     * 堆排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr, int n) {
        if (n <= 0) {
            return null;
        }
        int i;
        // 建堆 (i等于根节点(最顶父节点))
        for (i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 排序
        for (i = n - 1; i > 0; i--) {
            swap(arr, i, 0);
            heapify(arr, i, 0);
        }
        return arr;
    }

    /**
     * 维护堆的性质
     * @param arr
     * @param n
     * @param i
     * @return
     */
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int lson = i * 2 + 1;
        int rson = lson + 1;

        if (lson < n && arr[largest] < arr[lson]) {
            largest = lson;
        }
        if (rson < n && arr[largest] < arr[rson]) {
            largest = rson;
        }
        if (largest != i) {
            // 左右节点有比largest大,进行交换
            swap(arr, largest, i);
            // 递归维护堆的性质
            heapify(arr, n, largest);
        }
    }

    /**
     * 交换位置
     */
    public static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23};
		System.out.println(Arrays.toString(sort(arr, arr.length)));
    }
}

时间性能

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。
其中构建初始堆经推导复杂度为$O(n)$。
在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…]逐步递减，近似为$O(nlogn)$。
所以堆排序时间复杂度一般认为就是$O(nlogn)$级。