目录
直接选择排序
1.选择排序的基本思想
2.直接选择排序的基本思想
3.直接插入排序的代码思路步骤
4.直接选择排序代码
5.直接选择排序的特性总结
堆排序
一、排升序，建大堆
1.利用向上调整函数建大堆
1.1.建立大堆的思路
1.2.以下是具体步骤：
1.3.代码
2.利用向下调整函数建大堆
2.1.建立大堆的思路
2.2.代码思路步骤
2.3.利用向下调函数建大堆的案例
2.4.代码
3.建大堆排升序的思路
2.利用向上调整函数或者向下调整函数建大堆排升序
二、排降序，建小堆
1.利用向上调整函数建小堆
1.1.建立小堆的思路
1.2.以下是具体步骤：
1.3.代码
2.利用向下调整函数建小堆
2.1.建立大堆的思路
2.2.代码思路步骤
2.3.利用向下调函数建小堆的案例
编辑
2.4.代码
3.建大堆排升序的思路
2.利用向上调整函数或者向下调整函数建小堆排升序
三、堆排序的时间复杂度
1.利用向上调整函数建堆的时间复杂度
(1)对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析
(2)分析向上调整函数AdjustUp建堆的时间复杂度是O(N*logN )的原因
2.利用向下调整函数建堆的时间复杂度
(1)对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析
(2)分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因
3.堆排序的时间复杂度和空间复杂度
3.1.时间复杂度：O(N*logN)
(1)建立大堆过程的时间复杂度计算
(2)排序过程的时间复杂度计算
(3)对堆排序算法的时间复杂度是O(N*logN)的总结
3.2.空间复杂度：O(1)
3.3.稳定性：不稳定
直接选择排序
注意：下面都是以排升序为例进行说明的。
1.选择排序的基本思想
每一次从待排序的数据元素中选出最小的一个元素存放在序列的起始位置后待排序的数据就减少1个，然后重复上面步骤直到全部待排序的数据元素排完 。
图形解析：
2.直接选择排序的基本思想
注意：直接选择排序是对选择排序的优化。
每一次从待排序的数据元素中选出最小和最大的元素后，把最小元素存放在序列的起始位置而把最大元素存放到序列的末尾位置后待排序的数据就减少2个，重复上面步骤直到全部待排序的数据元素排完 。
3.直接插入排序的代码思路步骤
(1) 初始化两个指针，begin 指向待排序序列的起始位置，end 指向待排序序列的末尾位置。
(2) 在当前未排序的元素集合 a[begin] 到 a[end] 中，确定最小元素的索引 mini 和最大元素的索引 maxi。
(3) 将找到的最小元素 a[mini] 与 a[begin] 位置的元素进行交换。
(4) 在执行了步骤(3)的交换操作后，需要检查最大元素的索引 maxi 是否受到了影响：
- 如果最大元素的原始位置是 begin，而在步骤(3)的交换后，最大元素被移动到了 mini 位置，则需要将 maxi 更新为 mini。然后，将位于 maxi（现在等于 mini）的最大元素与 a[end] 位置的元素进行交换。
- 如果最大元素原本就不在 begin 位置，那么直接将 a[maxi] 与 a[end] 位置的元素进行交换。
(5) 将 begin 指针向后移动一位（begin++），将 end 指针向前移动一位（end–），以此来缩小待排序数据元素集合的范围，并排除已经排序的元素。
(6) 重复步骤(2)至(5)，直到 begin 大于或等于 end，此时表明所有元素都已按顺序排列。
注意：步骤(4)中的检查是必要的，因为在将最小元素与 a[begin] 位置的元素交换后，如果最大元素原本在 begin 位置，它会被交换到 mini 位置。因此，在交换最大元素之前，必须确保 maxi 指向正确的元素。
这个排序算法是一种双向选择排序的变种，它在每次迭代中同时找到最小和最大的元素，并将它们放置在正确的位置，然后缩小排序范围。
4.直接选择排序代码
//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{//1.初始化区间[begin，end]的范围int begin = 0, end = n - 1;//2.这个while (begin < end)循环的作用是：不断重复缩小区间[begin,end]的范围后再去找区间[begin,end]的最小值放到区间的最左边begin位置和找区间[begin,end]的最大值放到区间的最右边end位置这个操作，直到区间[begin,end]中的begin = end为止。while (begin < end)//注意：当begin = {//3.一开始假设区间下标begin位置的元素即使最大值也是最小值，并用mini和maxi记录区间下标begin位置int mini = begin, maxi = begin;//4.在区间[begin,end]中从头到尾找出区间中的最大值和最小值，并用maxi和mini分别记录最大值和最小值的下标for (int i = begin + 1; i <= end; ++i){//4.1.在区间[begin，end]中找出最小值if (a[i] < a[mini]){mini = i;}//4.2.在区间[begin,end]中找出最大值if (a[i] > a[maxi]){maxi = i;}}//写法1：//5.把区间[begin，end]中的最小值放到区间的最左边begin位置，而把区间中的最大值放到区间最右边end位置。//5.1.把区间[begin，end]最小值放到区间最左边begin位置Swap(&a[begin], &a[mini]);//注意：这个if (maxi == begin)语句的目的是为了防止区间最左边begin位置的元素是区间中的最大值，但是在通过Swap(&a[begin], &a[mini])函数把区间最小值元素放到区间最左边后进而使得此时//下标mini位置的元素才是区间中的最大值，所以此时必须更新maxi的值使得maxi可以指向此时位于mini位置的区间的最大值。if (maxi == begin)maxi = mini;//5.2.把区间[begin，end]最大值放大区间最右边end位置Swap(&a[end], &a[maxi]);//写法2：/*Swap(&a[end], &a[maxi]);//这个if(mini == end)语句的作用是为了防止区间最右边end位置是区间最小值，而Swap(&a[end], &a[maxi]函数把区间最大值元素放到区间最右边后进而使得此时//下标maxi位置的元素才是区间中的最小值，所以此时必须更新mini的值使得mini可以指向此时位于maxi位置的区间的最小值if (mini == end)mini = maxi;Swap(&a[begin], &a[mini]);*///6.更新区间[beign,end]的范围即缩小区间[beign,end]的范围。++begin;--end;}
}注意事项：
如果在代码中使用局部变量 max 和 min 来存放待排序序列中的最大元素和最小元素的值，而不是使用 maxi 和 mini 来存放它们的下标，将会导致以下问题：
-
无法正确交换元素：在找到最小和最大元素后，代码需要将它们放置到正确的位置。如果只有元素的值而没有它们在数组中的位置，就无法进行交换操作。因为交换需要知道元素在数组中的具体位置。
-
无法处理最大值或最小值重复的情况：如果最大值或最小值在数组中出现多次，仅记录值无法确定应该与哪个位置的元素进行交换。
-
代码逻辑不完整：原代码依赖于
maxi和mini来更新元素的位置，如果只记录值，那么在交换最小值后，原本最大值的位置可能发生变化（如果最小值原本在最大值的位置），这种情况下需要更新最大值的下标。如果没有下标，就无法进行这种更新。
5.直接选择排序的特性总结
(1) 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
(2) 时间复杂度：O(N^2)
(3)空间复杂度：O(1)
(4)稳定性：不稳定
(5)直接选择排序是所有排序算法中最差劲的算法。虽然直接选择排序算法和直接插入排序算法的时间复杂度一样，但是与直接选择排序算法相比反而是直接插入排序更好。直接插入排序算法的时间复杂度的多少和整个序列中数据的分布即是由局部有序或者近似有序有关。
分析：
①直接插入排序的适应性很强。若同时用直接插入排序算法和直接选择排序算法对局部有序或者近似有序的序列分别进行排序时，直接插入排序算法的效率更高且此时直接插入排序算法的时间复杂度一定小于O(N^2)。
②在任何情况下(即哪怕是对有序序列进行排序时)，直接选择排序的时间复杂度都是O(N^2)。
堆排序
一、排升序，建大堆
1.利用向上调整函数建大堆
1.1.建立大堆的思路
步骤1：初始化堆
- 将给定的数据序列（例如：数组）看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。
步骤2：向上调整函数
- 从完全二叉树根结点的第一个孩子结点开始按照从左至右且从上往下的顺序对完全二叉树每个结点执行向上调整操作直到完全二叉树最后一个结点完成向上调整操作为止，最终使其整个数据序列满足大堆的性质。
1.2.以下是具体步骤：
步骤1：找到根结点的第一个孩子结点
- 在一个完全二叉树中，根结点的第一个孩子结点的位置是 child = 1，其中
n是结点的总数。
步骤2：执行向上调整
- 从完全二叉树根结点的第一个孩子结点开始，依次向后遍历完全二叉树的每个结点。
- 对于每个结点，执行以下操作：
- 比较当前结点(即孩子结点)与其双亲结点的值。
- 如果当前结点(即孩子结点)的值大于其双亲结点的值，则交换当前结点(即孩子结点)与其双亲结点的值，然后对交换后位于双亲结点位置的孩子结点继续执行向上调整操作。
步骤3：重复步骤2直到完全二叉树最后一个结点完成向上调整操作
- 继续向后遍历完全二叉树并对每个结点执行向上调整，直到最后一个结点完成向上调整操作为止。
1.3.代码
//(利用向上调整函数建大堆。
int child = 0;
for (child = 1; child < n; child++)AdjustUp1(a, child);2.利用向下调整函数建大堆
2.1.建立大堆的思路
(1)初始化堆：将给定的数据序列(例如：数组)看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。
(1)向下调整函数：从最后一个孩子结点的双亲结点开始按照从右往左且从下往上的顺序对完全二叉树的每个结点执行向下调整操作直到完全二叉树的根结点完成向下调整操作为止，最终使其整个数据序列满足大堆的性质。
2.2.代码思路步骤
步骤1：找到最后一个孩子结点的双亲结点的位置
- 在一个完全二叉树中，最后一个孩子结点的双亲结点的位置是parent =
(n-1-1)/2，其中n是结点的总数。
步骤2：执行向下调整
- 从最后一个孩子结点的双亲结点开始，依次向前遍历完全二叉树的每个结点。
- 对于每个结点，执行向下调整操作：
- 比较当前双亲与其左右子孩子结点中最大孩子的值。
- 如果当前双亲结点的值小于最大孩子结点的值，则交换当前双亲结点与最大孩子结点的值，然后对交换后的位于最大孩子结点位置的双亲结点的值继续执行向下调整操作。
步骤3：重复步骤2直到完全二叉树的根结点完成向下调整操作。
- 继续向前遍历完全二叉树并对每个结点执行向下调整，直到完全二叉树的根结点完成向下调整操作为止。
2.3.利用向下调函数建大堆的案例
例1：在数组a没有变成大堆之前，一开始数组的元素是a[ ] = {1,3,8,5,4,6,9,2,7,10}。
图形解析：把数组a[ ] = {1,3,8,5,4,6,9,2,7,10}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点10的双亲结点4开始按照从右往左再从下往上的顺序对完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点1完成向下调整操作为止才结束。最终数组a变成a[ ] = {10,7,9,5,4,6,8,2,1}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。
注意：以下是整个完全二叉树的所有左右子树变成大堆的执行顺序① —>② —> ③—> ④—>⑤。
例2：在数组a没有变成大堆之前，一开始动态数组的元素是
a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}。
图形解析：把数组a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点31的双亲结点28开始按照从右往左再从下往上的顺序把完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点18完成向下调整操作为止才结束。最终数组a变成a[ ] = {49,37,31,27,21,21,30,15,16,20,18,20,18,15,28}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。
注意：以下是整个完全二叉树的左右子树变成堆的执行顺序① —>② —> ③—> ④—>⑤。
2.4.代码
//利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)AdjustDown1(a, n, parent);3.建大堆排升序的思路
① 构建大堆：首先，通过向下调整函数（而非向上调整，因为向下调整更高效）将原数组转换成一个大堆。这样，堆的根结点（即数组的第一个元素）将是数组中的最大值。
② 交换堆顶与堆尾元素：一旦大堆构建完成，将堆顶元素（数组的第一个元素）与堆的最后一个元素进行交换。这样，数组中的最大值就被放置到了数组的末尾。
③ 减少堆的大小：交换操作完成后，认为堆的最后一个元素已经排定，因此不再将其视为堆的一部分，从而将堆的大小减少1。
④ 维护大堆的性质：由于交换操作可能破坏了堆的性质，需要通过向下调整操作从新的堆顶开始，重新构建大堆。这一步骤确保了堆的根结点是剩余元素中的最大值。
⑤ 重复以上步骤：继续执行交换、减少堆大小、维护堆性质的步骤，直到堆的大小减少到只剩一个元素。此时，所有的元素都已经按升序排列。
总体来说，堆排序算法的思路是通过不断选出最大元素并将其放置到数组的末尾，同时维护剩余元素的大堆结构，以此来逐步构建一个升序数组。在每次选出最大元素后，都减少堆的大小，并利用向下调整操作来保持剩余元素的大堆性质，直到整个数组排序完成。
图形解析：下面是建完大堆后进行堆排序的过程。
2.利用向上调整函数或者向下调整函数建大堆排升序
代码：
//交换两个元素的函数
void swap(int* p1, int* p2)
{//判断指针p1与p2是否是空指针assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//建大堆
//(1)建大堆的向上调整
void AdjustUp1(int* a, int child)
{assert(a);//找当前孩子的双亲int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent])//若当前孩子比自己的双亲还有大，则当前孩子就要进行向上调整。{swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}//(2)建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{assert(a);//找当前双亲的左孩子int child = parent * 2 + 1;while (child < n){//让child始终指向当前双亲的左右孩子中最大一个孩子if (child + 1 < n && a[child + 1] > a[child])child++;if (a[child] > a[parent])//若当前双亲比最大一个孩子还有小，则当前双亲就要进行向下调整。{swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}//堆排序函数->在原数组中建大堆来排升序
void HeapSort1(int* a, int n)
{//判断指针a是否是空指针assert(a);//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建大堆的。//1.在原数组中建大堆//(1)利用向上调整函数建大堆。/*int child = 0;for (child = 1; child < n; child++)AdjustUp1(a, child);*///(2)利用向下调整函数建大堆int parent = 0;for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)AdjustDown1(a, n, parent);//2.利用大堆把原数组排成升序//思路：int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。while (k--){//(1)交换大堆堆顶元素和堆尾元素的值swap(&a[0], &a[n - 1]);//(2)不把处于数组尾部的堆顶元素看作是数组元素n--;//(3)利用向下调整操作保持数组剩余元素依然是个大堆AdjustDown1(a, n, 0);}}二、排降序，建小堆
1.利用向上调整函数建小堆
1.1.建立小堆的思路
步骤1：初始化堆
- 将给定的数据序列（例如：数组）看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。
步骤2：向上调整函数
- 从完全二叉树根结点的第一个孩子结点开始按照从左至右且从上往下的顺序对完全二叉树每个结点执行向上调整操作直到完全二叉树最后一个结点完成向上调整操作为止，最终使其整个数据序列满足小堆的性质。
1.2.以下是具体步骤：
步骤1：找到根结点的第一个孩子结点
- 在一个完全二叉树中，根结点的第一个孩子结点的位置是 child = 1，其中
n是结点的总数。
步骤2：执行向上调整
- 从完全二叉树根结点的第一个孩子结点开始，依次向后遍历完全二叉树的每个结点。
- 对于每个结点，执行以下操作：
- 比较当前结点(即孩子结点)与其双亲结点的值。
- 如果当前结点(即孩子结点)的值小于其双亲结点的值，则交换当前结点(即孩子结点)与其双亲结点的值，然后对交换后位于双亲结点位置的孩子结点继续执行向上调整操作。
步骤3：重复步骤2直到完全二叉树最后一个结点完成向上调整操作
- 继续向后遍历完全二叉树并对每个结点执行向上调整，直到最后一个结点完成向上调整操作为止。
1.3.代码
//(利用向上调整函数建小堆。
int child = 0;
for (child = 1; child < n; child++)AdjustUp2(a, child);2.利用向下调整函数建小堆
2.1.建立大堆的思路
(1)初始化堆：将给定的数据序列(例如：数组)看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。
(1)向下调整函数：从最后一个孩子结点的双亲结点开始按照从右往左且从下往上的顺序对完全二叉树的每个结点执行向下调整操作直到完全二叉树的根结点完成向下调整操作为止，最终使其整个数据序列满足小堆的性质。
2.2.代码思路步骤
步骤1：找到最后一个孩子结点的双亲结点的位置
- 在一个完全二叉树中，最后一个孩子结点的双亲结点的位置是parent =
(n-1-1)/2，其中n是结点的总数。
步骤2：执行向下调整
- 从最后一个孩子结点的双亲结点开始，依次向前遍历完全二叉树的每个结点。
- 对于每个结点，执行向下调整操作：
- 比较当前双亲与其左右子孩子结点中最小孩子的值。
- 如果当前双亲结点的值大于最小孩子结点的值，则交换当前双亲结点与最小孩子结点的值，然后对交换后的位于最小孩子结点位置的双亲结点的值继续执行向下调整操作。
步骤3：重复步骤2直到完全二叉树的根结点完成向下调整操作。
- 继续向前遍历完全二叉树并对每个结点执行向下调整，直到完全二叉树的根结点完成向下调整操作为止。
2.3.利用向下调函数建小堆的案例
例1：在数组a没有变成大堆之前，一开始数组的元素是a[ ] = {1,3,8,5,10,9,6,2,7,4}。
图形解析：把数组a[ ] ={1,3,8,5,10,9,6,2,7,4}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点4的双亲结点10开始按照从右往左再从下往上的顺序对完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点1完成向下调整操作为止才结束。最终数组a变成a[ ] = {1,2,6,3,4,9,8,5,7,10}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。
注意：以下是整个完全二叉树的所有左右子树变成小堆的执行顺序① —>② —> ③—> ④—>⑤。
2.4.代码
//利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)AdjustDown2(a, n, parent);3.建大堆排升序的思路
① 构建小堆：首先，通过向下调整函数（而非向上调整，因为向下调整更高效）将原数组转换成一个小堆。这样，堆的根结点（即数组的第一个元素）将是数组中的最小值。
② 交换堆顶与堆尾元素：一旦小堆构建完成，将堆顶元素（数组的第一个元素）与堆的最后一个元素进行交换。这样，数组中的最小值就被放置到了数组的末尾。
③ 减少堆的大小：交换操作完成后，认为堆的最后一个元素已经排定，因此不再将其视为堆的一部分，从而将堆的大小减少1。
④ 维护小堆的性质：由于交换操作可能破坏了堆的性质，需要通过向下调整操作从新的堆顶开始，重新构建小堆。这一步骤确保了堆的根结点是剩余元素中的最小值。
⑤ 重复以上步骤：继续执行交换、减少堆大小、维护堆性质的步骤，直到堆的大小减少到只剩一个元素。此时，所有的元素都已经按降序排列。
总体来说，堆排序算法的思路是通过不断选出最小元素并将其放置到数组的末尾，同时维护剩余元素的小堆结构，以此来逐步构建一个降序数组。在每次选出最小元素后，都减少堆的大小，并利用向下调整操作来保持剩余元素的小堆性质，直到整个数组排序完成。
图形解析：下面是建完小堆后进行堆排序的过程。
2.利用向上调整函数或者向下调整函数建小堆排升序
代码：
//交换两个元素的函数
void swap(int* p1, int* p2)
{//判断指针p1与p2是否是空指针assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//建小堆的向上调整
void AdjustUp2(int* a, int child)
{assert(a);//找当前孩子的双亲int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//若当前孩子比自己的双亲还有小，则当前孩子就要进行向上调整{swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}//建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{assert(a);//找当前双亲的左孩子int child = parent * 2 + 1;while (child < n){//让child始终指向当前双亲的左右孩子中最小的那个孩子if (child + 1 < n && a[child + 1] < a[child])child++;if (a[child] < a[parent])//若当前双亲比最小的孩子还有大，则当前双亲就要向下进行调整{swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}//堆排序函数->在原数组a中建小堆来排降序
void HeapSort2(int* a, int n)
{//判断指针a是否是空指针assert(a);//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建小堆的。//1.在原数组中建大堆//(1)利用向上调整函数建大堆。/*int child = 0;for (child = 1; child < n; child++)AdjustUp2(a, child);*///(2)利用向下调整函数建大堆int parent = 0;for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)AdjustDown2(a, n, parent);//2.利用大堆把原数组排成升序//思路：int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。while (k--){//(1)交换大堆堆顶元素和堆尾元素的值swap(&a[0], &a[n - 1]);//(2)不把处于数组尾部的堆顶元素看作是数组元素n--;//(3)利用向下调整操作保持数组剩余元素依然是个大堆AdjustDown2(a, n, 0);}}三、堆排序的时间复杂度
1.利用向上调整函数建堆的时间复杂度
(1)对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析
(2)分析向上调整函数AdjustUp建堆的时间复杂度是O(N*logN )的原因
完全二叉树层数低的结点少，而结点少的向上调整次数少；完全二叉树层数高的结点多，而结点多的向上调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向上调整函数建堆的时间复杂度高。总的来说，结点少的调整次数少，结点多的调整次数多。
2.利用向下调整函数建堆的时间复杂度
(1)对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：利用向下调整函数建堆的时间复杂度为O(N)。
(2)分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因
完全二叉树层数低的结点少，而结点少的向向下调整次数多；完全二叉树层数高的结点多，而结点多的向下调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向下调整函数建堆的时间复杂度低。总的来说，结点数量多的时候调整的次数少而结点少的时候调整次数多。
3.堆排序的时间复杂度和空间复杂度
堆排序使用堆来选数，效率就高了很多。
3.1.时间复杂度：O(N*logN)
以利用向下调整函数建大堆来排升序为例解析时间复杂度为O(N*logN)的原因：
(1)建立大堆过程的时间复杂度计算
①初始化堆的时间复杂度： 在建立大堆的过程中，我们需要从最后一个孩子结点的双亲结点非开始按照从右往左且从下往上的往前遍历完全二叉树并对每个结点执行向下调整操作。最后一个孩子结点的索引是 child = (n-1-1)/2，其中 n 是结点的总数。
②向下调整的时间复杂度： 对于每个结点，向下调整的时间复杂度是 O(logN)，因为最坏的情况下，双亲结点可能需要与每一层的孩子结点比较和交换，直到到达叶结点。完全二叉树的高度是 O(logN)。
③总的时间复杂度： 建立大堆的过程中，我们需要对大约一半的结点执行向下调整操作，即从下标(n-1-1)/2 到 下标0 的结点。因此，总的时间复杂度是：O(1) + O(2) + ... + O(logN-2) + O(logN-1) + O(logN) ，这可以近似为：O(N*logN)。因为对于每个层级，向下调整的时间复杂度是 O(logN)，而每一层的节点数大约是上一层的两倍。
(2)排序过程的时间复杂度计算
①排序的时间复杂度： 在建立大堆之后，我们开始排序过程。排序过程中，我们需要执行以下步骤 N-1 次（因为最后一个元素不需要再移动）：
- 将堆顶元素（最大值）与堆的最后一个元素交换，然后移除堆的最后一个元素（这实际上就是将最大值放置在正确的位置）。
- 对新的堆顶元素执行向下调整操作，以恢复大堆的性质。
②每次调整的时间复杂度： 每次向下调整操作的时间复杂度是 O(logN)，因为堆的高度是 O(logN)。
③总的时间复杂度： 因为我们需要对 N-1 个元素执行上述操作，所以排序过程的总时间复杂度是：O(logN) + O(logN) + ... + O(logN) (共 N-1 次)。这可以表示为：O((N-1)*logN) = O(N*logN)
(3)对堆排序算法的时间复杂度是O(N*logN)的总结
将建立大堆的时间复杂度 O(NlogN) 和排序的时间复杂度 O(NlogN) 结合起来，整个利用向下调整函数建大堆并排升序的过程的总时间复杂度仍然是 O(N*logN)。尽管建立大堆和排序是两个不同的步骤，但它们的时间复杂度是相同的，并且在总的时间复杂度计算中，排序步骤的时间复杂度起主导作用。