数据结构与程序设计(王丽苹)20sorting.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(20),王丽苹,5/27/2023,数据结构与程序设计,2,Chapter 8 Sorting 排序,什么是排序？设有n个结点的一个序列R1，R2，Rn，它们对应的关键字值序列为K1，K2，Kn，排序就是要确定出这n个结点的一个新的序列Rq1,Rq2,Rqn，这个新序列中结点的关键字Kq1，Kq2，Kqn满足递增或递减的关系，即Kq1Kq2Kqn;或Kq1Kq2Kqn；,5/27/2023,数据结构与程序设计,3,排序方法的稳定性,排序的过程中，如果具有相同关键字的那些结点排序前后它们在结点序列中的先后相对次序保持不变，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例如：一组数 5，2，6，3，2，用一种排序方法排序后，这组数成为：2，2，3，5，6则这种排序方法是稳定的。而用另一种排序方法排序后，这组数成为：2，2，3，5，6则这种排序方法是不稳定的。,5/27/2023,数据结构与程序设计,4,Sortable_list,本章排序算法主要是针对 List，List的元素内容为Record。Record类型在第七章定义，包括key和other两个数据成员。List类型在第六章定义。关于顺序列表和链表的排序问题在本章都将有讨论。目录Sortable_list下例程,需要你来补充。,5/27/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 shell_sort.希尔排序void sort_interval(int start,int increment);void shell_sort();private:/Add prototypes for auxiliary functions here.;,5/27/2023,数据结构与程序设计,6,插入排序,有序表插入方法的回顾,5/27/2023,数据结构与程序设计,7,插入排序（排序过程）,5/27/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。,5/27/2023,数据结构与程序设计,9,插入排序（稳定的）,5/27/2023,数据结构与程序设计,10,Sortable_list P322,void Sortable_list:insertion_sort()/*Post:The entries of the Sortable 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;/holds the entry temporarily removed from listfor(first_unsorted=1;first_unsorted 0,5/27/2023,数据结构与程序设计,11,效率分析,顺序表插入排序的效率：每插入一个值，平均需要比较的次数为：i/2i为已经排序的元素个数。比较的总次数约为：1/2+2/2+(n-1)/21/4n2移动次数与比较次数相同。请考虑：插入排序的最好情况是什么？插入排序的最坏情况是什么？,5/27/2023,数据结构与程序设计,12,选择排序,选择排序的方法是：每次从待排序结点序列中选出结点值最小或最大的，然后将它放在已排好序的结点序列的尾部或前部，直到待排序序列已无任何结点。一种算法是：对n个待排序结点做n-1次的扫描，第一次扫描找出整个结点序列中结点值最小的，并且将它与第一个结点交换位置。第二次扫描从第二个结点开始，找出剩余的n-1个结点中结点值最小的，并把它与第二个结点交换位置，如此重复至n-1次。则整个结点序列已是排好序。,5/27/2023,数据结构与程序设计,13,选择排序执行过程(不稳定的),5/27/2023,数据结构与程序设计,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_key(position,count-1);swap(min,position);,5/27/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;,5/27/2023,数据结构与程序设计,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 position high.Uses:The contiguous List implementation of Chapter 6.*/Record temp;temp=entrylow;entrylow=entryhigh;entryhigh=temp;,5/27/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.*/for(int position=count-1;position 0;position-)int max=max_key(0,position);swap(max,position);,5/27/2023,数据结构与程序设计,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.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;,5/27/2023,数据结构与程序设计,19,选择排序分析,特点：选择排序的最坏情况和最好情况下的实际没有太大区别。即选择排序对于原始记录的顺序不敏感。选择排序的比较次数分析：每一次的比较次数求和：(n-1)+(n-2)+.+11/2n2总移动次数为：3(n-1),5/27/2023,数据结构与程序设计,20,选择和插入排序对比,5/27/2023,数据结构与程序设计,21,SHELL SORT,在插入排序中，比较结点的值时，每次至多把结点移动一个位置（当tdm时，才把dm向“后”移动一位）。希尔排序的想法是：如果能够把相对位置较远的结点进行比较，使得结点在比较后能够一次移动较大的距离。这样处理可以把值较小的结点尽快往前移，值较大的结点尽快往后移，希望以此提高排序的效率。算法如下：首先将整个待排序结点序列分割成若干个子序列，然后对各个子序列分别执行插入排序；当各个子序列排好序后，整个文件就有序了些；多次重复上述过程，最终实现全部结点的排序。,5/27/2023,数据结构与程序设计,22,SHELL SORT,第一步，increment=5,5/27/2023,数据结构与程序设计,23,SHELL SORT,第二步，increment=3 第三步，increment=1,5/27/2023,数据结构与程序设计,24,SHELL SORT,BOOK P334 FIGURE 8.7取不同的增量序列，会有不同的比较次数。另外，至今没有一种最好的增量序列。但是肯定的是，无论哪种增量序列，最后一个增量值必须为。大量实例表明：希尔排序的速度要比插入排序快得多。另外，希尔排序是不稳定的。,5/27/2023,数据结构与程序设计,25,SHELL SORT,void Sortable_list:shell_sort()/*Post:The entries of theSortable list have been rearranged so that the keys in allthe entries are sorted into nondecreasing order.Uses:sort_interval*/int increment,/spacing of entries in sublist start;/starting point of sublistincrement=count;do increment=increment/3+1;for(start=0;start 1);,5/27/2023,数据结构与程序设计,26,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 start/上述算法和插入排序的区别,5/27/2023,数据结构与程序设计,27,Main,void main()Sortable_list mylist;for(int i=0;i10;i+)mylist.insert(i,Record(10-i,10);coutThe list is:endl;mylist.traverse(print);coutendlUse insertion_sort Method:endl;mylist.insertion_sort();mylist.traverse(print);coutendlUse selection_sort Method:endl;mylist.selection_sort();mylist.traverse(print);coutendlUse shell_sort Method:endl;mylist.shell_sort();mylist.traverse(print);cin.get();,5/27/2023,数据结构与程序设计,28,Linked_Sortable_list,上机：（1）请上机完成链表的插入排序操作，参考目录Linked_Sortable_list下例程BOOK P325 FIGURE 8.4,5/27/2023,数据结构与程序设计,29,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;,5/27/2023,数据结构与程序设计,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=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),5/27/2023,数据结构与程序设计,31,Sortable_list上机,(2)实现Sortable_list中的插入排序，选择排序和希尔排序上机文件在Sortable_list目录下。,5/27/2023,数据结构与程序设计,32,课后作业,P327 8.2节 E1（d）（e）P333 8.3节 E1（d）（e）P335 8.4节 E2,
