数据结构 选择排序PPT学习课件

选择排序 Selectionsort 1 选择排序 Selectionsort 是以选择为基础的一种常用排序方法 从记录的无序子序列中 选择 关键字最小或最大的记录 并将其加入到有序子序列的一端 以增加记录的有序子序列的长度 它也有几种不同的实现方法 这里仅介绍简单选择排序 树形排序和堆排序 2 1 简单选择排序 1 算法描述简单选择排序算法的基本思路 对于一组关键字 Kl K2 Kn 将其由小到大进行排序 首先从Kl K2 Kn中选择最小值 假设是Kk 则将Kk与K1对换 然后从K2 K3 Kn中选择最小值Kk 1 再将Kk 1与K2对换 如此进行选择和调换 对第i趟选择排序 进行n i次关键字比较 从n i 1个记录中选出关键字最小的记录 并与第i个记录交换 令i从1至n 1 进行n 1趟选择排序 一个由小到大的有序序列就形成了 3 例1设有一组关键字 49 39 66 49 76 11 27 96 这里n 8 试用简单选择排序方法 将这组记录由小到大进行排序 其排序过程如图所示 4 算法实现如下 voidSelectSort SqList SelectSort 5 2 算法分析在简单选择排序中 无论待排序的记录初始序列是否有序 都需要执行n n 1 2次关键字的比较操作 如果待排序的记录初始序列就是已经排好序的正列 则无须移动记录 因为每个元素都位于其最终位置上了 而如果待排序的记录初始序列是逆序 即在最坏情况下 则要做3 n 1 次记录移动 所以 简单选择排序的时间复杂度是O n n 由上面的例1很显然看到 49在排序前位于49 的前面 而经简单选择排序后却位于49 后面了 它们的相对位置发生了颠倒 因此简单选择排序算法是不稳定排序算法 6 3 堆排序 1 堆的定义堆是一个记录序列 k1 k2 kn 对于列表中位置i 编号从1开始 处的记录的关键字ki 当且仅当满足下列关系时 称之为堆 ki k2i或ki k2iki k2i 1ki k2i 1 i 1 2 n 2 其中 每个结点关键字都不小于其子孙结点关键字的堆称为 大根堆 而每个结点关键字都不小于其子孙结点关键字的堆称为 小根堆 下面的讨论中以小根堆为例 7 判断下列序列是否为堆 100 85 98 77 80 60 82 40 20 15 67 100 98 85 82 80 77 60 40 20 15 67 15 20 40 60 67 77 80 82 85 98 100 8 我们已经知道 对于一棵有n个结点的完全二叉树 当它的结点由上而下 自左至右编号之后 编号为1 n 2 的结点为分支结点 编号大于 n 2 的结点为叶子结点 对于每个编号为i的分支结点 它的左孩子的编号为2i 它的右孩子的编号为2i 1 对于每个编号为i i 1 的结点 它的双亲的编号为 i 2 因此 我们还可以借助完全二叉树来描述堆的概念 若完全二叉树中任一非叶子结点的值均小于等于 或大于等于 其左 右孩子结点的值 则从根结点开始按结点编号排列所得的结点序列就是一个堆 9 10 2 算法描述堆顶记录对应完全二叉树的根结点 堆顶记录关键字是所有记录关键字的最值 堆排序就是利用堆的上述特征完成排序的 在输出堆顶的最大 或最小 之后 使得剩余的n 1个记录的序列重新调整为一个堆 于是又得到次大 或次小 值 如此反复执行 直至所以记录都排序为一个有序序列 这就是堆排序 HeapSort 11 由于初始记录序列不一定满足堆关系 因此堆排序过程大体分两步处理 初建堆 从堆的定义出发 先取i n 2 它一定是第n个结点双亲的编号 将以i结点为根的子树调整成为堆 然后令i i 1 再将以i结点为根的子树调整成为堆 此时可能会反复调整某些结点 直到i 1为止 堆初建完成 堆排序 首先输出堆顶元素 一般是最小值 让堆中最后一个元素上移到原堆顶位置 然后恢复堆 因为经过第一步输出堆顶元素的操作后 往往破坏了原来的堆关系 所以要恢复堆 重复执行输出堆顶元素 堆尾元素上移和恢复堆的操作 直到全部元素输出完为止 按输出元素的前后次序排列 就形成了有序序列 完成了堆排序的操作 12 例设有n个记录 n 8 的关键字是 30 50 60 35 86 10 40 45 试用堆排序方法 将这组记录由小到大进行排序 13 第一步 初始建堆 其建堆过程如图所示 因为n 8 所以从i 4开始 14 第二步 堆排序 这是一个反复输出堆顶元素 将堆尾元素移至堆顶 再调整恢复堆的过程 恢复堆的过程与初建堆中i 1时所进行的操作完全相同 请注意 每输出一次堆顶元素 堆尾的逻辑位置退1 直到堆中剩下一个元素为止 排序过程如图所示 15 16 输出序列 1030354045506086 17 由上可知 调整恢复堆操作过程要被多次反复调用 即当i值确定之后 以ki为比较参照值 与其左 右孩子的关键字比较和调整 使以结点i为根的子树成为堆 因此把此过程设计成函数Heap voidHeap RedTyper inti intm i是根结点编号 m是以i结点为根的子树的最后一个结点编号 x r i j 2 i x保存根记录的内容 j为左孩子编号 while j m if j m r j key r j 1 key j 当结点i有左 右两个孩子时 j取关键字值较小的孩子结点编号 if r j key x key r i r j i j j 2 i 向下一层探测 elsej m 1 x key小于左 右孩于的关键字 强制使j m 以便结束循环 r i x Heap 18 另外 还需要设计一个主体算法 使在初建堆阶段 让i从 n 2 变化到1 循环调用heap函数 而在堆排序阶段 每输出一次堆顶元素 将堆尾元素移至堆顶之后 就要调用一次heap函数来恢复堆 主体算法由函数Heapsort来实现 voidHeapsort RedTyper intn n为文件的实际记录数 r o 没有使用 for i n 2 i 1 i Heap r i n 初建堆 for v n v 2 v x r 1 r 1 r v r v x 堆顶堆尾元素对换 Heap r 1 v 1 本次比上次少处理一个记录 Heapsort 19 3 算法分析在堆排序图示例中 堆越画越小 堆中结点越来越少 实际上 在用来存储堆的数组中堆顶元素输出之后并未删除 而是与堆尾元素对换 从图示看输出的是一个由小到大的升序序列 实际最后数组中记录的关键字从r l key到r n key是一个由大到小的降序序列 算法Heap的时间复杂度与堆所对应的完全二叉树的树深log2n相关 而算法Heapsort中对Heap的调用数量级为n 所以整个堆排序的时间复杂度为O nlog2n 20 稳定性如何 21 判断下列序列是否为堆 若不是 则把