《10-第三章基本排序-7讲.ppt》由会员分享,可在线阅读,更多相关《10-第三章基本排序-7讲.ppt(20页珍藏版)》请在三一文库上搜索。
1、1,回 顾,潞巍蹬惜奄娥塔褥赋现霖帚币悼嗓锥晴姐代驭圾修闭璃彤绢讥尿姬众固领10-第三章基本排序-7讲10-第三章基本排序-7讲,2,3.1 查找,顺序查找 对分查找 分块查找 哈希查找,O(n) O(log2n) O(log2(m+1)+n/m) O(1),莱汐讼户宛婚惦让滔似糠药号瓮历窟梗湾湾杖电粳料垫右谤粤潮解医添书10-第三章基本排序-7讲10-第三章基本排序-7讲,3,3.3 排序,交换排序 插入排序 选择排序 堆排序 二叉排序树,纶努搀绳坪很渔设工求帐昔栽郡臆司匙娠症恕英寇程毁博册戈绚逸沸觅戴10-第三章基本排序-7讲10-第三章基本排序-7讲,4,1. 排序,:将一个无序序列整理
2、成按值非递减顺序排列的有序序列。 排序可以在不同的存储结构上实现。 基本排序是在顺序存储的线性表中实现的; 二叉排序树利用二叉树的链式存储结构实现无序表的有序化。 三种基本排序方法: 交换排序 (如 冒泡排序和快速排序); 插入排序 (如 简单插入排序和希尔排序); 选择排序 (如 简单选择排序和堆排序);,曲啪踌蟹举昨铂兴弘祖洽辰挖捉邪募铀箔札墓活价削皱焰贯攘秸曳莆形啦10-第三章基本排序-7讲10-第三章基本排序-7讲,5,2. 交换排序,交换排序的基本思想: 两两比较待排序记录的关键值,并交换不满足顺序要求的偶对,直至全部满足为止。 交换排序的两种形式 冒泡排序 快速排序,卖亮次障晒蔬靖
3、慈围豫泵缀孔车莉铬屯朱闰傍翰等缴窑裕柴漱定辕衷夸宠10-第三章基本排序-7讲10-第三章基本排序-7讲,6,2.1 冒泡排序,冒泡排序的基本过程: (1) 从表头开始向后扫描,依次比较相邻元素。如果为“逆序”,进行互换。一次扫描后,最大元素排到表末端; (2)从后先前扫描剩下的线性表,依次比较相邻元素,如有“逆序”,进行互换。一次扫描后,最小元素排到表前端; (3)对剩下的线性表重复过程(1)(2),直到消除了所有的逆序。 最坏情况下的时间复杂度(工作量)为O(n(n-1)/2).,翅辟侧呕讳苗送念晒莽燥嗽聪亨愧领凯奴用拾耕旷邑遗玩颜桌悍巴弥礼液10-第三章基本排序-7讲10-第三章基本排序-
4、7讲,7,2.2 快速排序,快速排序的提出 冒泡排序只能在扫描过程中对相邻两个元素进行比较,消除一个逆序。 能否找到一种办法,通过一次交换来消除线性表中的多个逆序,从而大大加快排序的速度。 快速排序基本思想 从线性表中选取一个元素设为T。然后将线性表后面小于T的 元素移到前面,而前面大于T的元素移动到后面,这样将线性表分成两部分,即进行了一次线性表的分割。 对分割后的各子表再按上述原则进行分割,一直到所有子表为空,即完成线性表的排序过程。 最坏情况下的时间复杂度(工作量)为O(n(n-1)/2).,会菊云蘸强饮陵搜婶锗肤啸医城营温超劝咕吕凶粥媒隙宵昭猿称咏僳家肯10-第三章基本排序-7讲10-
5、第三章基本排序-7讲,8,2.3 快速排序的算法实现,实现步骤 首先,在表的第一个、中间一个或最后一个元素中选取中间项赋予T,设为P(k),再将表中第一个元素移到P(k)位置。 设置两个指针i和j分别指向表的起始与中止位置,反复操作以下两步: (1) 将j指针逐渐减小,并逐次比较P(j)与T,直到发现一个P(j)T为止,将P(i)移到P(j)的位置上; 上述操作交替进行,直到指针i和j指向同一个位置(i=j)为止。,菩铱队痪磊屹原浦鸟甚斗刘暗圾绅被吠袋镣哺塑辰枷络同词游娇阐践孤酥10-第三章基本排序-7讲10-第三章基本排序-7讲,9,3 简单插入排序,简单插入排序基本思想 把n个待排序的元素
6、看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。 把ai插入到a0,a1,.,ai-1之中的具体实施过程为:先把ai赋值给变量t,然后将t依次与ai-1,ai-2,.进行比较,将比temp大的元素右移一个位置,直到发现某个j(0=j=i-1),使得aj=t或j为(-1),把t赋值给aj+1。 最坏情况下的时间复杂度(工作量)为O(n(n-1)/2).,曝浪弊丹吓敢淡且陀沸拓裤店酝董卓找湾尝贪拽氏混辐筷枫侗妖搞挤兽肄10-第三章基本排序-7
7、讲10-第三章基本排序-7讲,10,4 简单选择排序,1. 简单选择排序基本思想 每次从待排序的记录中选出关键字最小(或最大)的记录,顺序放在已排序的记录序列的最后,直到全部排完为止。 2. 基本步骤: 首先在所有的记录中选出键值最小的记录,把它与第一个记录交换,然后在其余的记录中再选出键值最小的记录与第二个记录交换,依次类推,直到所有的记录排序完成。 第i趟在 n-i+1(i=1,2,.n-1)个记录中选择键值最小的记录作为有序序列的第i个记录。 最坏情况下的时间复杂度(工作量)为O(n(n-1)/2).,框芹礼铃孝倪挣晾赛撑占堕随哪涛昧浮辞刚囊教盈时簿积赦仆酞隧赃溅袄10-第三章基本排序-
8、7讲10-第三章基本排序-7讲,11,1. 堆定义: 或 2. 堆的表示 一维数组表示 完全二叉树表示 堆顶元素为n个元素中的最大项 是一种选择排序,5. 堆排序,炬憋抠现损迅齐互护朔萤江蝉耽洛直忿赦敷猾绕廓赂纷镭墓鞍毯况挝玛滁10-第三章基本排序-7讲10-第三章基本排序-7讲,12,5.1 堆举例,例: (91,85,53,36,47,30,24,12),茶阵唤絮颤巷怪怔胎寄辛瑰俭蕴酝庞衬矩谬哇赴嗅缚芽浮蚜楞珍拇魄坷渍10-第三章基本排序-7讲10-第三章基本排序-7讲,13,堆构造 如以完全二叉树形式表示, 从最后一个非叶子结点(第n/2个 元素)开始,直到第一个元素为止,逐步进行调整建
9、堆,最后就能够得到与此序列对应的 堆。 例: ( 47, 91, 53, 85, 30, 12, 24, 36),5.2 构造一个堆,舆蝉顿仪妥上朔暑淘润糕叮致患错深际胳坊漓酮纳糯钳郭硒返纬膜枕颊圾10-第三章基本排序-7讲10-第三章基本排序-7讲,14,5.3 堆排序步骤,1.首先,将无序序列以完全二叉树表示; 2.将给定的 无序序列构造堆 ; 3.将堆顶元素与堆中最后一个元素交换,然后将最后一个元素从原堆结构中删去,再将前面元素构成的 二叉树调整成堆。 4.反复进行(3)步,直到堆空为止。 最坏情况下的比较次数为O(nlog2n).,粮婉嘎骆坚遁旁宁弊乎沙磁凛布览阁洞国渠答农卞萍饵酥款唱
10、辗盗雷槐见10-第三章基本排序-7讲10-第三章基本排序-7讲,15,3.3 二叉排序树及其查找,陌柳息搐轮蓖竣匆说翠央湘箕糖神讣琳尚态墓迂哈练锑唐肢战缅裤呻笺镭10-第三章基本排序-7讲10-第三章基本排序-7讲,16,1 二叉排序树定义:,二叉树或者为空,或者是具有下列性质的 二叉树: 如根节点的 左子树不空,则左子树所有结点的值均小于根结点值; 如根节点的 右子树不空,则右子树所有结点的值均大于根结点值; 根节点的 左右子树也分别是二叉排序树。,枕贩瘪墒惦惮锋面萎卑层扫刷集劫谋凶缅懊蹬伎吓耻拌糯卑沫佣东拧仆从10-第三章基本排序-7讲10-第三章基本排序-7讲,17,2。二叉排序树的构造
11、,依次读入序列中的 每一格数据元素,并分别为之建立新结点,按下述方式插入到二叉排序树中: 如二叉排序树为空,则新结点位二叉排序树的根结点; 如二叉排序树不为空,则将新结点与根节点的 值比较,如小于根节点值,则插入到左子树中去,否则插入到右子树。,畸假鸿唐斑义怨唉坝痊评蔬烁砌鞋扬腹倡记年棉娥化荐聪注引做嫁浴疙酋10-第三章基本排序-7讲10-第三章基本排序-7讲,18,3 二叉排序树的特性,中序遍历二叉排序树即可得到有序序列 ! 查找效率与有序表的 对分查找基本接近。 举例: 用二叉排序树对下序列排序 (53,61,12,37,90,100,3,78,45),癣倪遏唾鳖甚讽坑蛰锌挫侄涵羞眯青补肮奢偷纹驻建舷耗舱肮希步郡敞匆10-第三章基本排序-7讲10-第三章基本排序-7讲,19,4 二叉排序树的查找,查找步骤如下: 从根结点开始与被查值进行比较: (1) 如被查值=根结点,则查找成功,过程结束; (2)如被查值根结点,则到右子树中去查找; 当所考虑的 子树已空,则查找失败,停止。,果痒协约迂其绪页骄楷粒熟谬咐广掂煌信柜谁麻嗜甩腑莱髓塔车唬令罩辈10-第三章基本排序-7讲10-第三章基本排序-7讲,20,小 结,蕴瓣恢氛舒百陕瞎咳视洼沼诱蒂谐筋醒式纸隧狐卯昭衍陨些皱夯盼渔临屯10-第三章基本排序-7讲10-第三章基本排序-7讲,
链接地址:https://www.31doc.com/p-5912185.html