软件工程 算法课程 第7章.doc

软件工程软件工程 算法课程算法课程 第第 7 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.两大类:内排序:对内存中的 n 个对象进行排序. 两大类:内排序:对内存中的 个对象进行排序 个对象进行排序. 两大类 外排序:内存放不下, 外排序:内存放不下,还要使用外存的 排序. 排序.4. 排序算法的稳定性: 排序算法的稳定性: 如果待排序的对象序列中, 如果待排序的对象序列中,含有多个关键码值 相等的对象,用某种方法排序后, 相等的对象,用某种方法排序后,这些对象的 相对次序不变的,则是稳定的, 相对次序不变的,则是稳定的,否则为不稳定 的. 81 20 15 82 28 例: 35 81 82 15 20 28 35 稳定的 5. 排序种类: 排序种类: –内排序 内排序 插入排序,交换排序,选择排序,归并排序, 插入排序,交换排序,选择排序,归并排序, 基数排序 –外排序 外排序6. 排序的算法分析: 排序的算法分析: 1)时间开销 比较次数,移动次数 比较次数, )时间开销—比较次数 2)所需的附加空间 ) 下面是静态排序过程中所用到的数据表类定义: 下面是静态排序过程中所用到的数据表类定义: vector 0 1 currentsize-1 maxsize-1 key otherdata … …const int DefaultSize=100; templateclass datalist templateclass Element { private: Type key; field otherdata; public: Type getkey( ){return key;} void setKey(const Type x){key=x;} Element } int operator= =(Type } }template class datalist { public: datalist(int MaxSz=DefaultSize):MaxSize(MaxSz),CurrentSize(0) { vector=new Element[MaxSz];} void swap (Element x=y; y=temp;} private: Element * vector; int MaxSize; CurrentSize; }7.2 插入排序(insert Sorting ) 插入排序(思想:V 思想:V0,V1,…,Vi-1 个对象已排好序, ,V - 个对象已排好序, 现要插入 Vi 到适当位置 现要插入 V 例子: 例子:体育课迟到的人 方法:直接插入排序,折半插入排序, 方法:直接插入排序,折半插入排序,链表插入 排序, 排序,希尔排序 一,直接插入排序 1.思想 思想 V0 V1 …Vi-1 -Vi 向后移动一个对象 位置, 位置,然后插入2.例子 例子 i=10 1 2 3 4 5 68 3 2 5 9 1 6 3 8 2 3 8 2 3 5 8 … 3.主程序 主程序 template void InsertionSort(datalist i子程序 template void Insert(datalist int j=i ; while(j>0 for ( int p = 1; p 0 ivoid BinaryInsert( datalist Elementtemp=list.Vector[i]; while (left void Shellsort( datalist while (gap) { ShellInsert(list, gap); gap=gap= =2? 1 : (int)(gap/2); } } template void ShellInsert( datalist const int gap) { for (int i=gap; itemp=list.Vector[i]; int j=i; while(j>=gap gap > 0; gap /= 2 ) for ( int i = gap; i = gap int exchange=1; while (passvoid BubbleExchange(datalist for (int j=list.CurrentSize-1; j>=i; j--) if (list.Vector[j-1].getkey( )>list.Vector[j].getkey( )) { swap( list.Vector[j-1], list.Vector[j] ); exchange=1; } }verctor 01 i 小2n-1 j 大该算法还可改进:从两头向中间逼近, 该算法还可改进:从两头向中间逼近,可加快速度4.算法分析 算法分析 最小比较次数 有序: 次比较 移动次数为 0 次比较, 有序:n-1 次比较,移动次数为最大比较次数 逆序: 逆序:(n-1)+(n-2)+…+1=n(n-1)/2≈O(n2) ≈ (比较次数 比较次数) 比较次数 3 ∑ i=(3/2)n(n-1)i=1 n-1(移动次数 移动次数) 移动次数 5.稳定性 稳定性 起泡排序是稳定的二,快速排序(分划交换排序) 快速排序(分划交换排序) 1962年 Hoare 提出的. 提出的. 年 提出的 1. 方法: 方法: 1)在 n 个对象中,取一个对象(如第一个对象 个对象中, ) 个对象中 取一个对象(如第一个对象——基 基 ),按该对象的关键码把所有 准 pivot),按该对象的关键码把所有≤ 该关键码 ),按该对象的关键码把所有≤ 的对象分划在它的左边.>该关键码的对象分划 的对象分划在它的左边. 在它的右边. 在它的右边. 2) 对左边和右边(子序列)分别再用快排序. ) 对左边和右边(子序列)分别再用快排序.2. 例子 i 46 [17 [05 05 05 05 05 13 55 13 05 13] 17 13 17 13 17 13 17 13 17 42 42] [42] 42 42 42 42 94 46 46 46 46 46 46 05 [94 [94 [94 [82 [70 55 17 70 82 55 70 82 55 70 82 55 70 82 55 70] 94 55] 82 94 70 82 94 j 100 100] 100] 100] 100] 100 100一次分划: 一次分划:i 46 13 55 42 94 i 17 13 55 42 94 i 17 13 46 42 94 i 17 13 05 42 94 17 13 05 42 46 05 05 j 05 55 j 46 94 55 55 70 70 70 85 85 85 17 j 46 70 70 85 85j 100 100 100 100 1003.算法:用递归方法实现 算法: 算法 template void QuickSort( datalist Elementpivot=list.Vector[low]; while (i != j ) { while(list.Vector[j].getkey( )>pivot.getkey( ) itemplate void SelectExchange( datalist for ( int j=i+1; j二,锦标赛排序(树形选择排序) 锦标赛排序(树形选择排序) 直接选择排序存在重复做比较的情况, 直接选择排序存在重复做比较的情况,锦标赛 排序克服了这一缺点. 排序克服了这一缺点. 思想: 个对象的关键码两两比较得到 个对象的关键码两两比较得到 思想:n 个对象的关键码两两比较得到 n/2 个 比较的优胜者(关键码小者 保留下来,再对 关键码小者)保留下来 比较的优胜者 关键码小者 保留下来 再对 个对象再进行关键码的两两比较, 这 n/2 个对象再进行关键码的两两比较, ……直至选出一个最小的关键码为止. 直至选出一个最小的关键码为止. 直至选出一个最小的关键码为止 如果 n 不是 不是 2 的 次幂 次幂, 如果 不是 的 K 次幂,则让叶结点数补足 到满足 2 ≤ 到满足 kvoid HeapSort(datalisti>=0;i--) FilterDown(i,list.currentsize-1); for(i=list.currentsize-1;i>=1;i--) {Swap(list.Vector[0],list.vector[i]); FilterDown(0,i-1); } } 其中, 就是第 6 章中的 其中,FilterDown()就是第 章中的,但要改一下:那里是 就是第 章中的,但要改一下: 建最小堆,这里是建最大堆. 建最小堆,这里是建最大堆.Heap sortjava program public static void heapsort( Comparable [ ] a ) { for( int i = a.length / 2; i >= 0; i-- ) percDown( a, i, a.length ); for( int i = a.length – 1; i > 0; i-- ) { swapReferences( a, 0, i ); percDown( a, 0, i); } } private static int leftChild( int i ) { return 2 * i + 1; }Heap sortprivate static void percDown( Comparable [ ] a, int i, int n ) { int child; Comparable tmp; for( tmp = a[ i ]; leftChild( i ) void merge(datalist while ( i int len=1; while (len= list.CurrentSize) { for (int i=0 ; i void MergePass( datalist while (i+2*len if (L.first!=NULL) if (L.first->link != NULL) //至少有两个结点 { divide (L, L1); MergeSort(L); MergeSort(L1); L=merge( L, L1); } }下面讨论两个有序链表的 merge 算法 算法 data link L1 5 first L2 15 first last 14 30 32 42 72 86 75 ∧ last 96 99 ∧List List temp ; 1. if ((p= =NULL) or (q= =NULL)) { if (p!=NULL){temp.first=p; temp.last=L1. last;} else{temp.first=q ; temp.last=L2. last;} } else 2. { 1) if (p->datadata) {r = p ; p = p->link;} else{ r = q ; q = q->link ;} 2) temp.first = r ; 。