数据结构与程序设计王丽苹20sorting.ppt
《数据结构与程序设计王丽苹20sorting.ppt》由会员分享,可在线阅读,更多相关《数据结构与程序设计王丽苹20sorting.ppt(32页珍藏版)》请在三一办公上搜索。
1、5/17/2023,数据结构与程序设计,1,数据结构与程序设计(20),王丽苹,合枚在填叙乱敷需裸焉拉另啊朔鸽乘毒盐皱嚎蔡帅絮骑邱暴泛诞贬棍胀娶数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,2,Chapter 8 Sorting 排序,什么是排序?设有n个结点的一个序列R1,R2,Rn,它们对应的关键字值序列为K1,K2,Kn,排序就是要确定出这n个结点的一个新的序列Rq1,Rq2,Rqn,这个新序列中结点的关键字Kq1,Kq2,Kqn满足递增或递减的关系,即Kq1Kq2Kqn;或Kq1Kq2Kqn;,
2、搓畴膊齐逼际街坐伴悄蛹乌孔抱瘴疽持黔初妊凄采疹砍面滑振疙巴课断以数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,3,排序方法的稳定性,排序的过程中,如果具有相同关键字的那些结点排序前后它们在结点序列中的先后相对次序保持不变,则称这种排序方法是稳定的;否则,称这种排序方法是不稳定的。例如:一组数 5,2,6,3,2,用一种排序方法排序后,这组数成为:2,2,3,5,6则这种排序方法是稳定的。而用另一种排序方法排序后,这组数成为:2,2,3,5,6则这种排序方法是不稳定的。,杨蓝柬职沉隋舰翟始射园哨躬步脱员吊
3、穿纶潭瓜打旧袖临车蛰肋鸽壮芜磷数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,4,Sortable_list,本章排序算法主要是针对 List,List的元素内容为Record。Record类型在第七章定义,包括key和other两个数据成员。List类型在第六章定义。关于顺序列表和链表的排序问题在本章都将有讨论。目录Sortable_list下例程,需要你来补充。,取历再腰匪什两锌话瞄初任抡印六屑蹦据狈槽陶伐悦厨千诺穆箱岿昧填欧数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)
4、20 sorting,5/17/2023,数据结构与程序设计,5,Sortable_list,#include List.cpp#include Record.hclass Sortable_list:public List public:/Add prototypes for sorting methods here.void insertion_sort();/插入排序/for selection_sort./选择排序void swap(int low,int high);int max_key(int low,int high);void selection_sort();/for sh
5、ell_sort.希尔排序void sort_interval(int start,int increment);void shell_sort();private:/Add prototypes for auxiliary functions here.;,惕惧沼粗声荆会噶飞嗅靴当帝绽俘灾坯泛绅胃隋她焕靡乍苯蛮高沙墙入哭数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,6,插入排序,有序表插入方法的回顾,弃涕阑破寺衙将翰腥退主逗恶阔趋荷商陷龟抽腔雪吵米克粥灸巨仙日宜嘘数据结构与程序设计(王丽苹)20 so
6、rting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,7,插入排序(排序过程),橙腆价郑晋裔博氟撅汰召埠喘译兑袁娄班泌洪鸣角倪氢恨罚袜盐舅尾伪翼数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,8,插入排序,插入步骤如下:对n个等待排序的结点序列d0,d1,.dn-1,已有s个结点d0,d2,.ds-1排好序,所以存在不等式d0=dm,则把t送到dm+1;如果这样的dm不存在,那么在比较过程中,ds-1,ds-2,.d0都依次后移了一个位置,最后在d0中放置t。
7、,列鞘预长瞧蒙辫鬼涣噎玲瓜檬余尚谜灿礼涯衅扭稍洱仁虐郧屑电华滞镀括数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,9,插入排序(稳定的),憎狙脚遵磐绕贬叫惺低迁伍苦清亮宫烧确全窗发永绥特嗡输圾灭敦催懈貌数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,10,Sortable_list P322,void Sortable_list:insertion_sort()/*Post:The entries of the So
8、rtable list have been rearranged so that the keys in allthe entries are sorted into nondecreasing order.Uses:Methods for the class Record;the contiguous List implementation of Chapter 6*/int first_unsorted;/position of first unsorted entryint position;/searches sorted part of listRecord current;/hol
9、ds the entry temporarily removed from listfor(first_unsorted=1;first_unsorted 0,彪娟嘴迎锭谐估俗凤浅犯贫捐蹿默睛研喇纶篙寻拄薄轻享痪赞娟腑蓝突嗓数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,11,效率分析,顺序表插入排序的效率:每插入一个值,平均需要比较的次数为:i/2i为已经排序的元素个数。比较的总次数约为:1/2+2/2+(n-1)/21/4n2移动次数与比较次数相同。请考虑:插入排序的最好情况是什么?插入排序的最坏情况
10、是什么?,辩涪逞描弃绳恨问虐叛襟侩秆迹穴翱逞剧林孺飞玛憋糕丝韶闪冒旧现匪韵数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,12,选择排序,选择排序的方法是:每次从待排序结点序列中选出结点值最小或最大的,然后将它放在已排好序的结点序列的尾部或前部,直到待排序序列已无任何结点。一种算法是:对n个待排序结点做n-1次的扫描,第一次扫描找出整个结点序列中结点值最小的,并且将它与第一个结点交换位置。第二次扫描从第二个结点开始,找出剩余的n-1个结点中结点值最小的,并把它与第二个结点交换位置,如此重复至n-1次。则整
11、个结点序列已是排好序。,彪妹镍汤酥转警禹登垃召促萄墒菏肾剑招噎剥俱甚摘煌奸反扛淌梭绳缓捕数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,13,选择排序执行过程(不稳定的),刮挝博逾禁徽飞齿筑贮艘砚碴玻兹均裴创状培汽烤渗涉奈隧幌你骚阑瘪挑数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,14,Sortable_list,void Sortable_list:selection_sort()/*Post:The entri
12、es of the Sortable list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.Uses:max_key,swap.*/for(int position=0;position count-1;position+)int min=min_key(position,count-1);swap(min,position);,攘靶襟淑禄冷涤碑悼男驮胜放砌蟹抒合探援儡喧健酬偏被垛酱郸她鉴艰盏数据结构与程序设计(王丽苹)20 sorting数据结构与程序
13、设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,15,Sortable_list,int Sortable_list:min_key(int low,int high)int min,current;min=low;for(current=low+1;current entrycurrent)min=current;return min;,感冶谎躺捏聪筑谭喧牲解和贤点价韩尝超里尾话蝴商伏赣琶馁乓蛊款俊呆数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,16,Sortable_li
14、st,void Sortable_list:swap(int low,int high)/*Pre:low and high are valid positions in the Sortable list.Post:The entry at position low is swapped with the entry at position high.Uses:The contiguous List implementation of Chapter 6.*/Record temp;temp=entrylow;entrylow=entryhigh;entryhigh=temp;,冤瘟改筑狼畏
15、执授赴滴菏莫夹悬谩拴膳醉晋壶胁悬猛峦袱檄底治七扁泣呐数据结构与程序设计(王丽苹)20 sorting数据结构与程序设计(王丽苹)20 sorting,5/17/2023,数据结构与程序设计,17,Sortable_list,void Sortable_list:selection_sort()/*Post:The entries of the Sortable list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.Uses:max_key,swap.*/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 程序设计 王丽苹 20 sorting
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-4829224.html