牛小飞《数据结构》7.2堆排序

选择排序,选择排序的基本思想,简单选择排序,堆排序7.5,小结和作业,简单选择排序-基本思想,假设排序过程中，待排记录序列的状态为：,有序序列R1.i-1,无序序列Ri.n,第i趟简单选择排序,从中选出关键字最小的记录,有序序列R1.i,无序序列Ri+1.n,选择排序的基本思想,选择排序的基本思想：,每一趟从待排序的n-i+1（i=1,2,3,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。,1.直接选择排序,2.堆选择排序,49,13,简单选择排序-例子,65,97,76,13,27,38,49,第一趟i=1,13,13,简单选择排序-例子,65,97,76,49,27,38,第二趟：i=2,27,38,27,13,简单选择排序-例子,65,97,76,49,38,第三趟：i=3,27,65,38,38,13,65,97,76,49,65,第四趟：i=4,27,38,97,49,49,简单选择排序-例子,13,65,97,76,97,65,第五趟：i=5,27,38,38,49,76,65,13,65,97,76,97,76,第六趟：i=6,27,38,38,49,76,65,97,13,65,97,76,97,97,排序结果：,27,38,38,49,76,65,97,简单选择排序-算法,privatestaticvoidSelectSort(AnyTypea)/对记录序列a进行简单选择排序for(inti=0;ia.length-1;i+)/排序趟数intk=i;for(intj=k+1;j=0;i-)percDown(a,i,a.length);/建堆,for(inti=a.length-1;i0;i-)SwapReferences(a,0,i);/删除最大元percDown(a,0,i);,privatestaticintleftChild(inti)return2*i+1;,堆排序堆排序算法,publicstaticvoidpercDown(AnyTypea,inti,intn)/*已知ai.n中记录的关键字除ai之外均满足堆的特征，本方法自上而下调整ai，使ai.n也成为一个大顶堆*/,for(tmp=ai;leftChild(i)=”成立，则说明已找到tmp的插入位置，不需要继续往下调整*/,/否则记录上移，尚需继续往下调整,堆排序堆排序算法,for(tmp=ai;leftChild(i)n;i=child)child=leftChild(i);,/下滤算法,if(child!=n-1,if(pareTo(achild)0)ai=achild;elsebreak;,堆排序-性能分析,1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；,2.对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多4n；,堆排序-性能分析,3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+log22)2n(log2n),因此，堆排序的时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。辅助空间为O(1),4.堆排序是一个不稳定的排序方法。,简单选择排序,堆排序,1基本思想,3算法,2实例模拟,4时间复杂度,1基本思想,3算法,2实例模拟,4时间