• 1. 分治思想以及排序算法2009/04/28
  • 2. 内容分治思想 分治排序算法 文件直接存取技术2
  • 3. 作业讲评从索引进行二分检索操作 函数指针3
  • 4. 4
  • 5. 5
  • 6. 文件直接存取6
  • 7. 文件直接存取(Random File Access)fseek(fileName, offset, origin) …file streamFile* fp;7
  • 8. Random File Accessrewind() resets the current position to the start of the file rewind(inFile) fseek() allows the programmer to move to any position in the file fseek(fileName, offset, origin) Origin: SEEK_SET, SEEK_CUR, and SEEK_END ftell() returns the offset value of the next character that will be read or written ftell(inFile);8
  • 9. 9
  • 10. 10
  • 11. 排序算法:为什么要排序?有序表的优点?缺点? 构造关系。 按照什么原则排序? 比较? 如何进行排序?11
  • 12. 基本概念排序(Sorting): 简单地说,排序就是把一组记录按照某个(或某几个)字段的值以递增(由小到大)或递减(由大到小)的次序重新排列的过程。(如按年龄从小到大排序)学号 姓名 年龄 性别 2004001 张佳 18 男 2004002 王鹏 19 男 2004003 刘宁 17 女 2004004 李娟 18 女 2004005 陈涛 19 男 2004006 李小燕 18 女 12
  • 13. 作为比较基础的一个(或多个)字段,称为排序码。排序码可以是数值、符号或符号串。 排序码不一定是关键码,关键码可以作为排序码。关键码是唯一的,但排序码不一定唯一。排序码不唯一时,排序的结果可能不唯一。 参与排序的对象,称为记录。一个记录可以包含多个字段。 如果记录集合中存在多个排序码相同的记录,经过排序后,排序码相同的记录的前后次序保持不变,则这种排序方法称为是稳定的,否则是不稳定的。 排序码 与 关键码(primary key)13
  • 14. 排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。 在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。 本章侧重讨论内排序的方法,但有些方法(特别是归并排序的思想)也可以用于外排序。 排序的类型14
  • 15. 排序算法的评价评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的时间开销是算法好坏的最重要的标志 排序的时间开销衡量标准: 算法执行中的比较次数(必须)。 算法执行中的移动次数(有可能避免)。 通常会关注最坏情况和平均情况的开销。 15
  • 16. 插入排序选择排序:直接选择排序交换排序归并排序直接插入排序二分插入排序起泡排序快速排序表插入排序Shell 排序堆排序排序算法16
  • 17. 插入排序基本思想:每步将一个待排序的记录,按其排序码大小插到前面已经排序的字序列的合适位置,直到全部插入排序完为止。x 顺次选取一个元素插入到合适位置17
  • 18. 插入排序的细分类如何插入到已排好序的序列中? 直接插入(从后向前找位置后插入) O(n2) 二分法插入(按二分法找位置后插入) O(nlog2n) 表插入排序(按链表查找位置后插入) O(n2) 18
  • 19. 直接插入排序基本思想: 假定前面m 个元素已经排序; 取第(m+1) 个元素,插入到前面的适当位置; 一直重复,到m=n 为止。 (初始情况下,m = 1)19
  • 20. 第一趟: {23}, [起始只有一个记录] {11, 23} 11 第二趟: {11,23}, {11,23,55} 55 第三趟: {11,23,55}, {11,23,55,97} 97 第四趟: {11,23,55,97}, {11,19,23,55,97} 19 第五趟: {11,19,23,55,97}, {11,19,23,55,80,97} 80示例:{23,11,55,97,19,80}20
  • 21. 直接插入排序的算法中记录的数据结构typedef int KeyType; typedef int DataType; typedef struct{ KeyType key; /* 排序码字段 */ DataType info; /* 记录的其他字段 */ }RecordNode; typedef struct { int n; /* n为文件中的记录个数,n
  • 22. 直接插入排序算法复杂度评价极端情况下: 最小比较次数∶每个记录仅比较一次 最大比较次数∶每个记录比较已排好序的记录长度 22
  • 23. 直接插入排序算法评价2最小移动次数∶ 最大移动次数∶ 23
  • 24. 直接插入排序算法评价3初始数据状态相关: 文件初态不同时,直接插入排序所耗费的时间有很大差异。 若文件初态为正序,则算法的时间复杂度为O(n) 若初态为反序,则时间复杂度为O(n2)24
  • 25. 直接插入排序算法评价4 —— 平均复杂度插入记录Ri-1,有i种可能的插入位置,即插入到第0,1,…,i-1位置上,假设每种情况发生的概率是相等的,均为 pj = 1/i (j=0,1,…,i-1) 比较次数为Cj=j+1(j=0,…,i-2,i-2),则插入记录Ri-1的平均比较次数为∶ 25
  • 26. 直接插入排序算法评价5 —— 平均复杂度直接插入排序的 总的比较次数为:26
  • 27. 直接插入排序算法评价6 —— 小结直接插入排序算法的平均移动次数与平均比较次数同级,也是O(n2) 直接插入排序的平均时间复杂度为T(n) = O(n2) 算法中引入了一个附加的记录空间temp,因此辅助空间为S(n) = O(1) 直接插入排序是稳定的 27
  • 28. 存储结构与算法优化顺序存储结构: 二分插入算法,减少比较次数。 链式存储结构: 减少移动次数。28
  • 29. 二分法插入排序特点:在直接插入排序的基础上减少比较的次数,即在插入Ri时改用二分法比较找插入位置,便得到二分法插入排序 限制:必须采用顺序存储方式。 29
  • 30. 例:有6个记录,前5 个已排序的基础上,对第6个记录排序。 [ 15 27 36 53 69 ] 42  low mid  high [ 15 27 36 53 69 ] 42 low  high mid [ 15 27 36 53 69 ] 42 high low [ 15 27 36 42 53 69 ] (high36 )( 42<53 )30
  • 31. 二分法插入排序算法void binSort(SortObject * pvector) { int i, j, left, mid, right; RecordNode temp; for( i = 1; i < pvector->n; i++ ) { temp = pvector- >record[i]; left = 0; right = i – 1; while (left <= right) { mid = (left+right)/2; if (temp.key < vector->record[mid].key) right = mid-1; else left = mid+1; }//while for(j=i-1; j>=left; j--) pvector->record[j+1] = pvector->record[j]; if(left != i) pvector->record[left] = temp; }// for } // binSort31
  • 32. 二分插入排序比较次数二分插入排序的比较次数与待排序记录的初始状态无关,仅依赖于记录的个数,插入第i个记录时,如果 ,则无论排序码的大小,都恰好经过 次比较才能确定插入位置,如果, 则比较次数为j+1,因此,将n(n=2k)个记录排序的总比较次数为 32
  • 33. 二分法插入排序方法性能分析当n较大时,比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数 算法的移动次数与直接插入排序算法的相同 最坏的情况为n2/2 最好的情况为n 平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为T(n)= O(n2) 二分插入排序法是稳定的排序算法,在检索时采用left>right结束,left、right的修改原则是:temp.key < pvector->record[mid].key,保证排序是稳定的。33
  • 34. 结论移动次数与直接插入排序相同,最坏的情况为n2/2,最好的情况为n,平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为 T(n)= O(n2) 二分法插入排序是稳定的34
  • 35. 表插入排序表插入排序是在直接插入排序的基础上减少移动的次数。 基本思想: 在记录中设置一个指针字段,记录用链表连接 插入记录Ri时,记录R0至Ri-1已经排序,先将记录Ri脱链 再采用顺序比较的方法找到Ri应插入的位置,将Ri插入链表。 35
  • 36. struct Node; /* 单链表结点类型 */ typedef struct Node ListNode; struct Node { KeyType key; /* 排序码字段 */ DataType info; /* 记录的其它字段 */ ListNode *next; /* 记录的指针字段 */ }; typedef ListNode * LinkList; 表插入算法中记录的数据结构36
  • 37. 表插入排序的算法性能分析 第i趟排序:最多比较次数i次,最少比较次数1次。 n-1趟总的比较次数: 最多: 最少: n-1 记录移动次数:0 时间效率: O(n2) 辅助空间: O(n) [指针] 稳定性: p->key <= now->key保证稳定的排序。37
  • 38. shell排序Shell排序法又称缩小增量法,由D.L.Shell在1959年提出,是对直接插入排序法的改进 思想: 直接插入排序中,当初始序列为逆序时,时间效率最差。若初始序列基本有序时,则大多数记录不需要插入,时间效率大大提高。 另外,当记录数n较小时,n2值受n的值影响不大。 Shell排序正是从这两个方面考虑对直接插入排序进行改进。 38
  • 39. 基本方法先取一个整数d1
  • 40. 示例: {49, 38, 65, 97, 13, 76, 27, 49’}原始序列 49 38 65 97 13 76 27 49’ d=4 └─────-------──-┘ └──--─------────┘ └────--------───┘ └───------─---───┘ d=2 13 38 27 49’ 49 76 65 97 └──----─┴──----─┴──----─┘ └─----──┴──----─┴──----─┘ d=1 13 38 27 49’ 49 76 65 97 └─--┴--─┴--─┴─--┴--─┴--─┴--─┘ 排序结果: 13 27 38 49’ 49 65 76 9740
  • 41. shell排序算法分析Shell排序算法的速度比直接插入排序快,其时间复杂度分析比较复杂,Shell排序的平均比较次数和平均移动次数都为n1.3左右 Shell排序算法中增加了一个辅助空间temp,因此算法的辅助空间为S(n)=O(1) Shell排序是不稳定的。 41
  • 42. di有各种不同的取法: Shell最早提出 d1= , di+1= , D.Knuth教授建议取di+1= 。 一般认为di都取成奇数、di之间互素为好,究竟如何选取di最好?理论上至今仍没有完全解决。 42
  • 43. 选择排序思想:每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置,直到全部排完。 关键问题:在剩余的待排序记录序列中找到最小关键码记录。 方法: 直接选择排序 堆排序。 43
  • 44. 直接选择排序方法是∶ 首先在所有记录中选出排序码最小的记录,与第一个记录交换 然后在其余的记录中再选出排序码最小的记录与第二个记录交换 以此类推,直到所有记录排好序 44
  • 45. 直接选择排序性能分析选择排序的比较次数与记录的初始状态无关。 第i趟排序:从第i个记录开始,顺序比较选择最小关键码记录需要n-i次比较。 总的比较次数: 移动次数: Mmin = 0 (初始为正序时) 最多移动次数:Mmax = 3(n-1) (初始为逆序时,每趟1次交换,3次移动完成) 时间复杂度:T(n)=O(n2), 辅助空间1个记录单位:Temp, 稳定性: 不稳定的排序。 45
  • 46. 时间效率评价建初始堆比较次数C1:O(n) 重新建堆比较次数C2:O(nlog2n) 总比较次数=C1+C2 移动次数小于比较次数 因此, 时间复杂度:O(nlog2n) 空间复杂度:O(1) 适用于n值较大的情况。 算法稳定性:不稳定 46
  • 47. 47交换排序交换排序的基本方法 两两比较待排序记录的排序码,交换不满足顺序要求的偶对,直到全部满足为止 交换排序的分类 起泡排序 快速排序47
  • 48. 48起泡排序方法 先将序列中的第一个记录R0与第二个记录R1比较,若前者大于后者,则两个记录交换位置,否则不交换 然后对新的第二个记录R1与第三个记录R2作同样的处理 依次类推,直到处理完第n-1个记录和第n个记录 从(R0,R1)到(Rn-2,Rn-1)的n-1次比较和交换过程称为一次起泡 经过这次起泡,n个记录中最大者被安置在第n个位置上48
  • 49. 49此后,再对前n-1个记录进行同样处理,使n-1个记录的最大者被安置在整个序列的第n-1个位置上。 然后再对前n-2个记录重复上述过程……,这样最多做n-1次起泡就能完成排序 可以设置一个标志noswap表示本次起泡是否有记录交换,如果没有交换则表示整个排序过程完成 起泡排序是通过相邻记录之间的比较与交换,使值较大的记录逐步从前(上)向后(下)移,值较小的记录逐步从后(下)向前(上)移,就像水底的气泡一样向上冒,故称为起泡排序 起泡排序方法49
  • 50. 50初始序列为49, 38, 65, 97, 76, 13, 27, 49’,请用起泡排序法排序 第一趟起泡∶ 38 49 65 76 13 27 49’ [97] 第二趟起泡∶ 38 49 65 13 27 49’ [76 97] 第三趟起泡∶ 38 49 13 27 49’ [65 76 97]例 题50
  • 51. 51第四趟起泡∶ 38 13 27 49 [49’ 65 76 97] 第五趟起泡∶ 13 27 38 [49 49’ 65 76 97] 第六趟起泡∶ 13 27 [38 49 49’ 65 76 97] 排序结果为∶ 13 27 38 49 49’ 65 76 97 例 题(续)51
  • 52. 若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为n-1,且没有记录移动,时间复杂度是O(n) 若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶ 起泡排序的算法评价52
  • 53. 起泡排序的算法评价(续)起泡排序最好时间复杂度是O(n) 起泡排序最坏时间复杂度为O(n2) 起泡排序平均时间复杂度为O(n2) 起泡排序算法中增加一个辅助空间temp,辅助空间为S(n)=O(1) 起泡排序是稳定的 53
  • 54. 54
  • 55. 分治法int DC(x) { if (x) 够简单 return C(x); else 将 x 分解为 x1 - xn for( i=0; i
  • 56. 归并排序(merge sort)归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。 最简单的情况是(base case),只含一个记录的序列显然是个有序序列,经过"逐趟归并"使整个序列中的有序子序列的长度逐趟增大,直至整个记录序列为有序序列止。 56
  • 57. 分治法的思路(divide and conquer )假设有序列A, 如果能将其平均分为A/2的两个序列A1,A2且分别使得A1,A2排序。 然后就可以通过一个简单的步骤实现A的排序 3,5,7,9 2,6,8,12…9,1257
  • 58. 归并排序(merge sort)归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。 最简单的情况是:只含一个记录的序列显然是个有序序列,经过"逐趟归并"使整个序列中的有序子序列的长度逐趟增大,直至整个记录序列为有序序列止。 58
  • 59. 归并排序(merge sort)88149825625279302331Divide and Conquer 59
  • 60. Merge Sort88149825625279302331Split Set into Two (no real work)25,31,52,88,98Get one friend to sort the first half. 14,23,30,62,79Get one friend to sort the second half. 60
  • 61. Merge SortMerge two sorted lists into one 25,31,52,88,9814,23,30,62,7914,23,25,30,31,52,62,79,88,9861
  • 62. 62
  • 63. 二路归并算法的基本思路:两组归并算法merge: 按low,m,high归并两组记录。结果放于low,high之间。 void merge(RecordNode* r, RecordNode *r1, int low, int m, int high) 一趟归并算法mergePass: 两两归并长度为length的一组记录: void mergePass(RecordNode *r, RecordNode *r1, int n, int length) 63
  • 64. 具有n个记录的文件排序,必须做log2n 趟归并,每趟归并所花费的时间是O(n) 二路归并排序算法的时间复杂度为T(n)=O(nlog2n) 算法中增加了一个数组record,算法的辅助空间为S(n)=O(n) 二路归并排序是稳定的算法评价64
  • 65. 快速排序 (Quick Sort)88149825625279302331Partition set into two using randomly chosen pivot142530233188986279≤ 52 ≤65
  • 66. Quick Sort142530233188986279≤ 52 ≤14,23,25,30,31Get one friend to sort the first half. 62,79,98,88Get one friend to sort the second half. 66
  • 67. Quick Sort14,23,25,30,3162,79,98,8852Glue pieces together. (No real work)14,23,25,30,31,52,62,79,88,9867
  • 68. Quick Sort88149825625279302331Let pivot be the first element in the list?1425302388986279≤ 31 ≤5268
  • 69. Quick Sort≤ 14 ≤14,23,25,30,31,52,62,79,88,9823,25,30,31,52,62,79,88,98If the list is already sorted, then the slit is worst case unbalanced.69
  • 70. 设置变量i指向参加排序的序列中第一个位置0,变量j指向参加排序的序列中最后位置n-1 首先保存记录R0,R[0]为空出的位置,空位在前一区 令j向前扫描,寻找小于R0的记录,找到小于R0的记录R[j],将记录R[j]移到当前空位中,这时空位在后一区 这时令i自i+1起向后扫描,寻找大于R0的记录,找到大于R0的记录R[i],将记录R[i]移到当前空位中,空位又到了前一区, 然后再令j自j-1起向前扫描,此交替改变扫描方向,从两端向中间靠拢,直到i=j,这时i所指的位置为R0的最终位置快速排序基本步骤70
  • 71. 初始序列为49, 38, 65, 97, 76, 13, 27, 49’,例:(1)一次分区过程如下∶ j向左扫描 [49 38 65 97 76 13 27 49’] i↑ j↑ 第一次交换后 [27 38 65 97 76 13 49’] i↑ j↑ i向右扫描 [27 38 65 97 76 13 49’] i↑ j↑71
  • 72. 第二次交换后 [27 38 97 76 13 65 49’] i↑ j↑ j向左扫描,位置不变,第三次交换后 [27 38 13 97 76 65 49’] i↑ j↑ i向右扫描,位置不变,第四次交换后 [27 38 13 76 97 65 49’] i↑ j↑ j向左扫描 [27 38 13 49 76 97 65 49’] i↑j↑例(续):72
  • 73. 13 27 38 49 [49’ 65] 76 [97] 13 27 38 49 49’ [65] 76 [97] 13 27 38 49 49’ 65 76 [97] 最后的排序结果 13 27 38 49 49’ 65 76 97 例(续):73
  • 74. 快速排序算法 初始化 申明temp为记录结点类型l < r?i,j分别赋值为l,r; temp赋为以i为下标的值i!=j?比较、交换找到以i 为下标元素 的排序位置对i值的前面部分继续快速排序endNYYN将找到的位置赋值 (以i为下标的记录)对i值的前面部分继续快速排序对整个文件排序,只需调用quickSort (pvector, 0,n-1)即可l,r为待比较记录序列的头位置和尾位置74
  • 75. 快速排序算法75
  • 76. 当待排序记录已经排序时,算法的执行时间最长 第一趟经过n-1次比较,将第一个记录定位在原来的位置上,并得到一个包括n-1个记录的子文件 第二趟经过n-2次比较,将第二个记录定位在原来的位置上,并得到一个包括n-2个记录的子文件;… 这样最坏情况总比较次数为快速排序算法评价76
  • 77. 77最好情况下,每次划分使两个子区的长度大致相等 C(n) ≤n+2C(n/2) ≤n+2[n/2+2C(n/22)]=2n+4c(n/22) ≤… ≤kn+2kC(n/2k)= nlog2n+nC(1)= O(nlog2n) 快速排序的平均时间复杂度是T(n)=O(nlog2n) 快速排序是不稳定的 快速排序算法评价(续)77
  • 78. 作业上机布置78