数据结构与程序设计王丽苹20sorting

1、10/21/2021数据结构与程序设计 1数据结构与程序设计数据结构与程序设计(20) (20) 王丽苹10/21/2021数据结构与程序设计 2chapter 8 sorting 排序n什么是排序？什么是排序？n设有设有n个结点的一个序列个结点的一个序列r1，r2，rn，它们对应，它们对应的关键字值序列为的关键字值序列为k1，k2，kn，排序就是要确，排序就是要确定出这定出这n个结点的一个新的序列个结点的一个新的序列rq1,rq2, rqn，这，这个新序列中结点的关键字个新序列中结点的关键字kq1，kq2，kqn满足递满足递增或递减的关系，即增或递减的关系，即kq1kq2kqn; 或或kq1

2、kq2kqn；10/21/2021数据结构与程序设计 3排序方法的稳定性n排序的过程中，如果具有相同关键字的那些结点排序前后它们在结点序列中的先后相对次序保持不变，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例如：一组数 5，2，6，3， 2 ，用一种排序方法排序后，这组数成为：2， 2 ，3，5，6n则这种排序方法是稳定的。n而用另一种排序方法排序后，这组数成为：n 2 ， 2 ，3，5，6n则这种排序方法是不稳定的。10/21/2021数据结构与程序设计 4sortable_listn本章排序算法主要是针对本章排序算法主要是针对 list，list的的元素内容为元素内容为re

3、cord。nrecord类型在第七章定义，包括类型在第七章定义，包括key和和other两个数据成员。两个数据成员。nlist类型在第六章定义。关于顺序列表和类型在第六章定义。关于顺序列表和链表的排序问题在本章都将有讨论。链表的排序问题在本章都将有讨论。n目录目录sortable_list下例程下例程,需要你来补充。需要你来补充。10/21/2021数据结构与程序设计 5sortable_listn#include list.cppn#include record.hnclass sortable_list: public list npublic: / add prototypes for

4、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 auxili

5、ary functions here.n;10/21/2021数据结构与程序设计 6插入排序n有序表插入方法的回顾10/21/2021数据结构与程序设计 7插入排序（排序过程）10/21/2021数据结构与程序设计 8插入排序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

6、的值送到一个临时的变量的值送到一个临时的变量t,t,然后用然后用t t值依次与排好值依次与排好序的结点序列中的序的结点序列中的ds-1,ds-2.d0ds-1,ds-2.d0进行比较进行比较, ,并且将比并且将比t t大的结点依次右移一个位置大的结点依次右移一个位置. .如果存在某个如果存在某个dm(0=m=s-dm(0=m=dmt=dm, ,则把则把t t送到送到dm+1;dm+1;如果这样的如果这样的dmdm不存在不存在, ,那那么在比较过程中么在比较过程中,ds-1,ds-2,.d0,ds-1,ds-2,.d0都依次后移了一个都依次后移了一个位置位置, ,最后在最后在d0d0中放置中放置

7、t t。10/21/2021数据结构与程序设计 9插入排序（稳定的）10/21/2021数据结构与程序设计 10sortable_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 contiguou

8、s 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 & entry

9、position - 1 current);nentryposition = current;nn 10/21/2021数据结构与程序设计 11效率分析n顺序表插入排序的效率：n每插入一个值，平均需要比较的次数为：i/2i为已经排序的元素个数。比较的总次数约为：1/2+2/2+(n-1)/21/4n2移动次数与比较次数相同。n请考虑：n插入排序的最好情况是什么？n插入排序的最坏情况是什么？10/21/2021数据结构与程序设计 12选择排序选择排序 n选择排序的方法是：每次从待排序结点序列中选选择排序的方法是：每次从待排序结点序列中选出结点值出结点值最小或最大最小或最大的，然后将它放在已排好序

10、的，然后将它放在已排好序的结点序列的的结点序列的尾部或前部尾部或前部，直到待排序序列已无，直到待排序序列已无任何结点。任何结点。n一种算法是：对一种算法是：对n n个待排序结点做个待排序结点做n-1n-1次的扫描，第一次扫次的扫描，第一次扫描找出整个结点序列中结点值最小的，并且将它与第一个描找出整个结点序列中结点值最小的，并且将它与第一个结点交换位置。第二次扫描从第二个结点开始，找出剩余结点交换位置。第二次扫描从第二个结点开始，找出剩余的的n-1n-1个结点中结点值最小的，并把它与第二个结点交换个结点中结点值最小的，并把它与第二个结点交换位置位置，如此重复至，如此重复至n-1n-1次。则整个结

11、点序列已是排好序。次。则整个结点序列已是排好序。 10/21/2021数据结构与程序设计 13选择排序执行过程选择排序执行过程(不不稳定的) 10/21/2021数据结构与程序设计 14sortable_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 ,swa

12、p . */nnfor (int position = 0; position count-1; position+) nint min = min_key(position, count-1);nswap(min, position);n n10/21/2021数据结构与程序设计 15sortable_listnint sortable_list : min_key(int low, int high)nnint min, current;nmin = low;nfor (current = low + 1; current entrycurrent)nmin = current;nretu

13、rn min;n10/21/2021数据结构与程序设计 16sortable_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

14、;ntemp = entrylow;nentrylow = entryhigh;nentryhigh = temp;n10/21/2021数据结构与程序设计 17sortable_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

15、(int position = count - 1; position 0; position-) nint max = max_key(0, position);nswap(max, position);n n10/21/2021数据结构与程序设计 18sortable_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

16、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;n10/21/2021数据结构

17、与程序设计 19选择排序分析n特点： 选择排序的最坏情况和最好情况下的实际没有太大区别。即选择排序对于原始记录的顺序不敏感。n选择排序的比较次数分析： n每一次的比较次数求和：n(n-1)+(n-2)+.+11/2n2n总移动次数为：3(n-1)10/21/2021数据结构与程序设计 20选择和插入排序对比10/21/2021数据结构与程序设计 21shell sortn在插入排序中，比较结点的值时，每次至多把结点移动一个位置（当tdm时，才把dm向“后” 移动一位）。希尔排序的想法是：如果能够把相对位置较远的结点进行比较，使得结点在比较后能够一次移动较大的距离。这样处理可以把值较小的结点尽快

18、往前移，值较大的结点尽快往后移，希望以此提高排序的效率。 n算法如下：n首先将整个待排序结点序列分割成若干个子序列，然后对各个子序列分别执行插入排序；当各个子序列排好序后，整个文件就有序了些；多次重复上述过程，最终实现全部结点的排序。10/21/2021数据结构与程序设计 22shell sortn第一步，increment=510/21/2021数据结构与程序设计 23shell sortn第二步，increment=3 第三步，increment=110/21/2021数据结构与程序设计 24shell sortnbook p334 figure 8.7n取不同的增量序列，会有不同的比较次

19、数。另外，至今没有一种最好的增量序列。但是肯定的是，无论哪种增量序列，最后一个增量值必须为。n大量实例表明：希尔排序的速度要比插入排序快得多。另外，希尔排序是不稳定的。10/21/2021数据结构与程序设计 25shell 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_in

20、terval */nnint increment, / spacing of entries in sublistn start; / starting point of sublistnincrement = count;ndo nincrement = increment/3 + 1;nfor (start = 0; start 1);n 10/21/2021数据结构与程序设计 26shell sort (compare with p322)void sortable_list : sort_interval(int start, int increment)int first_unsor

21、ted; / 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 cur

22、rent);entryposition = current;/上述算法和插入排序的区别上述算法和插入排序的区别10/21/2021数据结构与程序设计 27mainnvoid main()nsortable_list mylist;nfor(int i=0; i10; i+) mylist.insert(i,record(10-i,10);ncoutthe list is: endl;nmylist.traverse(print);nncoutendluse insertion_sort method:endl;nmylist.insertion_sort();nmylist.traverse(

23、print);ncoutendluse selection_sort method:endl;nmylist.selection_sort();nmylist.traverse(print);nncoutendluse shell_sort method:endl;nmylist.shell_sort();nmylist.traverse(print);ncin.get();n10/21/2021数据结构与程序设计 28linked_sortable_listn上机：上机： n（1）请上机完成链表的插入排序操作，）请上机完成链表的插入排序操作，参考目录参考目录linked_sortable_l

24、ist下例程下例程nbook p325 figure 8.410/21/2021数据结构与程序设计 29linked_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_unso