当前课程知识点：数据结构 > 第8章 排序 > 8.4 选择排序 > 讲解（下）
现在，我们来看具体的调整过程的实现
这是我们建立的大顶堆
它的根，就是这8个元素当中的最大值，也就是7
我们要进行调整
首先
我们交换根和最后一个元素
也就是，把7放到最下的位置
新的根是1
然后，我们对这样一棵完全二叉树，进行调整
以便找到次大值
那怎么找呢
首先
我们用low来指向要调整的树
它的第一个结点，high指向要调整的树的最后一个结点
也就是，序列的下界和上界
我们交换了根和最后一个元素之后
除了r[low]之外
剩下的那些结点，它们是满足大顶堆的性质的
比如这棵子树
它确实是满足大顶堆性质的
这棵子树也是的
因为，这两棵子树就是原来的初始堆的两棵子树
我们仅仅交换的是根结点和最后一个结点，交换之后
它并不会破坏这两棵子树的性质
也就是说
除了r[low]之外
剩下的结点，是满足大顶堆的性质的
我们现在就要进行调整
下界是low
上界是high
然后，我们用一个临时的变量root来存放
当前的下界，也就是树的根
那么，root它实际上是等于1的
因为，low指向1
继续往后，for循环，i从2*low开始
2*low是什么东西呢
low是指向1(值)的，它的初值是1(下标)
high是指向这个4，因为，初始堆建立完毕之后，最大值我们找出来了
没必要再管这个结点了
所以，high指向倒数第二个结点
现在，i等于2*low
我们把它们编号
i指向这个5
然后
i小于等于high
每次循环完毕之后
i自乘2
i自乘2，是什么意思呢
现在，i指向5这个结点，也就是i等于2
i自乘2，i会指向4这个结点
而4
恰好是5的左孩子
说明，这个for循环
它就是一直向下去找，去进行筛选
因为我在交换父结点和子结点的过程当中
可能会影响它的子树，不满足大顶堆的性质
所以，要继续向下筛选
紧接着，是一个if语句
第一个条件
是i 这个条件的作用，我们待会再说 我们先看第二个条件 r[i]小于r[i+1]，i指向5，i+1指向6 我们判断i+1和i指向的结点大小关系，这两个结点有什么样的关系呢 我们会发现，i和i+1指向的结点，恰好是 low指向的那个结点的左右孩子 也就是说，low的右孩子是i+1，也就是2*low+1 这完全是来自于我们前面讲的完全二叉树的性质 现在，我们判断左孩子和右孩子的大小关系 如果左孩子小于右孩子 我们将i自增 也就是，让i指向较大的那个孩子 现在，5小于6，那么i应该指向6 我们始终用i，指向low为父结点的 两个孩子当中，最大的那个孩子 然后，我们去判断当前的父结点 也就是low指向的这个结点 它和最大的那个孩子之间的大小关系 如果父结点都比最大的孩子要大 我们就没必要进行向下筛选的过程了 因为，我们现在建立的是大顶堆 根比孩子要大，没必要筛选了 所以这地方，if控制的是一个break 跳出这个循环 现在，1是小于6的，大于等于不成立 继续往下执行 现在，我们就应该进行交换 将较大的那个值，赋值给low 也就是 将r[i]的6，赋值给low指向的这个元素 我们把1修改成6，1被覆盖掉了 所以在之前，我们用root来暂存之前的这个low 紧接着 将low修改成i i是指向这个6的，low也指向这个6 我们进入下一次循环 实际上 这次赋值，完全是为了继续筛选以i为根的树，向下筛选 因为，你把6赋值上去了之后 你还要继续筛选 它的子树 现在，我们继续看，i自乘2 i是3，自乘2，是6 现在，i指向3这个结点，也就是6的左孩子 然后 判断i是否小于它的右孩子 i+1在这里 现在，3是小于这个右孩子的 那么，i就自增，指向6的右孩子4 再去判断 root是否大于等于i指向的4 现在，这个条件依然是不满足的 不满足，我们就要执行将r[i]赋值给r[low] r[i]是4，赋值给r[low] 那么，4放到这里 因为，1即将放下来 1是小于4的 所以，4要上移 我们建立的是大顶堆 然后 将low修改成i 它指向4，再回去，i再自乘2 i再自乘2，会超过high 所以循环退出，循环退出的时候 注意，循环退出要执行这个语句 那我们应该将暂存的这个root 赋值到low的位置 low在这里，root是1 最终，1就放在这里 从而，我们筛选出了次大值6 它是作为树的新的根的 现在，我们再回过头看一下，这个语句它的作用 按理说 这个for循环，它的第二个表达式，已经有i小于等于high了 我们在进入这个for循环的时候 也就是，执行这个if语句的时候 为什么还要判断i是否小于等于high呢 因为，这个if语句是判断 r[i]和它的右兄弟之间的大小关系 那么，什么时候，i没有右兄弟呢 比如，我们现在的树，是这样的 low指向根结点 那么，2*low 是它的左孩子，也就是i 现在，low没有右孩子 这时候，去找i+1，实际上是没有意义的 也就是说，这时候的high 最后一个结点 其实和i是相等的 也就是说，i要小于high的时候，low才可能有右孩子 你才能去比较i和i+1这个结点的大小关系 所以，我们在这里要加一个限定 这是调整的具体实现 现在，我们来看完整的堆排序算法 刚才我们写的代码 现在就忽略掉，放到上面，完整的代码 heapSort(堆排序)，对L进行堆排序 首先，我们要建立初始堆 那么，我们从最后一个非叶结点开始 刚才讲的，建立初始堆，从最后一个非叶结点 也就是，编号为n/2向下取整的那个结点 从下往上，i-- 逐个调整 初始堆建立完毕了之后 第二个for循环 去开始做n-1趟筛选 i从n开始，最后一个值是2 一共是n-1趟 这里，很明显是交换r[i]和r[1] r[1]它就是整棵树的根 它已经是最大值了 树的根已经是最大值了 现在，我们就交换根和最后一个结点r[i] 因为，i是从n开始的 我们第一次交换的，就是r[1]跟r[n] 第二次，就交换r[1]跟r[n-1] 然后，重复刚才的调整过程 下界永远是1，上界呢 因为，上一轮找出了当前的最大者之后 放到树的最后 我们就没必要再去管这个结点了 所以，上界是不断地减小 这就是完整的堆排序 现在，我们来分析它的时间复杂度 这个算法 第一个for循环，一共执行了n/2向下取整这么多次 下面这个for循环，一共执行n-1次 循环体都是我们之前讲的调整算法 因为，树是完全二叉树 前面讲过，完全二叉树的深度 它是这个量级 所以，最终的时间复杂度 就是n*log2(n) 所采用的临时空间只有1个 用来交换的，就是O(1) 堆排序它是不稳定的 因为，我们在交换父结点和子结点的过程当中 很有可能跳过与之相同的关键字 所以，堆排序算法是不稳定的
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
