数据结构-从概念到C++实现（第4版）课件 7-4选择排序

7-4选择排序v第七章排序技术学什么？简单选择排序堆排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-4-1简单选择排序v第七章排序技术基本思想有序区无序区min简单选择排序的基本思想：第

i

趟（1≤i≤n-1）排序在待排序序列ri~rn

中选取最小记录，并和第

i个记录交换。r1ri-1…rirn……r1ri-1…ri'ri+1rn…运行实例2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1012242018122420181018241220102018241210关键问题简单选择排序进行多少趟？for(i=0;i<length-1;i++){

}算法描述：第i趟简单选择排序；有序区无序区minr1ri-1…rirn……第i

趟简单选择排序完成什么工作？（1）在r[i]~r[n-1]中找最小值（2）将最小记录与r[i]交换算法描述：

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;if(index!=i)data[i]<==>data[index];算法实现voidSort::SelectSort(){inti,j,index,temp;for(i=0;i<length-1;i++) {

}}

if(index!=i){temp=data[i];data[i]=data[index];data[index]=temp;}

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;交换语句之前的判断一定会提高效率吗？比较语句？执行次数？移动语句？执行次数？时间性能与排序数据的初始状态有关性能分析最好情况：0次最坏情况：3(n-1)次比较次数：O(n2)移动次数：12345最好、最坏、平均情况：O(n2)12345

空间性能：O(1)

稳定性：不稳定155*155*7-4-2堆排序v第七章排序技术改进的着眼点缺点：简单选择排序的时间主要耗费在哪了呢？第i

趟扫描无序序列（n-i

次比较）只做了一件事——找最小值改进的着眼点：利用简单选择排序的思想，同时减少比较次数利用每趟比较后的结果优点：移动次数较少，最坏情况O(n)查找最小值的同时找出并保存较小值减少后面选择所用的比较次数提高整个排序的效率堆的定义小根堆：每个结点的值都小于等于其左右孩子结点的完全二叉树。大根堆：每个结点的值都大于等于其左右孩子结点的完全二叉树。小根堆和大根堆统称为堆。1820323825365040284550384532364020182828堆的特点50384532364020182828（2）较大值的结点靠近根结点，但不绝对。大根堆有什么特点呢？（1）根结点（称为堆顶）的值是所有结点的最大值；将堆按层序编号，有什么特点？12367541098堆与序列的关系5038453236402018282812367541098堆采用顺序存储，则对应一个（无序）序列503845323640282018280123456789顺序存储data[i]左孩子data[2*i+1]右孩子data[2*i+2]双亲与左右孩子之间的关系？堆调整堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，调整根结点使整个完全二叉树成为一个堆的过程。voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}如何设计函数接口？由于初始建堆和重建堆均调用此函数，因此，设置形参k和last关键问题283632251816362832251816iji和j的关系是？inti=k,j=2*i+1;j是i的左孩子voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}循环条件是？283632301816362832301816363032281816

while(j<=last){}ijijiinti=k,j=2*i+1;voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}关键问题28为什么和36交换？

if(j<last&&data[j]<data[j+1])j++;交换后如何调整i和j？else{

temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;}283632301816362832301816363032281816ijiji

while(j<=last){

}

if(j<last&&data[j]<data[j+1])j++;if(data[i]>data[j])break;什么时候结束筛选？关键问题堆调整算法voidSort::Sift(intk,intlast){inti,j,temp;i=k;j=2*i+1;//i是被调整结点，j是i的左孩子while(j<=last)//还没有进行到叶子{if(j<last&&data[j]<data[j+1])j++;//j指向左右孩子的较大者if(data[i]>data[j])break;//已经是堆else{temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;//被调整结点位于结点j的位置}}}基本思想堆排序的基本思想：首先将待排序序列构造成一个大根堆，即选出了堆中所有记录的最大者，将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。r1…rirn…rn-i+1无序区，调整为大根堆有序区第i

趟堆排序将r1~ri

调整成大根堆，再将堆顶与ri

交换运行实例12345待排序序列初始建堆541325413254132541325413254132交换r[1]和r[5]无序区重建堆交换r[1]和r[4]无序区重建堆交换r[1]和r[3]541324312312最后一趟5413221初始建堆如何将一个无序序列建成一个大根堆——初始建堆？待排序序列{28,25,16,36,18,32}282516361832362832251816初始建堆结果{36,28,32,25,18,16}解决办法：从编号最大的分支结点到根结点进行调整算法描述：for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//调整结点i需要调整叶子结点吗？运行实例待排序序列{28,25,16,36,18,32}282516361832282532361816283632251816362832251816初始建堆结果{36,28,32,25,18,16}for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//调整结点i关键问题12345待排序序列初始建堆5413254132如何处理堆顶——无序区中的最大值？解决办法：交换data[0]与

data[length-i];52交换413241352413如何将无序区重新调整成为大根堆？无序区最后一个结点的编号？解决办法：调整根结点算法描述：Sift(0,length-i-1);52第一趟堆排序结果413431252重建堆结果413关键问题堆排序要进行多少趟？n-1趟算法描述：for(i=0;i<length;i++){

第i

趟堆排序}52第一趟堆排序结果41352重建堆结果413第二趟堆排序结果52413关键问题算法实现voidSort::HeapSort(){inti,temp;for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);for(i=1;i<length;i++)