大学计算机实践教程：第4章 算法与复杂性.pptx

大学计算机__计算思维导论第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）内排序
冒泡排序
基本思想：一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较，将小的放前，大的放后--递增排序(或者是将大的放前，小的放后--递减排序)。

9
8
5
4
2
08
5
4
2
0
95
4
2
0
8
94
2
0
5
8
92
0
4
5
8
9N个数从小到大冒泡法排序的算法：
1.N个数排序，要进行N-1趟扫描。
2.第i趟扫描时，要做N-i次两两比较
第几趟扫描未排序数个数两两比较的次数
1NN-1
2N-1N-2
………………
iN-(i-1)N-i
3.具体记忆（假定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）内排序
快速排序(只讲思想)
基本思想：划分，从待排序列中任取一个元素(例如取第一个)