【算法系列 | 6】深入解析排序算法之——堆排序

序言

��只管努力，其他交给时间，时间会证明一切。

文章标记颜色说明：

• 黄色：重要标题
• 红色：用来标记结论
• 绿色：用来标记一级论点
• 蓝色：用来标记二级论点

  决定开一个算法专栏，希望能帮助大家很好的了解算法。主要深入解析每个算法，从概念到示例。

  我们一起努力，成为更好的自己！

  今天第3讲，讲一下排序算法的堆排序（Heap Sort）

  1 基础介绍

  排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

  以下是一些常见的排序算法：

  1. 冒泡排序（Bubble Sort）

  2. 插入排序（Insertion Sort）

  3. 选择排序（Selection Sort）

  4. 归并排序（Merge Sort）

  5. 快速排序（Quick Sort）

  6. 堆排序（Heap Sort）

  一、堆排序介绍

  1.1 原理介绍

  堆排序（Heap Sort）是一种基于堆数据结构的排序算法，其核心思想是将待排序的序列构建成一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再将剩余元素重新调整为最大堆（或最小堆），重复以上步骤直到所有元素都有序。

  堆是一种特殊的二叉树，满足以下两个条件：

  1. 堆是一棵完全二叉树，即除了最后一层，其他层都是满的，最后一层的节点都靠左排列。

  2. 对于最大堆，任何一个父节点的值都大于（或等于）其左右子节点的值，对于最小堆，则是任何一个父节点的值都小于（或等于）其左右子节点的值。

  堆排序的实现过程如下：

  1. 构建堆：首先将待排序的序列构建成一个最大堆（或最小堆），可以从最后一个非叶子节点开始，从右至左，从下至上依次将每个节点调整为符合堆的性质。

  2. 堆排序：将堆顶元素与最后一个元素交换，然后将剩余元素重新调整为最大堆（或最小堆），再次将堆顶元素与倒数第二个元素交换，如此循环直到排序完成。

  细节讲解 

  具体的实现细节如下：

  1. 构建堆：从最后一个非叶子节点开始，依次将每个节点调整为符合堆的性质。对于一个节点，如果它的左右子节点中有一个大于（或小于）该节点，则交换它们的位置，然后递归调用该节点所在的子树，直到该节点不再有子节点或者其子节点都满足堆的性质为止。

  2. 堆排序：将堆顶元素与最后一个元素交换，然后将剩余元素重新调整为最大堆（或最小堆），再次将堆顶元素与倒数第二个元素交换，如此循环直到排序完成。

  1.2 复杂度 

  堆排序：

  • 时间复杂度为 $O(n\log n)$
  • 空间复杂度为 $O(1)$

    相对于其他的排序算法，其实现简单，但需要额外的空间来存储堆数据结构。

    1.3使用场景

    堆排序使用场景堆排序的使用场景与其他排序算法类似，适用于需要对大量数据进行排序的场景。

    1.4 优缺点 

    优点：

    其优点主要包括：

    1. 时间复杂度较低：堆排序的时间复杂度为 $O(n\log n)$，相对于其他排序算法，其排序速度较快。

    2. 不占用额外空间：堆排序是一种原地排序算法，不需要额外的空间来存储排序结果。

    3. 适用于大数据量的排序：堆排序的时间复杂度不随数据量的增加而变化，因此适用于大数据量的排序。

    缺点：

    堆排序的缺点主要包括：

    1. 不稳定性：由于堆排序是通过交换元素来实现排序的，因此在排序过程中可能会破坏原有的相对顺序，导致排序结果不稳定。

    2. 实现复杂：相对于其他排序算法，堆排序的实现稍微复杂一些，需要理解堆数据结构的基本原理和实现过程。

    因此，堆排序适用于需要对大量数据进行排序的场景，特别是在数据量较大、内存有限的情况下，堆排序可以通过原地排序的方式，节省额外空间的使用。

    二、代码实现

    2.1 Python 实现

    下面是 Python 实现堆排序的示例代码：

    def heap_sort(arr):    n = len(arr)        # 构建最大堆    for i in range(n // 2 - 1, -1, -1):        heapify(arr, n, i)        # 排序    for i in range(n - 1, 0, -1):        # 将堆顶元素与最后一个元素交换        arr[0], arr[i] = arr[i], arr[0]        # 调整剩余元素为最大堆        heapify(arr, i, 0)def heapify(arr, n, i):    # 将以 i 为根节点的子树调整为最大堆    largest = i  # 初始化最大元素为根节点    left = 2 * i + 1  # 左子节点的索引    right = 2 * i + 2  # 右子节点的索引    # 找出左右子节点中的最大值    if left  arr[largest]:        largest = left    if right  arr[largest]:        largest = right    # 如果最大值不是根节点，则交换根节点和最大值，并递归调整子树    if largest != i:        arr[i], arr[largest] = arr[largest], arr[i]        heapify(arr, n, largest)

    测试

    下面是 Python 实现堆排序的测试代码：

    arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]print("Before sorting:", arr)heap_sort(arr)print("After sorting:", arr)

    在上面的测试代码中，定义了一个整数数组 arr，并将其传递给 heap_sort 函数进行排序。

    排序完成后，使用 print 函数将排序后的数组输出到控制台。运行测试代码，将得到以下输出结果：

    Before sorting: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]After sorting: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

    可以看到，排序后的数组已经按照从小到大的顺序排列。

    2.2Java实现

    下面是 Java 实现堆排序的示例代码：

    public static void heapSort(int[] arr) {    int n = arr.length;    // 构建最大堆    for (int i = n / 2 - 1; i >= 0; i--) {        heapify(arr, n, i);    }    // 排序    for (int i = n - 1; i > 0; i--) {        // 将堆顶元素与最后一个元素交换        int tmp = arr[0];        arr[0] = arr[i];        arr[i] = tmp;        // 调整剩余元素为最大堆        heapify(arr, i, 0);    }}public static void heapify(int[] arr, int n, int i) {    // 将以 i 为根节点的子树调整为最大堆    int largest = i;  // 初始化最大元素为根节点    int left = 2 * i + 1;  // 左子节点的索引    int right = 2 * i + 2;  // 右子节点的索引    // 找出左右子节点中的最大值    if (left  arr[largest]) {        largest = left;    }    if (right  arr[largest]) {        largest = right;    }    // 如果最大值不是根节点，则交换根节点和最大值，并递归调整子树    if (largest != i) {        int tmp = arr[i];        arr[i] = arr[largest];        arr[largest] = tmp;        heapify(arr, n, largest);    }}

    测试

    下面是 Java 实现堆排序的测试代码：

    import java.util.Arrays;public class HeapSortTest {    public static void main(String[] args) {        int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };        System.out.println("Before sorting: " + Arrays.toString(arr));        heapSort(arr);        System.out.println("After sorting: " + Arrays.toString(arr));    }}

    在上面的测试代码中，定义了一个整数数组 arr，并将其传递给 heapSort 方法进行排序。排序完成后，使用 Arrays.toString 方法将排序后的数组输出到控制台。

    运行测试代码，将得到以下输出结果：

    Before sorting: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]After sorting: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

    可以看到，排序后的数组已经按照从小到大的顺序排列。

    图书推荐

    图书名称：

    • 精通Hadoop3
    • pandas1.X实例讲解
    • 人人都离不开的算法——图解算法应用
    • Python数据清洗

      精通Hadoop3

      pandas1.X实例讲解

      人人都离不开的算法——图解算法应用

      Python数据清洗

      活动说明

         618，清华社 IT BOOK 多得图书活动开始啦！活动时间为 2023 年 6 月 7 日至 6 月 18 日，清华社为您精选多款高分好书，涵盖了 C++、Java、Python、前端、后端、数据库、算法与机器学习等多个 IT 开发领域，适合不同层次的读者。全场 5 折，扫码领券更有优惠哦！快来京东点击链接 IT BOOK 多得，查看详情吧！

      活动链接：IT BOOK

      ​ 

      参与方式 

      图书数量：本次送出 3 本   ！！！⭐️⭐️⭐️

      活动时间：截止到 2023-06-16 12:00:00

      抽奖方式：

      • 评论区随机抽取小伙伴！

        留言内容，以下方式都可以：

        • 根据文章内容进行高质量评论

          参与方式：关注博主、点赞、收藏，评论区留言 

          中奖名单 

          获奖名单

           中奖名单：请关注博主动态

          名单公布时间：2023-06-16 下午

          名单详情：https://bbs.csdn.net/topics/615944050