索引技术简介分治思想以及排序算法

索引技术简介、分治思想以及排序算法2010/05/131内容作业讲解分治思想分治排序算法倒排索引技术中文信息处理与数据分析2345能否实现冒泡排序？6科学网广度优先有回路中文内容2000网页词频统计结果高频词低频词7Google+百度私家爬虫网上智能代理爬虫，还是爬虫…8中文信息处理分词词典分词新词发现统计分词序列标注语义标识与信息提取9排序算法：为什么要排序？有序表的优点？缺点？构造关系。按照什么原则排序？比较？如何进行排序？10基本概念排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕18女11作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。排序码与关键码（primarykey）12排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。

本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序的类型13排序算法的评价评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。14插入排序选择排序：直接选择排序交换排序归并排序直接插入排序二分插入排序起泡排序快速排序表插入排序Shell排序堆排序排序算法15插入排序基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x

顺次选取一个元素插入到合适位置16插入排序的细分类如何插入到已排好序的序列中？直接插入（从后向前找位置后插入）

O(n2)

二分法插入（按二分法找位置后插入）

O(nlog2n)

表插入排序（按链表查找位置后插入）

O(n2)17直接插入排序基本思想：假定前面m个元素已经排序；取第(m+1)个元素，插入到前面的适当位置；一直重复，到m=n为止。（初始情况下，m=1）18

第一趟：{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}19直接插入排序的算法中记录的数据结构typedef

int

KeyType;typedef

int

DataType;typedef

struct{

KeyTypekey; /*排序码字段*/

DataTypeinfo;/*记录的其他字段*/}RecordNode;typedef

struct{

intn;/*n为文件中的记录个数，n<MAXNUM*/

RecordNode*record;}SortObject;20直接插入排序算法复杂度评价极端情况下：最小比较次数∶每个记录仅比较一次最大比较次数∶每个记录比较已排好序的记录长度21直接插入排序算法评价2最小移动次数∶最大移动次数∶22直接插入排序算法评价3初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序，则时间复杂度为O(n2)23直接插入排序算法评价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的平均比较次数为∶24直接插入排序算法评价5——平均复杂度直接插入排序的总的比较次数为：25直接插入排序算法评价6——小结直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n)=O(n2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)直接插入排序是稳定的26存储结构与算法优化顺序存储结构：二分插入算法，减少比较次数。链式存储结构：减少移动次数。27二分法插入排序特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序限制：必须采用顺序存储方式。28算法分析移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为

T(n)=O(n2)二分法插入排序是稳定的29表插入排序表插入排序是在直接插入排序的基础上减少移动的次数。基本思想:在记录中设置一个指针字段，记录用链表连接插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。30structNode; /*单链表结点类型*/typedef

structNodeListNode;structNode{KeyTypekey; /*排序码字段*/

DataTypeinfo; /*记录的其它字段*/

ListNode*next; /*记录的指针字段*/};typedef

ListNode*LinkList;表插入算法中记录的数据结构31表插入排序的算法性能分析

第i趟排序：最多比较次数i次，最少比较次数1次。

n-1趟总的比较次数：最多：最少：n-1

记录移动次数：0

时间效率：O(n2)

辅助空间：O(n)[指针]

稳定性：p->key<=now->key保证稳定的排序。32选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。关键问题：在剩余的待排序记录序列中找到最小关键码记录。方法：直接选择排序堆排序。33直接选择排序方法是∶首先在所有记录中选出排序码最小的记录，与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推，直到所有记录排好序34直接选择排序性能分析选择排序的比较次数与记录的初始状态无关。第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。总的比较次数：移动次数：Mmin=0(初始为正序时）最多移动次数：Mmax=3(n-1)(初始为逆序时，每趟1次交换，3次移动完成）

时间复杂度：T(n)=O(n2)，辅助空间1个记录单位：Temp，稳定性：不稳定的排序。

35时间效率评价建初始堆比较次数C1：O(n)重新建堆比较次数C2：O(nlog2n)总比较次数=C1+C2移动次数小于比较次数因此，时间复杂度：O（nlog2n）空间复杂度：O（1）适用于n值较大的情况。算法稳定性：不稳定3637交换排序交换排序的基本方法两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足为止交换排序的分类起泡排序快速排序3738起泡排序方法先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换然后对新的第二个记录R1与第三个记录R2作同样的处理依次类推，直到处理完第n-1个记录和第n个记录从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡经过这次起泡，n个记录中最大者被安置在第n个位置上3839此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程……，这样最多做n-1次起泡就能完成排序可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序起泡排序方法39若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶起泡排序的算法评价40起泡排序的算法评价(续)起泡排序最好时间复杂度是O(n)起泡排序最坏时间复杂度为O(n2)起泡排序平均时间复杂度为O(n2)起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)起泡排序是稳定的41分治法int

DC(x){if(x)够简单

returnC(x);else

将x分解为x1-xn for(i=0;i<n;++i)DC(xi);

重组DC(xi)得到C(x);}42QuickSort142530233188986279≤

52≤14,23,25,30,31Getonefriendto

sortthefirsthalf.62,79,98,88Getonefriendto

sortthesecondhalf.43QuickSort14,23,25,30,3162,79,98,8852Gluepiecestogether.(Norealwork)14,23,25,30,31,52,62,79,88,9844QuickSort88149825625279302331Letpivotbethefirst

elementinthelist?1425302388986279≤

31≤5245QuickSort≤

14≤14,23,25,30,31,52,62,79,88,9823,25,30,31,52,62,79,88,98Ifthelistisalreadysorted,

thentheslitisworstcaseunbalanced.46设置变量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的最终位置快速排序基本步骤47初始序列为49,38,65,97,76,13,27,49’，例:(1)一次分区过程如下∶j向左扫描[493865977613 27 49’]i↑ j↑第一次交换后[273865977613

49’] i↑ j↑i向右扫描 [2738 65 97 76 13

49’] i↑ j↑48第二次交换后[2738

977613 65 49’] i↑ j↑j向左扫描，位置不变，第三次交换后 [2738139776

6549’] i↑ j↑i向右扫描，位置不变，第四次交换后 [273813

76976549’] i↑j↑j向左扫描[2738134976976549’]

i↑j↑例（续）:4913273849[49’65]76[97] 13 273849 49’[65]76[97] 13 273849 49’6576[97]

最后的排序结果

13 273849 49’657697例（续）:50快速排序算法

初始化申明temp为记录结点类型l<r？i,j分别赋值为l,r;temp赋为以i为下标的值i!=j?比较、交换找到以i为下标元素的排序位