课程名称:
物联网/嵌入式工程师
课程章节(阶段二第七周 堆排序之原理讲解 1-8):
堆排序之原理讲解课程链接
老师:
大白老师
课程内容:
学习常用排序中的堆排序
学习笔记:
概念:
-
堆是一种类似完全二叉树的数据结构，可以分为大顶堆，小顶堆，而堆排序就是基于这种结构而产生的一种程序算法。
-
大顶堆：每个节点的值都大于或则等于其左右孩子的值。
-
小顶堆：每个节点的值都小于或则等于其左右孩子的值。
-
堆排序：若是需要进行堆排序的代码，一定需要先把树构建成大顶堆或则小顶堆，然后在进行排序。
思路:
1.首先，将待排序的数组构造成一个大顶堆，此时，整个数组的最大值就是堆结构的顶端。
2.n为元素个数，将顶端的树与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个位为n - 1.
3.将剩余的n - 1个数再构造成大顶堆，在将顶端数与 n - 1位置的数交换，如此返回执行，便能得到有序数组。
打卡:
课程评价
本节主要讲解堆排序，对于堆排序，最重要的两个操作是构造初始化堆和重新调整堆。大白老师对堆排序的每个步骤讲的都很清楚，特别是对大根堆，小根堆的调整的讲解，很容易让人理解。