文档详情

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

发布:2025-04-21约3.92千字共26页下载文档
文本预览下载声明

选择排序选择排序的基本思想简单选择排序堆排序7.5小结和作业

假设排序过程中,待排记录序列的状态为:01有序序列R[1..i-1]02无序序列R[i..n]03第i趟简单选择排序04从中选出关键字最小的记录05有序序列R[1..i]06无序序列R[i+1..n]07简单选择排序-基本思想

堆选择排序直接选择排序选择排序的基本思想:每一趟从待排序的n-i+1(i=1,2,3,…,n-1)个记录中选出关键字最小的记录,作为有序序列中第i个记录,直到全部记录排序完毕。选择排序的基本思想

4913简单选择排序-例子6597761327381234567kjkjjjjkj49第一趟i=113i

简单选择排序-例子136597764927381234567kj第二趟:i=2jjjjk273827i

简单选择排序-例子1365977649381234567第三趟:i=3j2765kjjj38k381365977649651234567第四趟:i=42738974949iik

简单选择排序-例子1365977697651234567第五趟:i=52738384976651365977697761234567第六趟:i=6273838497665971365977697971234567排序结果:27383849766597ii

简单选择排序-算法privatestaticAnyTypeextendsComparable?superAnyTypevoidSelectSort(AnyType[]a){//对记录序列a[]进行简单选择排序for(inti=0;ia.length-1;i++){//排序趟数intk=i;for(intj=k+1;ja.length;j++)//在a[]中选择关键字最小的记录,并用k来存放if(a[j].compareTo(a[k])0)k=j;if(i!=k)SwapReferences(a,i,k);}}

对n个记录进行简单选择排序,所需进行的关键字间的比较次数总计为:01简单选择排序是一种不稳定的排序方法???01移动记录的次数,当待排序列为正序数为最小,最小值为0。待排序列为逆序数为最大,最大值为3(n-1)。01简单选择排序-性能分析

例:关键字序列T=(21,25,49,25*,16,08),请给出简单选择排序的具体实现过程。第1趟第2趟第3趟第4趟第5趟交换,不稳定的原始序列:21,25,49,25*,16,0808,25,49,25*,16,2108,16,49,25*,25,2108,16,21,25*,25,4908,16,21,25*,25,4908,16,21,25*,25,4912345简单选择排序-讨论

堆排序可将堆序列看成完全二叉树,则堆顶元素(完全二叉树的根)必为序列中n个元素的最小值或最大值堆排序过程—以大顶堆为例1)将无序序列建成一个堆,得到关键字最大的记录;2)输出堆顶的最大值后,使剩余的n-1个元素重又建成一个堆,则可得到n个元素的次最大值。3)重复执行,得到一个有序序列,这个过程叫堆排序buildHeap下滤

堆排序将含8个元素的无序序列(49,38,65,97,76,13,27,50)调整成大顶堆。49386597761327501.先将无序序列建立完全二叉树

堆排序49386597761327502.按照建堆思想,将(49,38,65,97,76,13,2

显示全部
相似文档