战德臣《大学计算机-计算思维导论》大学计算机第8讲-怎样研究算法-排序算法研究示例

为什么要研究排序算法--结构化数据表查找问题ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授为什么要研究排序算法--结构化数据表查找问题(1)什么是排序问题?排序问题对一组对象按照某种规则进行有序排列。通常是把一组对象整理成按关键字递增(或递减)的排列，关键字是指对象的一个用于排序的特性。例如：对一组“人”，按“年龄”或“身高”排序；对一组“商品”，按“价格”排序；对一组“网页”，按“重要度”排序；对一组“词汇”，按“首字母”字典序排序。……战德臣教授为什么要研究排序算法--结构化数据表查找问题(2)为什么要研究排序问题?结构化数据表的查找问题【算法A：未排序数据查找算法】StartofalgorithmStep1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step2。Step2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。Endofalgorithm学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73查找成绩为80分的所有同学?算法效率：读取并处理所有记录，即n条记录数据表记录数:n未排序战德臣教授为什么要研究排序算法--结构化数据表查找问题(2)为什么要研究排序问题?结构化数据表的查找与统计需要排序【算法B：已排序数据查找算法】StartofalgorithmStep1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step2和Step3步。Step2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。Endofalgorithm学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44查找成绩为80分的所有同学?算法效率：读取并处理部分记录，即=n条记录数据表记录数:n已排序战德臣教授为什么要研究排序算法--结构化数据表查找问题(2)为什么要研究排序问题?结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44查找成绩为80分的所有同学?数据表记录数:n【算法C：已排序数据查找算法】StartofalgorithmStep1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step2.计算中间记录位置I=(Start+Finish)/2，读取第I条记录。Step3.判断第I条记录成绩是否大于给定查找分数：(1)如果是小于，调整Finish=I-1,如果StartFinish则结束，否则继续做Step2；(2)如果是大于，调整Start=I+1，如果StartFinish则结束，否则继续做Step2；(3)如果是等于，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。Endofalgorithm•算法效率：除极端情况外读取并处理=n/2条记录已排序战德臣教授为什么要研究排序算法--结构化数据表查找问题(2)为什么要研究排序问题?结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73•统计各个分数段的人数•统计每个同学的平均分数•统计每门课的平均分数???•算法效率：需要读取并处理???条记录才能完成呢？战德臣教授为什么要研究排序算法--结构化数据表查找问题(3)小结?结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73•统计各个分数段的人数•统计每个同学的平均分数•统计每门课的平均分数???•算法效率：需要读取并处理???条记录才能完成呢？排序算法是计算学科中很重要的算法排序算法是很多复杂算法的基础当对数据集合需要多遍处理时，先排序-好为什么要研究排序算法--非结构化的数据文档查找问题ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授为什么要研究排序算法---非结构化的数据文档查找问题(1)非结构化数据(文档)的查找问题?怎样按照关键词找到相应的文档呢?关键词查询包含关键词的文档是哪一个?有多少个?怎样找?怎样快速地找?战德臣教授为什么要研究排序算法--非结构化的数据文档查找问题(2)索引与倒排索引--需要排序?怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表---倒排索引正排：一个文档包含了哪些词汇?#Doc1,{Word1,Word2,…}倒排：一个词汇包含在哪些文档中Word1,{#Doc1,#Doc2,…}怎样建立索引?怎样利用索引快速地找?排序or不排序?战德臣教授为什么要研究排序算法--非结构化的数据文档查找问题(3)关键词的提取--需要排序?关键词索引表---倒排索引文档能否自动找出文档中的关键词?哪些是关键词?排序or不排序?战德臣教授为什么要研究排序算法--非结构化的数据文档查找问题(4)小结?非结构化数据(文档)的查找与搜索也需要排序怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表---倒排索引文档怎样快速找到关键词呢?哪些是关键词呢?战德臣教授为什么要研究排序算法--非结构化的数据文档查找问题(4)小结?非结构化数据(文档)的查找与搜索也需要排序怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表---倒排索引文档怎样快速找到关键词呢?哪些是关键词呢?排序：字母序排序：数值序查找：反复进行不同类别的查找，不同类别的排序基本排序算法I--内排序之插入法排序ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授基本排序算法I--内排序之插入法排序(1)插入排序的思想?插入法排序类似于打扑克牌时，一边抓牌，一边理牌的过程：每抓一张牌就把它插入到适当的位置；牌抓完了，也理完了。---这种策略被称为插入排序战德臣教授基本排序算法I--内排序之插入法排序(2)插入排序的过程模拟?插入法排序1274978193366505180i=2i=3i=4i=512345678910Ai=57124978193366505180A7124978193366505180A7124978193366505180A7121949783366505180A7121933495051667880Ai=9…i=57124978783366505180Ai=57124949783366505180A插入排序:递增排序示意.其中三角形左侧为已排好序的元素,其右侧为未排序的元素,实心三角形本身为待插入的元素.图中示意了为待排序元素19腾挪空间的过程,由箭头示意.空心三角形表示新插入的元素战德臣教授INSERTION-SORT(A)1.fori=2toN2.{key=A[i];3.j=i-1;4.While(j0andA[j]key)do5.{A[j+1]=A[j];6.j=j-1;}7.A[j+1]=key;8.}基本排序算法I--内排序之插入法排序(3)插入排序的算法表达?插入法排序O(N2)基本排序算法II--内排序之简单选择法排序ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授简单选择法排序首先在所有数组元素中找出最小值的元素，放在A[1]中；接着在不包含A[1]的余下的数组元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一个元素。这一排序策略被称为简单选择排序。基本排序算法II--内排序之简单选择法排序(1)简单选择排序的思想?战德臣教授简单选择法排序1274978193366505180i=1i=3i=412345678910A7124978193366505180A7121978493366505180A7121933495051667880Ai=9…i=47121978493366505180Ai=47121933497866505180A(b)选择排序:递增排序示意.其中三角形代表本轮要找的最小元素应在的位置,方形代表本轮次至今为止所找到的最小元素所在位置,三角形左侧为已排好序的元素,三角形右侧的每一元素依次和方形位置元素比较.实线双向箭头代表两个元素交换.虚线双向箭头代表两个元素需要比较基本排序算法II--内排序之简单选择法排序(2)简单选择排序的过程模拟?战德臣教授SELECTION-SORT(A)1.fori=1toN-12.{k=i;3．forj=i+1toN4.{ifA[j]A[k]thenk=j;}5.ifkithen6.{7.temp=A[k];8.A[k]=A[i];9.A[i]=temp;10.}11.}O(N2)简单选择法排序基本排序算法II--内排序之简单选择法排序(3)简单选择排序的算法表达?基本排序算法III--内排序之冒泡法排序ResearchCenteronIntelligentComputingforEnter