《数据结构》-第十章d选择排序

1,第十章 内部排序,10.1 概述,10.2 插入排序,10.2.1 直接插入排序,10.2.2 其他插入排序,10.2.3 希尔排序,10.3 快速排序,10.4 选择排序,10.4.1 简单选择排序,10.4.2 树形选择排序,10.4.3 堆排序,10.5 归并排序,10.6 基数排序,10.6.1 多关键字的排序,10.6.2 链式基数排序,10.7 各种内部排序方法的比较讨论,2,四、选择排序,两种常见的选择排序,直接选择排序堆排序,基本原理: 将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。,3,直接选择排序的基本过程,在一组对象Vi到Vn-1中选择具有最小关键字的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。,4,直接选择排序示例,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,5,（1）算法实现： 一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1in）个记录交换之。 对L.r1.n中记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作，如算法10.9所示。,算法10.9如下： void SelectSort (SqList /与第i个记录交换 / for / SelectSort,6,（2）简单选择排序的改进,选择排序的主要操作是进行关键字间的比较。因此改进简单选择排序应减少“比较”。,显然，在n个关键字中选出最小值，至少进行n-1次比较，若能利用前n-1次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。,例如，在8个运动员中决出前3名至多需要11场比赛，而不是7+6+5=18场比赛（前提：若乙胜丙，甲胜乙，则认为甲必能胜丙）。,7,10.4.2 树形选择排序,例如，图10.8(a)中的二叉树表示从8个关键字中选出最小关键字的过程。8个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等于其左、右孩子结点中较小的关键字，则根结点中的关键字即为叶子结点中的最小关键字。,(a) 选出最小关键字为13,8,(b) 选出次小关键字为27,(c) 选出居第三的关键字为38,图10.8 树形选择排序示例,在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字（13）改为“最大值”，然后从该叶子结点开始，和其左（或右）兄弟的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点即为次小关键字。同理,可依次选出从小到大的所有关键字。如图10.8(b)和 (c)所示。,9,10,10.4.3 堆排序,堆的定义如下：n个元素的序列k1, k2, , kn当且仅当满足以下关系时，称之为堆。,（1）定义,例如，下列两个序列为堆96，83，27，38，11，09，12，36，24，85，47，30，53，91，对应的完全二叉树如图10.9所示。,(a) 堆顶元素取最大值,(b) 堆顶元素取最小值,图10.9堆的示例,11,堆排序（Heap Sort）：若在输出堆顶的最小值之后，使得剩余n1个元素的序列重又建成一个堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。,（2）堆调整,筛选：自堆顶至叶子的调整过程。,例如，图10.10(a)是个堆，假设输出堆顶元素之后，以堆中最后一个元素替代之，如图10.10(b)所示。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。首先以堆顶元素和其左、右子树根结点的值比较之，由于右子树根结点的值小于左子树根结点的值且小于根的值，则将27和97交换之；由于97替代了27之后破坏了右子树的“堆”，则需进行和上述相同的调整，直至叶子结点，调整后的状态如图10.10(c)所示，此时堆顶为n1个元素中的最小值。重复上述过程,将堆顶元素27和和堆中最后一个元素97交换且调整,得到如图10.10(d)所示新的堆。,12,(a) 堆,(b) 13和97交换后的情形,(c) 调整后的新堆,(d) 27和97交换后再进行调整建成的新堆,图10.10 输出堆顶元素并调整健新堆的过程,13,算法实现：算法10.10如下： typedef SqListHeapType;/堆采用顺序表存储表示 void HeapAdjust (HeapType /插入 / HeapAdjust,14,（3）建堆,个元素,由此“筛选”只需从第,15,例如，图10.11(a)中的二叉树表示一个有8个元素的无序序列,(a) 无序序列,(b) 97被筛选之后的状态,16,(c) 65被筛选之后的状态,(d) 38被筛选之后的状态,(e) 49被筛选之后的状态,图10.11 建初始堆的过程示例,17,（4）堆排序 堆排序的算法如算法10.11所示。为使排序结果和前述一致，即使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大记录并与序列中最后一个记录交换，然后对序列中前n1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。由此，“筛选”应沿关键字较大的孩子结点向下进行。,算法10.11如下： void HeapSort (HeapType /将H.r1i1重新调整为大顶堆 / for / HeapSort,堆排序在最坏的情况下，其时间复杂度也为 。,18,例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,19,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,20,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,21,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,22,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,23,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,24,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,25,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,26,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后,27,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,28,（f）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,29,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,30,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,31,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,32,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,33,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,34,