《数据结构与程序设计（王丽苹）20 sorting.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）20 sorting.ppt（32页珍藏版）》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(20),王丽苹 ,合枚在填叙乱敷需裸焉拉另啊朔鸽乘毒盐皱嚎蔡帅絮骑邱暴泛诞贬棍胀娶数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,2,Chapter 8 Sorting 排序,什么是排序？ 设有n个结点的一个序列R1，R2，Rn，它们对应的关键字值序列为K1，K2，Kn，排序就是要确定出这n个结点的一个新的序列Rq1,Rq2, Rqn，这个新序列中结点的关键字Kq1，Kq2，Kqn满足递增或递减的关系，即Kq1Kq2Kqn; 或Kq1Kq2K
2、qn；,搓畴膊齐逼际街坐伴悄蛹乌孔抱瘴疽持黔初妊凄采疹砍面滑振疙巴课断以数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,3,排序方法的稳定性,排序的过程中，如果具有相同关键字的那些结点排序前后它们在结点序列中的先后相对次序保持不变，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例如：一组数 5，2，6，3， 2 ，用一种排序方法排序后，这组数成为： 2， 2 ，3，5，6 则这种排序方法是稳定的。 而用另一种排序方法排序后，这组数成为： 2 ， 2 ，3，5，6 则这种排序方法是不稳定的。,杨
3、蓝柬职沉隋舰翟始射园哨躬步脱员吊穿纶潭瓜打旧袖临车蛰肋鸽壮芜磷数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,4,Sortable_list,本章排序算法主要是针对 List，List的元素内容为Record。 Record类型在第七章定义，包括key和other两个数据成员。 List类型在第六章定义。关于顺序列表和链表的排序问题在本章都将有讨论。 目录Sortable_list下例程,需要你来补充。,取历再腰匪什两锌话瞄初任抡印六屑蹦据狈槽陶伐悦厨千诺穆箱岿昧填欧数据结构与程序设计（王丽苹）20 so
4、rting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,5,Sortable_list,#include “List.cpp“ #include “Record.h“ class 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, in
5、t high); void selection_sort( ); /for shell_sort. 希尔排序 void sort_interval(int start, int increment); void shell_sort(); private: / Add prototypes for auxiliary functions here. ;,惕惧沼粗声荆会噶飞嗅靴当帝绽俘灾坯泛绅胃隋她焕靡乍苯蛮高沙墙入哭数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,6,插入排序,有序表插入方法的回顾,弃涕阑
6、破寺衙将翰腥退主逗恶阔趋荷商陷龟抽腔雪吵米克粥灸巨仙日宜嘘数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,7,插入排序（排序过程）,橙腆价郑晋裔博氟撅汰召埠喘译兑袁娄班泌洪鸣角倪氢恨罚袜盐舅尾伪翼数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,8,插入排序,插入步骤如下: 对n个等待排序的结点序列d0,d1,.dn-1,已有s个结点d0,d2,ds-1排好序,所以存在不等式d0=dm,则把t送到dm+1;如果这样的d
7、m不存在,那么在比较过程中,ds-1,ds-2,.d0都依次后移了一个位置,最后在d0中放置t。,列鞘预长瞧蒙辫鬼涣噎玲瓜檬余尚谜灿礼涯衅扭稍洱仁虐郧屑电华滞镀括数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,9,插入排序（稳定的）,憎狙脚遵磐绕贬叫惺低迁伍苦清亮宫烧确全窗发永绥特嗡输圾灭敦催懈貌数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,10,Sortable_list P322,void Sortable_l
8、ist : insertion_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: Methods for the class Record ; the contiguous List implementation of Chapter 6 */ int first_unsorted; / position of first unsorted ent
9、ry int position; / searches sorted part of list Record current; / holds the entry temporarily removed from list for (first_unsorted = 1; first_unsorted 0 ,彪娟嘴迎锭谐估俗凤浅犯贫捐蹿默睛研喇纶篙寻拄薄轻享痪赞娟腑蓝突嗓数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,11,效率分析,顺序表插入排序的效率： 每插入一个值，平均需要比较的次数为：i/2 i为
10、已经排序的元素个数。 比较的总次数约为：1/2+2/2+(n-1)/21/4n2 移动次数与比较次数相同。 请考虑： 插入排序的最好情况是什么？ 插入排序的最坏情况是什么？,辩涪逞描弃绳恨问虐叛襟侩秆迹穴翱逞剧林孺飞玛憋糕丝韶闪冒旧现匪韵数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,12,选择排序,选择排序的方法是：每次从待排序结点序列中选出结点值最小或最大的，然后将它放在已排好序的结点序列的尾部或前部，直到待排序序列已无任何结点。 一种算法是：对n个待排序结点做n-1次的扫描，第一次扫描找出整个结点序
11、列中结点值最小的，并且将它与第一个结点交换位置。第二次扫描从第二个结点开始，找出剩余的n-1个结点中结点值最小的，并把它与第二个结点交换位置，如此重复至n-1次。则整个结点序列已是排好序。,彪妹镍汤酥转警禹登垃召促萄墒菏肾剑招噎剥俱甚摘煌奸反扛淌梭绳缓捕数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,13,选择排序执行过程(不稳定的),刮挝博逾禁徽飞齿筑贮艘砚碴玻兹均裴创状培汽烤渗涉奈隧幌你骚阑瘪挑数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/
12、2020,数据结构与程序设计,14,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 . */ for (int position = 0; position count-1; position+) int min = min_ke
13、y(position, count-1); swap(min, position); ,攘靶襟淑禄冷涤碑悼男驮胜放砌蟹抒合探援儡喧健酬偏被垛酱郸她鉴艰盏数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,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; r
14、eturn min; ,感冶谎躺捏聪筑谭喧牲解和贤点价韩尝超里尾话蝴商伏赣琶馁乓蛊款俊呆数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,16,Sortable_list,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
15、position high . Uses: The contiguous List implementation of Chapter 6. */ Record temp; temp = entrylow; entrylow = entryhigh; entryhigh = temp; ,冤瘟改筑狼畏执授赴滴菏莫夹悬谩拴膳醉晋壶胁悬猛峦袱檄底治七扁泣呐数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,17,Sortable_list,void Sortable_list : selection_sort(
16、) /* 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 . */ for (int position = count - 1; position 0; position-) int max = max_key(0, position); swap(max, position); ,膳单植互打灿陶篇满撩蕾吾擒公毋泽苞烙攻制舷崔还嘴颗娱腊靴人
17、驴毡慌数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,18,Sortable_list,int Sortable_list : max_key(int low, int high) /* Pre: low and high are valid positions in the Sortable list and low = high . Post: The position of the entry between low and high with the largest key is returned
18、. Uses: The class Record . The contiguous List implementation of Chapter 6. */ int largest, current; largest = low; for (current = low + 1; current = high; current+) if (entrylargest entrycurrent) largest = current; return largest; ,直蔫耽胰祝砌毛靠善兔循民疵躁寝论镐双畏嗣奶厦区菩伯擞柳骑宿申畅芽数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王
19、丽苹）20 sorting,4/16/2020,数据结构与程序设计,19,选择排序分析,特点： 选择排序的最坏情况和最好情况下的实际没有太大区别。即选择排序对于原始记录的顺序不敏感。 选择排序的比较次数分析： 每一次的比较次数求和： (n-1)+(n-2)+.+11/2n2 总移动次数为：3(n-1),湛早弧坐旗锦邻文价揭寥随背愧膝配柠唁仗苦嫁鳖白顽是褐磁币杀太三秆数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,20,选择和插入排序对比,黑刻韦吗罐冯框趟罗矫淆拳跃崇图擦乱魄富棕秩酵饭佃赂竖娠秃案潘帚躇数据
20、结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,21,SHELL SORT,在插入排序中，比较结点的值时，每次至多把结点移动一个位置（当tdm时，才把dm向“后” 移动一位）。希尔排序的想法是：如果能够把相对位置较远的结点进行比较，使得结点在比较后能够一次移动较大的距离。这样处理可以把值较小的结点尽快往前移，值较大的结点尽快往后移，希望以此提高排序的效率。 算法如下： 首先将整个待排序结点序列分割成若干个子序列，然后对各个子序列分别执行插入排序；当各个子序列排好序后，整个文件就有序了些；多次重复上述过程，最终
21、实现全部结点的排序。,摄罗焰过泽穗皋智兴右锄茎捷萨形鸡艾灸槛换卑咸穆窑宾瘩尤掂饺疾到渡数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,22,SHELL SORT,第一步，increment=5,邱今痪罕虽烂森辙独枷色疼辖葵脱烁角永占颅拔祸撩审剪慧蕾纪典猖约怜数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,23,SHELL SORT,第二步，increment=3 第三步，increment=1,卑倍官万野茂鸯啡恃曙功
22、彦辞反雇搞爆夜角赦度畏串闪能狡少正冀碉姥膳数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,24,SHELL SORT,BOOK P334 FIGURE 8.7 取不同的增量序列，会有不同的比较次数。另外，至今没有一种最好的增量序列。但是肯定的是，无论哪种增量序列，最后一个增量值必须为。 大量实例表明：希尔排序的速度要比插入排序快得多。另外，希尔排序是不稳定的。,欺烯恢初焚馒鄂琵现增咎纷走濒醛电桌郁崎嗡写嘶殖氖泳恐拦勃链匙糯花数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20
23、sorting,4/16/2020,数据结构与程序设计,25,SHELL SORT,void Sortable_list : shell_sort( ) /* Post: The entries of theSortable list have been rearranged so that the keys in all the entries are sorted into nondecreasing order. Uses: sort_interval */ int increment, / spacing of entries in sublist start; / starting
24、point of sublist increment = count; do increment = increment/3 + 1; for (start = 0; start 1); ,洛枕宗溃兴朝霄呻坟谆套芥浑撩什在肇训衡粮勇晰饿加墙岿庚框砍拇乏聚数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,26,SHELL SORT (Compare with P322),void Sortable_list : sort_interval(int start, int increment) int first
25、_unsorted; / position of first unsorted entry int position; / searches sorted part of list Record current; / holds the entry temporarily removed from list for (first_unsorted = start + increment; first_unsorted start /上述算法和插入排序的区别,磐共城盼电懒信婆脉厦淆砾耕学犯憋碍棱水掳熙咸牵炳拳图糊言郴肢铺减数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹
26、）20 sorting,4/16/2020,数据结构与程序设计,27,Main,void main() Sortable_list mylist; for(int i=0; i10; i+) mylist.insert(i,Record(10-i,10); cout“The list is: “endl; mylist.traverse(print); coutendl“Use insertion_sort Method:“endl; mylist.insertion_sort(); mylist.traverse(print); coutendl“Use selection_sort Met
27、hod:“endl; mylist.selection_sort(); mylist.traverse(print); coutendl“Use shell_sort Method:“endl; mylist.shell_sort(); mylist.traverse(print); cin.get(); ,提茸轨汉源狮烧蕊绷嗡怪榨料会灾攫是红音骨蜗锅泽选背实甫动椭跺淖纠数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,28,Linked_Sortable_list,上机： （1）请上机完成链表的插入排序操
28、作，参考目录Linked_Sortable_list下例程 BOOK P325 FIGURE 8.4,酥结煮汤鳞囚幅静责隶蔫脾俭扰读蔷酋微寺版疗演岿井贞稿案岿拙咯壕丢数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,29,Linked_Sortable_list(book p324),void Sortable_list : insertion_sort( ) Node *first_unsorted, / the first unsorted node to be inserted *last_sorte
29、d, / tail of the sorted sublist *current, / used to traverse the sorted sublist *trailing; / one position behindcurrent if (head != NULL) / Otherwise, the empty list is already sorted. last_sorted = head; / The first node alone makes a sorted sublist. while (last_sorted-next != NULL) first_unsorted
30、= last_sorted-next; if (first_unsorted-entry entry) / Insert *first_unsorted at the head of the sorted list: last_sorted-next = first_unsorted-next; first_unsorted-next = head; head = first_unsorted; ,盎换读脑秀色憎擅奈屡凋剂念奥左毛规全狮重狠越珊哀挞顷验织柱瘟集启数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设
31、计,30,else / Search the sorted sublist to insert*first_unsorted : trailing = head; current = trailing-next; while (first_unsorted-entry current-entry) trailing = current; current = trailing-next; / *first_unsorted now belongs between*trailing and*current . if (first_unsorted = current) last_sorted =
32、first_unsorted; / already in right position else last_sorted-next = first_unsorted-next; first_unsorted-next = current; trailing-next = first_unsorted; ,Linked_Sortable_list(book p324),伦瞩抠咨愈釉千西骄跌悯头宝熟圆誊踏磺棍宰缕殃组警捧颐猎侵彦依詹赔数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,31,Sortable_li
33、st上机,(2) 实现Sortable_list中的插入排序，选择排序和希尔排序 上机文件在Sortable_list目录下。,胜冰浇镇俩拨计魔犯将弯墟疮壤柯韧城磅崇九钩存妆薪匪义万菌讣胁速茅数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,4/16/2020,数据结构与程序设计,32,课后作业,P327 8.2节 E1（d）（e） P333 8.3节 E1（d）（e） P335 8.4节 E2,株翠狰彻愈隧稼塞橡速淀成敷郑浑惠厦豢宾蕾浓泥宅蒜税仓绚涵提纽拽砖数据结构与程序设计（王丽苹）20 sorting数据结构与程序设计（王丽苹）20 sorting,