软件工程 算法课程 第7章

《软件工程 算法课程 第7章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、软件工程算法课程第7章本文由xuji1230贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。第7章排序(sorting)章排序()7.1概述7.2插入排序7.3交换排序7.4选择排序7.5归并排序7.6基数排序本章小结7.1概述1.排序:n个对象的序列排序:个对象的序列个对象的序列R[0],R[1],R[2],…R[n-1]按其关键码的大小,进行由小到大(非递减)按其关键码的大小,进行由小到大(非递减)或由大到小(非递增)的次序重新排序的.由大到小(非递增)的次序重新排序的.2.关键码(key)关键码()关键码3.

2、两大类:内排序:对内存中的n个对象进行排序.两大类:内排序:对内存中的个对象进行排序个对象进行排序.两大类外排序:内存放不下,外排序:内存放不下,还要使用外存的排序.排序.4.排序算法的稳定性:排序算法的稳定性:如果待排序的对象序列中,如果待排序的对象序列中,含有多个关键码值相等的对象,用某种方法排序后,相等的对象,用某种方法排序后,这些对象的相对次序不变的,则是稳定的,相对次序不变的,则是稳定的,否则为不稳定的.8120158228例:35818215202835稳定的5.排序种类:排序种类:–内排序内排序插入排序,交换排序,选择排序,归并排序,插入排

3、序,交换排序,选择排序,归并排序,基数排序–外排序外排序6.排序的算法分析:排序的算法分析:1)时间开销比较次数,移动次数比较次数,)时间开销—比较次数2)所需的附加空间)下面是静态排序过程中所用到的数据表类定义:下面是静态排序过程中所用到的数据表类定义:vector01currentsize-1maxsize-1keyotherdata……constintDefaultSize=100;templateclassdatalisttemplateclassElement{private:Typekey;fiel

4、dotherdata;public:Typegetkey(){returnkey;}voidsetKey(constTypex){key=x;}Element&operator=(Element&x){this=x;}intoperator==(Type&x){return!(this

5、

6、xx);}intoperator>=(Type&x){return!(thisx;}}templateclassdatalist{public:d

7、atalist(intMaxSz=DefaultSize):MaxSize(MaxSz),CurrentSize(0){vector=newElement[MaxSz];}voidswap(Element&x,Element&y){Elementtemp=x;x=y;y=temp;}private:Element*vector;intMaxSize;CurrentSize;}7.2插入排序(insertSorting)插入排序(思想:V思想:V0,V1,…,Vi-1个对象已排好序,,V-个对象已

8、排好序,现要插入Vi到适当位置现要插入V例子:例子:体育课迟到的人方法:直接插入排序,折半插入排序,方法:直接插入排序,折半插入排序,链表插入排序,排序,希尔排序一,直接插入排序1.思想思想V0V1…Vi-1-Vi向后移动一个对象位置,位置,然后插入2.例子例子i=101234568325916382382358…3.主程序主程序templatevoidInsertionSort(datalist&list){for(inti=1;i子程序templatevoidInsert(datalist

9、pe>&list,inti){Elementtemp=list.vector[i];intj=i;while(j>0&&temp.getkey()javaprogrampublicstaticvoidinsertionSort(Comparable[]a){intj;for(intp=1;p0&&tmp.compareTo(a[j–1])<0;j--)a[j]=a[j–1];a[j]=tmp;}}4.算法分析算法分析1)n个对象已有序个对象已有序比较总次数

10、KCN=n-1=O(n)=-=()比较总次数移动次数RMN=2*(n-1)=O(