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