数据结构 选择排序PPT学习教案

1、会计学1数据结构数据结构 选择排序选择排序 选择排序（选择排序（Selection sort）是以选择为基础的）是以选择为基础的一种常用排序方法，从记录的无序子序列中一种常用排序方法，从记录的无序子序列中“选择选择”关键字最小或最大的记录，并将其加入到有序子序列关键字最小或最大的记录，并将其加入到有序子序列的一端，以增加记录的有序子序列的长度。它也有几的一端，以增加记录的有序子序列的长度。它也有几种不同的实现方法，这里仅介绍简单选择排序、树形种不同的实现方法，这里仅介绍简单选择排序、树形排序和堆排序。排序和堆排序。 第1页/共23页1. 1. 简单选择排序简单选择排序（1）算法描述）算法描述

2、简单选择排序算法的基本思路：对于一组关键字简单选择排序算法的基本思路：对于一组关键字(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至

3、至n-1，进行，进行n-1趟选择排序，一个由小到大的有序序趟选择排序，一个由小到大的有序序列就形成了。列就形成了。第2页/共23页例例1 设有一组关键字设有一组关键字49，39，66，49*，76，11，27，96，这里，这里n8。试用简单选择排序方法，将这组记录由小到大进行排序。其排序过程如图所示，。试用简单选择排序方法，将这组记录由小到大进行排序。其排序过程如图所示，第3页/共23页算法实现如下：算法实现如下：void SelectSort(SqList &L) /* 对顺序表对顺序表L作简单选择排序。作简单选择排序。*/ int i , j; RedType temp; for (i=1

4、; iL.length; +i) /* 选择第选择第i小的记录并交换到位小的记录并交换到位*/ j = SelectMinKey(L, i); /* 在在L.ri.L.length中选择中选择key最小的记录最小的记录*/ if (i!=j) /* L.riL.rj; 与第与第i个记录交换个记录交换*/ temp=L.ri; L.ri=L.rj; L.rj=temp; / * SelectSort*/第4页/共23页（2）算法分析）算法分析 在简单选择排序中，无论待排序的记录初始序列在简单选择排序中，无论待排序的记录初始序列是否有序，都需要执行是否有序，都需要执行n(n-1)/2次关键字的比较

5、操作。次关键字的比较操作。如果待排序的记录初始序列就是已经排好序的正列，如果待排序的记录初始序列就是已经排好序的正列，则无须移动记录，因为每个元素都位于其最终位置上则无须移动记录，因为每个元素都位于其最终位置上了；而如果待排序的记录初始序列是逆序，即在最坏了；而如果待排序的记录初始序列是逆序，即在最坏情况下，则要做情况下，则要做3(n-1)次记录移动。所以，简单选择次记录移动。所以，简单选择排序的时间复杂度是排序的时间复杂度是O(n*n)。 由上面的例由上面的例1很显然看到，很显然看到，49在排序前位于在排序前位于49*的的前面，而经简单选择排序后却位于前面，而经简单选择排序后却位于49*后面

6、了，它们的后面了，它们的相对位置发生了颠倒，因此简单选择排序算法是不稳相对位置发生了颠倒，因此简单选择排序算法是不稳定排序算法。定排序算法。第5页/共23页3. 3. 堆排序堆排序（1）堆的定义）堆的定义 堆是一个记录序列堆是一个记录序列k1，k2，kn，对于列，对于列表中位置表中位置i（编号从（编号从1开始）处的记录的关键字开始）处的记录的关键字ki，当且，当且仅当满足下列关系时，称之为堆。仅当满足下列关系时，称之为堆。 kik2i 或或 kik2i kik2i+1 kik2i+1 （ i 1，2，n/2 ） 其中，每个结点关键字都不小于其子孙结点关键字其中，每个结点关键字都不小于其子孙结点

7、关键字的堆称为的堆称为“大根堆大根堆”；而每个结点关键字都不小于其；而每个结点关键字都不小于其子孙结点关键字的堆称为子孙结点关键字的堆称为“小根堆小根堆”。下面的讨论中。下面的讨论中以小根堆为例。以小根堆为例。第6页/共23页 判断下列序列是否为堆？判断下列序列是否为堆？ (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)第7页/共23页 我们已经知道，对于一棵有我们已经知道，对于一棵有n个结点的完全二叉树个结点的完全二叉树，当它的

8、结点由上而下，自左至右编号之后，编号为，当它的结点由上而下，自左至右编号之后，编号为1n/2的结点为分支结点，编号大于的结点为分支结点，编号大于n/2的结点为叶子的结点为叶子结点，对于每个编号为结点，对于每个编号为i的分支结点，它的左孩子的编号的分支结点，它的左孩子的编号为为2i，它的右孩子的编号为，它的右孩子的编号为2i+1。对于每个编号为。对于每个编号为i（i1）的结点，它的双亲的编号为）的结点，它的双亲的编号为i/2。 因此，我们还可以借助完全二叉树来描述堆的概念因此，我们还可以借助完全二叉树来描述堆的概念：若完全二叉树中任一非叶子结点的值均小于等于：若完全二叉树中任一非叶子结点的值均小

9、于等于(或大或大于等于于等于)其左、右孩子结点的值，则从根结点开始按结点其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。编号排列所得的结点序列就是一个堆。 第8页/共23页第9页/共23页（2）算法描述）算法描述 堆顶记录对应完全二叉树的根结点，堆顶记录关键堆顶记录对应完全二叉树的根结点，堆顶记录关键字是所有记录关键字的最值，堆排序就是利用堆的上述字是所有记录关键字的最值，堆排序就是利用堆的上述特征完成排序的。在输出堆顶的最大（或最小）之后，特征完成排序的。在输出堆顶的最大（或最小）之后，使得剩余的使得剩余的n-1个记录的序列重新调整为一个堆，于是又个记录的序列重新

10、调整为一个堆，于是又得到次大（或次小）值得到次大（或次小）值如此反复执行，直至所以记如此反复执行，直至所以记录都排序为一个有序序列。这就是堆排序（录都排序为一个有序序列。这就是堆排序（Heap Sort）。 第10页/共23页 由于初始记录序列不一定满足堆关系，因此堆排序由于初始记录序列不一定满足堆关系，因此堆排序过程大体分两步处理：过程大体分两步处理： 初建堆。从堆的定义出发，先取初建堆。从堆的定义出发，先取i=n/2 (它一定它一定是第是第n个结点双亲的编号个结点双亲的编号)，将以，将以i结点为根的子树调整成结点为根的子树调整成为堆；然后令为堆；然后令i=i-1；再将以；再将以i结点为根的

11、子树调整成为堆结点为根的子树调整成为堆。此时可能会反复调整某些结点，直到。此时可能会反复调整某些结点，直到i=1为止，堆初建为止，堆初建完成。完成。 堆排序。首先输出堆顶元素堆排序。首先输出堆顶元素(一般是最小值一般是最小值)，让，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过第一步输出堆顶元素的操作后，往往破坏了原来为经过第一步输出堆顶元素的操作后，往往破坏了原来的堆关系，所以要恢复堆；重复执行输出堆顶元素、堆的堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的操作，直到全部元素输出完为止尾元素上移和恢复堆的操作，直到

12、全部元素输出完为止。按输出元素的前后次序排列，就形成了有序序列，完。按输出元素的前后次序排列，就形成了有序序列，完成了堆排序的操作。成了堆排序的操作。第11页/共23页例例 设有设有n个记录个记录(n8)的关键字是的关键字是30，50，60，35，86，10，40，45，试用堆排序方法，将这组记录由，试用堆排序方法，将这组记录由小到大进行排序。小到大进行排序。 第12页/共23页第一步：初始建堆，其建堆过程如图所示。因为第一步：初始建堆，其建堆过程如图所示。因为n=8，所，所以从以从i4开始。开始。第13页/共23页 第二步：堆排序。这是一个反复输出堆顶元素，将第二步：堆排序。这是一个反复输出

13、堆顶元素，将堆尾元素移至堆顶，再调整恢复堆的过程。恢复堆的过堆尾元素移至堆顶，再调整恢复堆的过程。恢复堆的过程与初建堆中程与初建堆中i=1时所进行的操作完全相同。时所进行的操作完全相同。 请注意：每输出一次堆顶元素，堆尾的逻辑位置退请注意：每输出一次堆顶元素，堆尾的逻辑位置退1，直到堆中剩下一个元素为止，排序过程如图所示。，直到堆中剩下一个元素为止，排序过程如图所示。 第14页/共23页第15页/共23页输出序列：输出序列： 10 30 35 40 45 50 60 86第16页/共23页 由上可知，调整恢复堆操作过程要被多次反复调用由上可知，调整恢复堆操作过程要被多次反复调用，即当，即当i值

14、确定之后，以值确定之后，以ki为比较参照值，与其左、右孩为比较参照值，与其左、右孩子的关键字比较和调整，使以结点子的关键字比较和调整，使以结点i为根的子树成为堆，为根的子树成为堆，因此把此过程设计成函数因此把此过程设计成函数Heap：void Heap(RedType r ，int i，int m) /*i是根结点编号，是根结点编号，m是以是以i结点为根的子树的最后一个结点编号结点为根的子树的最后一个结点编号*/ x=ri；j=2*i；/* x保存根记录的内容，保存根记录的内容，j为左孩子编号为左孩子编号*/ while (j=m) if ( jm&rjkeyrj+1key) j+； /* 当

15、结点当结点i有左、右两个孩子时，有左、右两个孩子时，j取关键字值较小的孩子结点编号取关键字值较小的孩子结点编号*/ if ( rj. keyx. key) ri=rj；i=j；j=2*i； /*向下一层探测向下一层探测*/ else j=m+1； /*x. key小于左、右孩于的关键字，强制使小于左、右孩于的关键字，强制使jm，以便结束循环，以便结束循环*/ ri=x； /* Heap */ 第17页/共23页 另外，还需要设计一个主体算法，使在初建堆阶段另外，还需要设计一个主体算法，使在初建堆阶段，让，让i从从n/2变化到变化到1，循环调用，循环调用heap函数，而在堆排序函数，而在堆排序阶

16、段，每输出一次堆顶元素，将堆尾元素移至堆顶之后阶段，每输出一次堆顶元素，将堆尾元素移至堆顶之后，就要调用一次，就要调用一次heap函数来恢复堆。主体算法由函数函数来恢复堆。主体算法由函数Heapsort来实现：来实现：void Heapsort(RedType r ，int n) /* n为文件的实际记录数，为文件的实际记录数，ro没有使用没有使用*/ for(i=n/2；i=1；i-) Heap(r，i，n)； /*初建堆初建堆*/ for(v=n; v=2; v-) x=r1; r1=rv; rv=x； /*堆顶堆尾元素对换堆顶堆尾元素对换*/ Heap(r,1,v-1); /*本次比上次

17、少处理一个记录本次比上次少处理一个记录*/* Heapsort */ 第18页/共23页（3）算法分析）算法分析 在堆排序图示例中，堆越画越小，堆中结点越来在堆排序图示例中，堆越画越小，堆中结点越来越少，实际上，在用来存储堆的数组中堆顶元素输出之越少，实际上，在用来存储堆的数组中堆顶元素输出之后并未删除，而是与堆尾元素对换。从图示看输出的是后并未删除，而是与堆尾元素对换。从图示看输出的是一个由小到大的升序序列，实际最后数组中记录的关键一个由小到大的升序序列，实际最后数组中记录的关键字从字从rl. key到到rn. key是一个由大到小的降序序列。算是一个由大到小的降序序列。算法法Heap的时间复杂度与堆所对应的完全二叉树的树深的时间复杂度与堆所对应的完全二叉树的树深log2n相关，而算法相关，而算法Heapsort中对中对Heap的调用数量级为的调用数量级为n，所以整个堆排序的时间复杂度