分治思想以及排序算法,2009/04/28,,,,,2,内容,分治思想 分治排序算法 文件直接存取技术,3,作业讲评,从索引进行二分检索操作 函数指针,4,,,,,,5,,,,,6,文件直接存取,,7,文件直接存取（Random File Access）,fseek(fileName, offset, origin),,,,,,,,,,,,,,file stream,,File* fp;,8,Random File Access,rewind() 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);,,9,,,10,,,,11,排序算法：,为什么要排序？有序表的优点？缺点？ 构造关系。
按照什么原则排序？ 比较？ 如何进行排序？,12,基本概念,排序（Sorting）： 简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程如按年龄从小到大排序）,13,作为比较基础的一个(或多个)字段，称为排序码排序码可以是数值、符号或符号串 排序码不一定是关键码，关键码可以作为排序码关键码是唯一的，但排序码不一定唯一排序码不唯一时，排序的结果可能不唯一 参与排序的对象，称为记录一个记录可以包含多个字段 如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的排序码 与 关键码（primary key）,14,排序方法可以分为五种插入排序、选择排序、交换排序、分配排序和归并排序 在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序 本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序排序的类型,15,排序算法的评价,评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的时间开销是算法好坏的最重要的标志 排序的时间开销衡量标准: 算法执行中的比较次数（必须）。
算法执行中的移动次数（有可能避免） 通常会关注最坏情况和平均情况的开销16,,插入排序,选择排序：直接选择排序,交换排序,归并排序,直接插入排序,二分插入排序,起泡排序,快速排序,,,,表插入排序,Shell 排序,,堆排序,排序算法,17,插入排序,基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止x,,,顺次选取一个元素,插入到合适位置,18,插入排序的细分类,如何插入到已排好序的序列中？ 直接插入（从后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n) 表插入排序（按链表查找位置后插入） O(n2),19,直接插入排序,基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止 （初始情况下，m = 1）,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,21,直接插入排序的算法中记录的数据结构,typedef int KeyType; typedef int DataType; typedef struct KeyType key; /* 排序码字段 */ DataType info; /* 记录的其他字段 */ RecordNode; typedef struct int n; /* n为文件中的记录个数，n
若文件初态为正序，则算法的时间复杂度为O(n) 若初态为反序，则时间复杂度为O(n2),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的平均比较次数为,,26,直接插入排序算法评价5 平均复杂度,直接插入排序的 总的比较次数为：,27,直接插入排序算法评价6 小结,直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2) 直接插入排序的平均时间复杂度为T(n) = O(n2) 算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1) 直接插入排序是稳定的,28,存储结构与算法优化,顺序存储结构： 二分插入算法，减少比较次数 链式存储结构： 减少移动次数29,二分法插入排序,特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序 限制：必须采用顺序存储方式30,(high
但大于直接插入排序的最小比较次数 算法的移动次数与直接插入排序算法的相同 最坏的情况为n2/2 最好的情况为n 平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为T(n)= O(n2) 二分插入排序法是稳定的排序算法,在检索时采用leftright结束，left、right的修改原则是：temp.key recordmid.key，保证排序是稳定的34,结论,移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为 T(n)= O(n2) 二分法插入排序是稳定的,35,表插入排序,表插入排序是在直接插入排序的基础上减少移动的次数 基本思想: 在记录中设置一个指针字段，记录用链表连接 插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链 再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表36,struct Node;/* 单链表结点类型 */ typedef struct Node ListNode; struct Node KeyType key;/* 排序码字段 */ DataType info;/* 记录的其它字段 */ ListNode *next;/* 记录的指针字段 */ ; typedef ListNode * LinkList;,表插入算法中记录的数据结构,37,表插入排序的算法性能分析,第i趟排序：最多比较次数i次，最少比较次数1次。
n-1趟总的比较次数： 最多： 最少： n-1 记录移动次数：0 时间效率： O(n2) 辅助空间： O(n) 指针 稳定性： p-key key保证稳定的排序38,shell排序,Shell排序法又称缩小增量法，由D.L.Shell在1959年提出，是对直接插入排序法的改进 思想: 直接插入排序中，当初始序列为逆序时，时间效率最差若初始序列基本有序时，则大多数记录不需要插入，时间效率大大提高 另外，当记录数n较小时，n2值受n的值影响不大 Shell排序正是从这两个方面考虑对直接插入排序进行改进39,基本方法,先取一个整数d1
42,di有各种不同的取法：,Shell最早提出 d1= ， di+1= ， D.Knuth教授建议取di+1= 一般认为di都取成奇数、di之间互素为好，究竟如何选取di最好?理论上至今仍没有完全解决43,选择排序,思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完 关键问题：在剩余的待排序记录序列中找到最小关键码记录 方法： 直接选择排序 堆排序44,直接选择排序,方法是 首先在所有记录中选出排序码最小的记录，与第一个记录交换 然后在其余的记录中再选出排序码最小的记录与第二个记录交换 以此类推，直到所有记录排好序,45,直接选择排序性能分析,选择排序的比较次数与记录的初始状态无关 第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较 总的比较次数： 移动次数： Mmin = 0 (初始为正序时） 最多移动次数：Mmax = 3(n-1) (初始为逆序时，每趟1次交换，3次移动完成） 时间复杂度：T(n)=O(n2)， 辅助空间1个记录单位：Temp， 稳定性： 不稳定的排序46,时间效率评价,建初始堆比较次数C1：O(n) 重新建堆比较次数C2：O(nlog2n) 总比较次数=C1+C2 移动次数小于比较次数 因此， 时间复杂度：O（nlog2n） 空间复杂度：O（1） 适用于n值较大的情况。
算法稳定性：不稳定,47,47,交换排序,交换排序的基本方法 两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足为止 交换排序的分类 起泡排序 快速排序,48,48,起泡排序,方法 先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换 然后对新的第二个记录R1与第三个记录R2作同样的处理 依次类推，直到处理完第n-1个记录和第n个记录 从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡 经过这次起泡，n个记录中最大者被安置在第n个位置上,49,49,此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上 然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序 可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成 起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序,起泡排序方法,50,50,初始序列为49, 38, 65, 97, 76, 13, 27, 49，请用起泡排序法排序 第一趟起泡 38 49657613274997 第二趟起泡 38 4965 1327497697 第三趟起泡 38 4913274965 7697,例 题,51,51,第四趟起泡 38 13274949657697 第五趟起泡 13 27384949657697 第六趟起泡 13 27384949657697 排序结果为 13 27 38 4949657697,例 题(续),52,若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n) 若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值,起泡排序的算法评价,53,起泡排序的算法评价(续),起泡排序最好时间复杂度是O(n) 起泡排序最坏时间复杂度为O(n2) 起泡排序平均时间复杂度为O(n2) 起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1) 起泡排序是稳定的,54,,,55,分治法,int DC(x) if (x) 够简单 return C(x); else 将 x 分解为 x1 - xn for( i=0; i
最简单的情况是(base case)，只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止57,分治法的思路（divide and conquer ）,假设有序列A, 如果能将其平均分为A/2的两个序列A1,A2且分别使得A1,A2排序 然后就可以通过一个简单的步骤实现A的排序 3，5，7，9 2，6，8，12,58,归并排序（merge sort）,归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列 最简单的情况是:只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止59,归并排序（merge sort）,Divide and Conquer,60,Merge Sort,Split Set into Two,61,Merge Sort,Merge two sorted lists into one,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),64,具有n个记录的文件排序，必须做log2n 趟归并，每趟归并所花费的时间是O(n) 二路归并排序算法的时间复杂度为T(n)=O(nlog2n) 算法中增加了一个数组record，算法的辅助空间为S(n)=O(n) 二路归并排序是稳定的,算法评价,65,快速排序 (Quick Sort),Partition set into two using randomly chosen pivot,,66,Quick Sort,67,Quick Sort,,68,Quick Sort,Let pivot be the first element in the list?,,14,25,30,23,,88,98,62,79, 31 ,,52,69,Quick Sort,, 14 ,,If the list is already sorted, then the slit is worst case unbalanced.,70,设置变量i指向参加排序的序列中第一个位置0，变量j指向参加排序的序列中最后位置n-1 首先保存记录R0，R0为空出的位置，空位在前一区 令j向前扫描，寻找小于R0的记录，找到小于R0的记录Rj，将记录Rj移到当前空位中，这时空位在后一区 这时令i自i+1起向后扫描，寻找大于R0的记录，找到大于R0的记录Ri，将记录Ri移到当前空位中，空位又到了前一区， 然后再令j自j-1起向前扫描，此交替改变扫描方向，从两端向中间靠拢，直到i=j，这时i所指的位置为R0的最终位置,快速排序基本步骤,71,初始序列为49, 38, 65, 97, 76, 13, 27, 49，,例:,(1)一次分区过程如下 j向左扫描 49 38 65 97 76 1327 49 ij 第一次交换后 27 38 65 97 76 13 49 ij i向右扫描 27 3865977613 49 ij,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 ij,例（续）:,73,13 27 38 49 49 65 76 97 1327 38 4949 65 76 97 1327 38 4949 65 76 97 最后的排序结果 1327 38 4949 65 76 97,例（续）:,74,,快速排序算法,初始化 申明temp为记录结点类型,l < r？,i,j分别赋值为l,r; temp赋为以i为下标的值,i!=j?,,,,比较、交换找到以i 为下标元素 的排序位置,,,,,对i值的前面部分继续快速排序,,,,,end,,N,Y,Y,N,,,将找到的位置赋值 (以i为下标的记录),对i值的前面部分继续快速排序,,对整个文件排序，只需调用quickSort (pvector, 0,n-1)即可,l,r为待比较记录序列的头位置和尾位置,,75,快速排序算法,76,当待排序记录已经排序时，算法的执行时间最长 第一趟经过n-1次比较，将第一个记录定位在原来的位置上，并得到一个包括n-1个记录的子文件 第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件； 这样最坏情况总比较次数为,快速排序算法评价,77,77,最好情况下，每次划分使两个子区的长度大致相等 C(n) n+2C(n/2) n+2n/2+2C(n/22)=2n+4c(n/22) kn+2kC(n/2k)= nlog2n+nC(1)= O(nlog2n) 快速排序的平均时间复杂度是T(n)=O(nlog2n) 快速排序是不稳定的,快速排序算法评价(续),78,作业,上机布置,。