数据结构与程序设计(王丽苹)21sorting.ppt

《数据结构与程序设计(王丽苹)21sorting.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计(王丽苹)21sorting.ppt（34页珍藏版）》请在三一办公上搜索。

1、5/27/2023,数据结构与程序设计,1,数据结构与程序设计(21),王丽苹,5/27/2023,数据结构与程序设计,2,Chapter 08 排序,插入排序选择排序希尔排序快速排序合并排序堆排序,5/27/2023,数据结构与程序设计,3,Sortable_list新增排序,class Sortable_list:public List public:/Add prototypes for sorting methods here./for quick_sort.void quick_sort();void recursive_quick_sort(int low,int high);in

2、t partition(int low,int high);/for heap_sort.void heap_sort();void build_heap();void insert_heap(const Record,5/27/2023,数据结构与程序设计,4,Mergesort,合并排序思想:We chop the list into two sublists of sizes as nearly equal as possible and then sort them separately.Afterward,we carefully merge the two sorted subli

3、sts into a single sorted list.把待排序的列表划分为分成近似相等的两部分，分别将两个子列表排序，然后再合并成一个完整的列表。,5/27/2023,数据结构与程序设计,5,Mergesort,Mergesort:BOOK P341 FIGURE 8.9Example对26 33 35 29 19 12 22进行合并排序的过程(1)划分为：26 33 35 29 and 19 12 22(2)对子序列1：26 33 35 29 进行合并排序(3)对子序列2：19 12 22进行合并排序(4)合并两个子序列,5/27/2023,数据结构与程序设计,6,Mergesort,

4、void Mergesort(Sortable_list,5/27/2023,数据结构与程序设计,7,Mergesort,void divide_from(Sortable_list/在原序列中删除该节点,5/27/2023,数据结构与程序设计,8,Mergesort,void combine(Sortable_list,5/27/2023,数据结构与程序设计,9,while(mfirstsortlist.size()Record x;firstsortlist.retrieve(m,x);tmp.insert(i+,x);m+;while(nsecondsortlist.size()Reco

5、rd y;secondsortlist.retrieve(n,y);tmp.insert(i+,y);n+;firstsortlist=tmp;,5/27/2023,数据结构与程序设计,10,Mergesort For Linked Lists,class Sortable_list:public List public:/Add prototypes for sorting methods here.void insertion_sort();private:/Add prototypes for auxiliary functions here.;/对sub_list进行合并排序void

6、recursive_merge_sort(Node*,5/27/2023,数据结构与程序设计,11,Mergesort For Linked Lists,void recursive_merge_sort(Node*,5/27/2023,数据结构与程序设计,12,Mergesort For Linked Lists,Node*divide_from(Node*sub_list)/P346/*Post:The list of nodes referenced by sub_list has been reduced to its first half,and a pointer to the f

7、irst node in the second half of the sublist is returned.If thesublist has an odd number of entries,then its first half will be one entry largerthan its second.*/Node*position,/traverses the entire list*midpoint,/moves at half speed of position to midpoint*second_half;if(midpoint=sub_list)=NULL)retur

8、n NULL;/List is empty.position=midpoint-next;while(position!=NULL)/Move position twice for midpoints one move.position=position-next;if(position!=NULL)midpoint=midpoint-next;position=position-next;second_half=midpoint-next;midpoint-next=NULL;return second_half;,5/27/2023,数据结构与程序设计,13,Mergesort For L

9、inked Lists,midpoint,position,midpoint,position,midpoint,position,midpoint,position,5/27/2023,数据结构与程序设计,14,Node*merge(Node*first,Node*second)Node*last_sorted;/points to the last node of sorted listNode combined;/dummy first node,points to merged listlast_sorted=,5/27/2023,数据结构与程序设计,15,Mergesort For

10、Linked Lists,combined,last_sorted,first,last_sorted,head,5/27/2023,数据结构与程序设计,16,Mergesort For Linked Lists,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 recursive_merge_sort Method:endl;recursive_merge_sort(

11、mylist.Get_head();mylist.traverse(print);coutendlUse insertion_sort Method:endl;mylist.insertion_sort();mylist.traverse(print);cin.get();,5/27/2023,数据结构与程序设计,17,Mergesort For Linked Lists,template Node*,5/27/2023,数据结构与程序设计,18,Quick_sort,Quicksort思想:We first choose some key from the list for which,we

12、 hope,about half the keys will come before and half after.Call this key the pivot（轴点）.Then we partition the items so that all those with keys less than the pivot come in one sublist,and all those with greater keys come in another.Then we sort the two reduced lists separately,put the sublists togethe

13、r,and the whole list will be in order.,5/27/2023,数据结构与程序设计,19,Quicksort:BOOK P343 FIGURE 8.10,19,5/27/2023,数据结构与程序设计,20,Quicksort,66 30 35 29 19 32 35,29 30 35 66 19 32 35,Pivot=29,29 19 35 66 30 32 35,19 29 35 66 30 32 35,35 66 30 32 35 Pivot=30,30 66 35 32 35,66 35 32 35 Pivot=35,35 66 32 35,35 32

14、 66 35,32 35 66 35,66 35 Pivot=66,66 35,35 66,5/27/2023,数据结构与程序设计,21,Quicksort,void Sortable_list:quick_sort()/*Post:The entries of the Sortable list have been rearranged so that their keys are sorted into nondecreasing order.Uses:Contiguous List implementation of Chapter 6,recursive quick sort.*/re

15、cursive_quick_sort(0,count-1);,5/27/2023,数据结构与程序设计,22,Quicksort,void Sortable_list:recursive_quick_sort(int low,int high)/*Pre:low and high are valid positions in the Sortable list.Post:The entries of the Sortable list have been rearranged so that their keys are sorted into nondecreasing order.Uses:

16、Contiguous List implementation of Chapter 6,recursive quick sort,and partition.*/int pivot_position;if(low high)/Otherwise,no sorting is needed.pivot_position=partition(low,high);recursive_quick_sort(low,pivot_position-1);recursive_quick_sort(pivot_position+1,high);,5/27/2023,数据结构与程序设计,23,Quicksort,

17、int Sortable_list:partition(int low,int high)/*Pre:low and high are valid positions of the Sortable list,with low=high.Post:The center(or left center)entry in the range between indices low and high of the Sortable list has been chosen as a pivot.All entries of the Sortable list between indices low a

18、nd high,inclusive,have been rearranged so that those with keys less than the pivot come before the pivot and the remaining entries come after the pivot.The final position of the pivot is returned.Uses:swap(int i,int j)(interchanges entries in positions i and j of a Sortable list),the contiguous List

19、 implementation of Chapter 6,and methods for the class Record.*/,5/27/2023,数据结构与程序设计,24,int Sortable_list:partition(int low,int high)Record pivot;int i,/used to scan through the listlast_small;/position of the last key less than pivot，记录小于抽点的数值下标swap(low,(low+high)/2);/将抽点与最小位置的值交换，并放置于最小的位置pivot=en

20、trylow;/First entry is now pivot.last_small=low;/初始化为最小的位置for(i=low+1;i=high;i+)if(entryi pivot)last_small+;/从low+1开始放置。swap(last_small,i);/Move large entry to right and small to left.swap(low,last_small);/Put the pivot into its proper position.return last_small;,5/27/2023,数据结构与程序设计,25,Quicksort P35

21、4 分析,LOW,pivot,last_small,HIGH,代码走读：16 33 15 29 49 25 32 low=0；high=6,5/27/2023,数据结构与程序设计,26,HOMEWORK,课后作业，请用作业本完成BOOK P343 E1,E2,5/27/2023,数据结构与程序设计,27,Heap_sort,BOOK P364DEFINITION A heap is a list in which each entry contains a key,and,for all positions k in the list,the key at position k is at l

22、east as large as the keys in positions 2k+1 and 2k+2,provided these positions exist in the list.这样的堆也称为大根堆。,5/27/2023,数据结构与程序设计,28,Heap_sort Example,5/27/2023,数据结构与程序设计,29,Heap_sort Example,5/27/2023,数据结构与程序设计,30,Heap_sort BOOK P367 FIGURE 8.18,void Sortable_list:heap_sort()/*Post:The entries of the

23、 Sortable list have been rearranged so that their keysare sorted into nondecreasing order.Uses:The contiguous List implementation of Chapter 6,build_heap,and insert_heap.*/Record current;/temporary storage for moving entriesint last_unsorted;/Entries beyond last unsorted have been sorted.build_heap(

24、);/First phase:Turn the list into a heap.for(last_unsorted=count-1;last_unsorted 0;last_unsorted-)current=entrylast_unsorted;/Extract last entry from list.entrylast_unsorted=entry0;/Move top of heap to the endinsert_heap(current,0,last_unsorted-1);/Restore the heap,5/27/2023,数据结构与程序设计,31,Heap_sort,v

25、oid Sortable_list:insert_heap(const Record¤t,int low,int high)/*Pre:The entries of the Sortable list between indices low+1 and high,inclusive,form a heap.The entry in position low will be discarded.Post:The entry current has been inserted into the Sortable list and theentries rearranged so tha

26、t the entries between indices low and high,inclusive,form a heap.Uses:The class Record,and the contiguous List implementation of Chapter 6.*/Low+1到High满足堆的结构。插入Current。经过插入后，最终使得从下标low到下标high形成一个新堆,5/27/2023,数据结构与程序设计,32,Heap_sort,void Sortable_list:insert_heap(const Record,5/27/2023,数据结构与程序设计,33,He

27、ap_sort BOOK P368,void Sortable_list:build_heap()/*Post:The entries of the Sortable list have been rearranged so that it becomes a heap.Uses:The contiguous List implementation of Chapter 6,and insert heap.*/int low;/All entries beyond the position low form a heap./非叶子结点K的满足的条件是：2K+1=0;low-)Record current=entrylow;insert_heap(current,low,count-1);,5/27/2023,数据结构与程序设计,34,Heap_sort BOOK P368,走读代码，build_heap()说明以下数据建堆的过程：26 5 77 1 61 11 59 15 48 19结果为：77 61 59 48 19 11 26 15 1 5,