[数据结构与算法] 堆排序算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 堆排序算法 -> 正文阅读

[数据结构与算法]堆排序算法

堆排序思路

将一个无序序列构建成一个堆
将堆顶元素下沉到数组后面
将剩余的 n - 1 个元素重新调整成一个堆
继续将堆顶元素下沉
重复执行上诉操作，直到得到一个完整的有序序列为止

堆排序代码

import java.util.Arrays;

public class HeadSort {

    public static void main(String[] args) {
        int[] array = new int[]{3, 2, 5, 7, 4, 8, 15, 1};
        HeadSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] arr) {
        // 1.构建大顶堆
        buildHead(arr);

        // 2.交换堆顶元素和末尾元素，并重新调整堆结构（不包含沉到后面的元素哦）
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);      // 将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);   // 重新对堆进行调整
        }

    }

    // 构建堆（堆是在已有数组的基础上进行构建的）
    private static void buildHead(int[] arr){
        // 1.构建大顶堆，从最后一个非叶子结点开始
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            // 从最后一个非叶子结点自下而上，自左往右调整结构
            adjustHeap(arr, i, arr.length);
        }
    }


    // 调整堆结构
    public static void adjustHeap(int[] arr, int i, int len) {
        int left = 2 * i + 1;   // 左孩子的索引
        int right = 2 * i + 2;  // 右孩子的索引
        int maxIndex = i;  // 临时变量记录最大值的索引，初始时记录父节点的索引为最大值的索引

        if (left < len && arr[left] > arr[maxIndex]) {
            maxIndex = left;
        }

        if (right < len && arr[right] > arr[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex != i) {
        	// 若最大值在子孩子中，则交换它们的位置
            swap(arr, i, maxIndex);
            // 这一步为什么要递归调用，可能有初学者不太理解，我会解惑一栏中着重讲解
            adjustHeap(arr, maxIndex, len);
        }

    }


    // 交换元素
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}

代码解惑

// 调整堆结构
public static void adjustHeap(int[] arr, int i, int len) {
    // 省略. . .
    
    if (maxIndex != i) {
    	// 若最大值在子孩子中，则交换它们的位置
        swap(arr, i, maxIndex);
        // 这一步为什么要递归调用，可能有初学者不太理解，我会解惑一栏中着重讲解
        adjustHeap(arr, maxIndex, len);
    }

}

对于上诉 if 语句中，为什么交换了孩子节点和父节点的位置后，要进行递归调用？这里的递归调用起到了什么作用？

具体可以看我的另一篇文章自底向上的构建二叉堆，文中有关于这个问题得详细解析

算法分析

建堆的时间复杂度为 $O (n)$ ，遍历交换栈顶元素和尾部元素得时间复杂度为 $O (n)$ ，调整堆结构得时间复杂度为 $O (l o g n)$ ，总体时间复杂度为 $O (n l o g n)$
堆排序属于就地排序，空间复杂度为 $O (1)$
堆排序属于不稳定排序。因为在交换元素位置时，有可能会把后面的元素交换到前面去。