大学计算机__计算思维导论第4章算法与复杂性第4章算法与复杂性排序(Sort)：对一组对象按照“关键字”递增(或递减)的排列的过程。“关键字”：是指对象的一个用于排序的特性。例如：对一组“人”进行排序：可按“年龄”/“身高”进行排序，“人”即为对象，而“年龄”、“身高”等则为“关键字”。在计算科学中,排序对象是多种多样的。排序--许多复杂问题求解的基础，如数据库查询、数据挖掘、搜索引擎等大规模数据处理算法实现的基础。通过排序可有效降低问题求解算法的执行时间。1）结构化数据表的查找与统计需要排序下图为学生成绩表，以“记录”为元素，将大量数据组织成一张表。在数据表中，类似如下的查找或统计是使用频率非常高的操作：(1)“查找80分以上的同学?”(2)“查找姓名为江海的同学及其相关信息?”(3)“查找学号为120300106同学的相关信息?”1）结构化数据表的查找与统计需要排序怎样完成查找和统计呢？未排序的数据查寻，需要检索整个数据表才能正确回答上面的问题。需要访问n条记录。已按“关键字”排序的数据进行查询，则仅需访问一半甚至更少的记录便可得到正确的结果。当数据表的记录数非常庞大时，显而易见，数据排序则是节省时间提高查找效率的有效手段。1）结构化数据表的查找与统计需要排序怎样对结构化的数据进行排序呢？内排序问题:待排序的数据可一次性地装入内存中，即可以完整地看到和操纵所有数据，使用数组或其他数据结构便可进行统一的排序处理的排序问题；外排序问题:待排序的数据保存在磁盘上，不能一次性装入内存，即不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；1）结构化数据表的查找与统计需要排序怎样实现内排序和外排序呢？问题：某教师要对学生按身高排序。教师只能在容纳100人房间(相当于内存)中对学生进行排序。对于小于100人的学生排序问题属于内排序问题。对于大于100人的学生排序问题，学生并不能都进入房间，而只能在操场(相当于磁盘)等候，轮流进入房间，这样的排序便属于外排序问题。2）非结构化数据(文档)的查找与搜索也需要排序针对图书馆/网上大量的文献/文档如何快速地查找一份文档？如何确定一份文档是否包含给定的一个或多个“关键词”？哪些词汇是一份文档的关键词？当用户输入一个关键词查询的时候，是否要扫描这几十几百几千万册文档呢？这些问题的解决需要倒排索引文件的技术2）非结构化数据(文档)的查找与搜索也需要排序倒排索引文件的技术对一份文档，去掉标点符号和一些辅助词汇，将所有出现的单词无重复地按照出现的频次由多到少排列出来。将频次排序在前面的若干个词汇，或者频次超过一定阈[yù]值的若干个词汇作为本文档的关键词。对于所有的文档，建立一个“索引表”(类似于一般纸质图书后面都有的索引表)，通常称为倒排索引文件4.1.1排序问题(a)Google的搜索结果排序示意1）内排序插入排序基本思想：类似于打扑克牌时，一边抓牌，一边理牌的过程，每抓一张牌就把它插入到适当的位置，牌抓完了，也理完了---这种策略被称为插入排序。1）内排序--插入排序（后插算法）1）内排序--插入排序（后插算法）1）内排序选择排序基本思想：一个轮次一个轮次的处理。首先在所有数组元素中找出最小值的元素，放在A[1]中；接着在不包含A[1]的余下的数组元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一个元素。这一排序策略被称为选择排序。1）内排序--选择排序n个数从小到大选择法排序的算法1.n个数选择排序，要做n-1次选择；2.每一次选择都是在尚未排好序的数中找最小数，交换到尚未排好序数的第一个位置上。1）内排序--选择排序1）内排序冒泡排序基本思想：一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较，将小的放前，大的放后--递增排序(或者是将大的放前，小的放后--递减排序)。985420854209542089420589204589N个数从小到大冒泡法排序的算法：1.N个数排序，要进行N-1趟扫描。2.第i趟扫描时，要做N-i次两两比较第几趟扫描未排序数个数两两比较的次数1NN-12N-1N-2………………iN-(i-1)N-i3.具体记忆（假定N个数）for(i=1;i<=N-1;i++)for(j=1;j<=N-i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}4.1.2基本排序算法1）内排序三种基本排序算法的比较1）内排序快速排序(只讲思想)基本思想：划分，从待排序列中任取一个元素(例如取第一个)