内蒙古大学《算法与数据结构》课件第7章排序
103页1、1 第第 7 章章 排排 序序7.1 内部排序方式内部排序方式7.2 插入排序插入排序7.3 选择排序选择排序7.4 交换排序交换排序 7.5 归并排序归并排序7.6 基数排序基数排序7.7 各种内部排序算法的比较各种内部排序算法的比较27.1 内部排序方式内部排序方式3 0 1 . 1 0 1 . 1K pK pK p nK pK pK p n或者456class /排序码排序码/其它数据成员其它数据成员/提取排序码提取排序码/修改修改 /数据表数据表/存储向量存储向量/最大元素个数与当前元素个数最大元素个数与当前元素个数/构造函数构造函数/交换元素交换元素97.2 插入排序插入排序1、直接插入排序直接插入排序(基于顺序查找)(基于顺序查找)2、 折半插入排序折半插入排序(基于折半查找)(基于折半查找)3、 希尔排序希尔排序(基于逐趟缩小增量)(基于逐趟缩小增量)10基本思想是:基本思想是:当插入第当插入第i (i 2) 个数据时,前面的处理个数据时,前面的处理R1, , Ri-1已经排好序。这时用已经排好序。这时用Ri的排序码与的排序码与Ri-1, Ri-2, 的的排序码顺序进行比
2、较,直到排序码顺序进行比较,直到 Rj.key=Ri.key( 0 ji )将将Rj+1, Ri-1向后顺移向后顺移,将将Ri插入到插入到j+1位置处。位置处。 初始初始 50 22 45 80 08 45* 62 i=2 22 50 45 80 08 45* 62 i=3 22 45 50 80 08 45* 62 i=4 22 45 50 80 08 45* 62 i=5 08 22 45 50 80 45* 62 i=6 08 22 45 45* 50 80 62 i=7 08 22 45 45* 50 80 62 0 1 2 3 4 5 6 7例如:给出初始排序码序列例如:给出初始排序码序列 50 22 45 80 08 45* 62 的直接插入排序示意图。的直接插入排序示意图。 图图7.1 直接插入排序示例直接插入排序示例12 直接插入排序的算法如下:直接插入排序的算法如下:void InsertionSort( ) /按排序码按排序码Key 非递减顺序对数据表进行直接插入排序非递减顺序对数据表进行直接插入排序 for(i=2; i=CurrentSize; i+ ) if
3、(Ri.KeyRi-1.Key) R0=Ri; for(j=i-1; R0.KeyRj.Key; j-) Rj+1=Rj; Rj+1=R0; / InsertionSort13最好的情况(排序码有序):最好的情况(排序码有序):“比较比较”的次数:的次数:最坏的情况(排序码逆序):最坏的情况(排序码逆序):“比较比较”的次数:的次数:112nni21412)n)(n()i (ni“移动移动”的次数:的次数:“移动移动”的次数:的次数:2) 1n)(2n(in2i 直接插入排序算法分析:直接插入排序算法分析:014 平均的情况平均的情况: 若待排序数据序列中出现各种可能排列的概率相同,则可若待排序数据序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。在平均情况下的排取上述最好情况和最坏情况的平均情况。在平均情况下的排序码比较次数和数据移动次数约为序码比较次数和数据移动次数约为 因此,直接插入排序的时间复杂度为因此,直接插入排序的时间复杂度为 O(n2)。 空间效率:空间效率:因为仅占用因为仅占用1个缓冲单元个缓冲单元R0 直接插入排序是一种直接插入排序是一种稳定稳
4、定的排序方法。的排序方法。4n4) 1n)(4n(21i2n2i直接插入排序算法分析:直接插入排序算法分析:151614 36 49 52 80 58 61 23 97 75ileftrightmmleftleftmrightileftrightmrightmrightmleft例如例如:插入插入位置位置插入插入位置位置R再如再如:14 36 49 52 58 61 80 23 97 75R折半插入排序示例折半插入排序示例17折半插入排序的算法如下:折半插入排序的算法如下:void BinaryInsertSort ( ) for (i = 2; i =CurrentSize; i+) left = 1, right = i-1; R0=Ri; flag=1; while ( left = right ) & flag middle = ( left + right )/2; if (R0. Key Rmiddle. Key) left = middle + 1; else flag=0; / 遇到有相同排序码的元素时,停止寻找遇到有相同排序码的元素时,停止寻找 if (!flag)
5、/ 当当flag0时,说明序列中存在有相同排序码的元素时,说明序列中存在有相同排序码的元素 left=middle; / 此时元素需从此时元素需从Rmiddle到到Ri-1 向后顺移元素向后顺移元素 for ( k = i-1; k = left; k- ) / 元素后移元素后移 Rk+1 = Rk; Rleft = R0;/for/ BinaryInsertSort203515455025102030折半插入排序的算法分析折半插入排序的算法分析:21时间效率:时间效率:比较次数比较次数: 在插入第在插入第 i 个数据时个数据时,最多需要经过最多需要经过 log2 (i+1) 次排序码次排序码比较,才能确定它应插入的位置。因此,将比较,才能确定它应插入的位置。因此,将 n 个数据用个数据用折半插入排序所进行的排序码比较次数为:折半插入排序所进行的排序码比较次数为:O(n*log2n)折半插入排序的算法分析折半插入排序的算法分析:空间效率:空间效率: O(1)O(1)( (R0 ) )但是移动次数并未减少,所以折半插入排序效率仍为但是移动次数并未减少,所以折半插入排序效率仍为O(nO(n
《内蒙古大学《算法与数据结构》课件第7章排序》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第7章排序》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页