分治思想以及排序算法_19849.ppt

分治思想以及排序算法 2009/04/28 内容 分治思想 分治排序算法 文件直接存取技术 作业讲评 从索引进行二分检索操作 函数指针 文件直接存取 文件直接存取（Random File Access） fseek(fileName, offset, origin) 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); 排序算法： 为什么要排序？有序表的优点？缺点？ 构造关系。 按照什么原则排序？ 比较？ 如何进行排序？ 基本概念 排序（Sorting）： 简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序） 排序码 与 关键码（primary key） 作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。 排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。 参与排序的对象，称为记录。一个记录可以包含多个字段。 如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。 排序的类型 排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。 在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。 本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。 插入排序 基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。 插入排序的细分类 如何插入到已排好序的序列中？ 直接插入（从后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n) 表插入排序（按链表查找位置后插入） O(n2) 直接插入排序 基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止。 （初始情况下，m = 1） 存储结构与算法优化 顺序存储结构： 二分插入算法，减少比较次数。 链式存储结构： 减少移动次数。 二分法插入排序 特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序 限制：必须采用顺序存储方式。 二分法插入排序算法 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 } // binSort 结论 移动次数与直接插入排序相同，最坏的情况