欢迎来到天天文库
浏览记录
ID:51305931
大小:535.00 KB
页数:23页
时间:2020-03-22
《数据结构选择排序.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、选择排序(Selectionsort)选择排序(Selectionsort)是以选择为基础的一种常用排序方法,从记录的无序子序列中“选择”关键字最小或最大的记录,并将其加入到有序子序列的一端,以增加记录的有序子序列的长度。它也有几种不同的实现方法,这里仅介绍简单选择排序、树形排序和堆排序。1.简单选择排序(1)算法描述简单选择排序算法的基本思路:对于一组关键字(Kl,K2,…,Kn),将其由小到大进行排序,首先从Kl,K2,…,Kn中选择最小值,假设是Kk,则将Kk与K1对换;然后从K2,K3,…,Kn中选择最小值Kk+1,再将Kk+1与K2对换。如此进行选择和
2、调换,对第i趟选择排序,进行n-i次关键字比较,从n-i+1个记录中选出关键字最小的记录,并与第i个记录交换。令i从1至n-1,进行n-1趟选择排序,一个由小到大的有序序列就形成了。例1设有一组关键字[49,39,66,49*,76,11,27,96],这里n=8。试用简单选择排序方法,将这组记录由小到大进行排序。其排序过程如图所示,算法实现如下:voidSelectSort(SqList&L){/*对顺序表L作简单选择排序。*/inti,j;RedTypetemp;for(i=1;i3、tMinKey(L,i);/*在L.r[i..L.length]中选择key最小的记录*/if(i!=j)/*L.r[i]←→L.r[j];与第i个记录交换*/{temp=L.r[i];L.r[i]=L.r[j];L.r[j]=temp;}}}/*SelectSort*/(2)算法分析在简单选择排序中,无论待排序的记录初始序列是否有序,都需要执行n(n-1)/2次关键字的比较操作。如果待排序的记录初始序列就是已经排好序的正列,则无须移动记录,因为每个元素都位于其最终位置上了;而如果待排序的记录初始序列是逆序,即在最坏情况下,则要做3(n-1)次记录移动。所以,简4、单选择排序的时间复杂度是O(n*n)。由上面的例1很显然看到,49在排序前位于49*的前面,而经简单选择排序后却位于49*后面了,它们的相对位置发生了颠倒,因此简单选择排序算法是不稳定排序算法。3.堆排序(1)堆的定义堆是一个记录序列{k1,k2,…,kn},,对于列表中位置i(编号从1开始)处的记录的关键字ki,当且仅当满足下列关系时,称之为堆。ki≤k2i或ki≥k2iki≤k2i+1ki≥k2i+1(i=1,2,…,n/2)其中,每个结点关键字都不小于其子孙结点关键字的堆称为“大根堆”;而每个结点关键字都不小于其子孙结点关键字的堆称为“小根堆”。下面的讨论5、中以小根堆为例。判断下列序列是否为堆?⑴(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)我们已经知道,对于一棵有n个结点的完全二叉树,当它的结点由上而下,自左至右编号之后,编号为1~[n/2]的结点为分支结点,编号大于[n/2]的结点为叶子结点,对于每个编号为i的分支结点,它的左孩子的编号为2i,它的右孩子的编号为2i+1。对于每个编号为i(i>1)的结点,它的双亲的编号为[i/2]。因此,我们还可6、以借助完全二叉树来描述堆的概念:若完全二叉树中任一非叶子结点的值均小于等于(或大于等于)其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个堆。(2)算法描述堆顶记录对应完全二叉树的根结点,堆顶记录关键字是所有记录关键字的最值,堆排序就是利用堆的上述特征完成排序的。在输出堆顶的最大(或最小)之后,使得剩余的n-1个记录的序列重新调整为一个堆,于是又得到次大(或次小)值……如此反复执行,直至所以记录都排序为一个有序序列。这就是堆排序(HeapSort)。由于初始记录序列不一定满足堆关系,因此堆排序过程大体分两步处理:①初建堆。从堆的定义出发,先7、取i=[n/2](它一定是第n个结点双亲的编号),将以i结点为根的子树调整成为堆;然后令i=i-1;再将以i结点为根的子树调整成为堆。此时可能会反复调整某些结点,直到i=1为止,堆初建完成。②堆排序。首先输出堆顶元素(一般是最小值),让堆中最后一个元素上移到原堆顶位置,然后恢复堆,因为经过第一步输出堆顶元素的操作后,往往破坏了原来的堆关系,所以要恢复堆;重复执行输出堆顶元素、堆尾元素上移和恢复堆的操作,直到全部元素输出完为止。按输出元素的前后次序排列,就形成了有序序列,完成了堆排序的操作。例设有n个记录(n=8)的关键字是[30,50,60,35,86,10,48、0,45],试用堆排序方
3、tMinKey(L,i);/*在L.r[i..L.length]中选择key最小的记录*/if(i!=j)/*L.r[i]←→L.r[j];与第i个记录交换*/{temp=L.r[i];L.r[i]=L.r[j];L.r[j]=temp;}}}/*SelectSort*/(2)算法分析在简单选择排序中,无论待排序的记录初始序列是否有序,都需要执行n(n-1)/2次关键字的比较操作。如果待排序的记录初始序列就是已经排好序的正列,则无须移动记录,因为每个元素都位于其最终位置上了;而如果待排序的记录初始序列是逆序,即在最坏情况下,则要做3(n-1)次记录移动。所以,简
4、单选择排序的时间复杂度是O(n*n)。由上面的例1很显然看到,49在排序前位于49*的前面,而经简单选择排序后却位于49*后面了,它们的相对位置发生了颠倒,因此简单选择排序算法是不稳定排序算法。3.堆排序(1)堆的定义堆是一个记录序列{k1,k2,…,kn},,对于列表中位置i(编号从1开始)处的记录的关键字ki,当且仅当满足下列关系时,称之为堆。ki≤k2i或ki≥k2iki≤k2i+1ki≥k2i+1(i=1,2,…,n/2)其中,每个结点关键字都不小于其子孙结点关键字的堆称为“大根堆”;而每个结点关键字都不小于其子孙结点关键字的堆称为“小根堆”。下面的讨论
5、中以小根堆为例。判断下列序列是否为堆?⑴(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)我们已经知道,对于一棵有n个结点的完全二叉树,当它的结点由上而下,自左至右编号之后,编号为1~[n/2]的结点为分支结点,编号大于[n/2]的结点为叶子结点,对于每个编号为i的分支结点,它的左孩子的编号为2i,它的右孩子的编号为2i+1。对于每个编号为i(i>1)的结点,它的双亲的编号为[i/2]。因此,我们还可
6、以借助完全二叉树来描述堆的概念:若完全二叉树中任一非叶子结点的值均小于等于(或大于等于)其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个堆。(2)算法描述堆顶记录对应完全二叉树的根结点,堆顶记录关键字是所有记录关键字的最值,堆排序就是利用堆的上述特征完成排序的。在输出堆顶的最大(或最小)之后,使得剩余的n-1个记录的序列重新调整为一个堆,于是又得到次大(或次小)值……如此反复执行,直至所以记录都排序为一个有序序列。这就是堆排序(HeapSort)。由于初始记录序列不一定满足堆关系,因此堆排序过程大体分两步处理:①初建堆。从堆的定义出发,先
7、取i=[n/2](它一定是第n个结点双亲的编号),将以i结点为根的子树调整成为堆;然后令i=i-1;再将以i结点为根的子树调整成为堆。此时可能会反复调整某些结点,直到i=1为止,堆初建完成。②堆排序。首先输出堆顶元素(一般是最小值),让堆中最后一个元素上移到原堆顶位置,然后恢复堆,因为经过第一步输出堆顶元素的操作后,往往破坏了原来的堆关系,所以要恢复堆;重复执行输出堆顶元素、堆尾元素上移和恢复堆的操作,直到全部元素输出完为止。按输出元素的前后次序排列,就形成了有序序列,完成了堆排序的操作。例设有n个记录(n=8)的关键字是[30,50,60,35,86,10,4
8、0,45],试用堆排序方
此文档下载收益归作者所有