王桂平信息学院信息技术教研室《数据结构与算法》第7章内排序2信息学院信息技术教研室内排序知识点7.1排序问题的基本概念排序问题的基本概念7.1.1补充：用系统函数实现排序补充：用系统函数实现排序7.2三种三种O(nO(n22))的简单排序算法的简单排序算法7.2.1插入排序法插入排序法7.2.2冒泡排序法冒泡排序法7.2.3直接选择排序法直接选择排序法7.2.4简单排序算法的时间代价对比简单排序算法的时间代价对比7.3ShellShell排序排序7.4基于分治法的排序基于分治法的排序7.4.1快速排序快速排序7.4.2归并排序归并排序3信息学院信息技术教研室排序无处不在在计算机应用软件计算机应用软件中经常需要对所管理的各种数据进行处数据进行处理理，排序排序往往是这些数据处理中需要用到的核心运算核心运算。排序例子排序例子11：资源管理器资源管理器。一级排序4信息学院信息技术教研室排序例子排序例子22：ExcelExcel提供的排序功能提供的排序功能，最多可以选择3个关键字关键字(也就是最多可以进行三级排序最多可以进行三级排序)，每个关键字都可以选择是增序还是减序。二级排序5信息学院信息技术教研室排序例子排序例子33：回收站的排序功能回收站的排序功能，可以对已删除的文件按删除日期删除日期、修改时间等属性进行排序，当需要还还原文件时原文件时，按删除日期排序按删除日期排序将给用户提供重要的参考。6信息学院信息技术教研室日常生活中的排序例子以上例子是排序在计算机常用软件中的经典应用。日常生活中的排序例子日常生活中的排序例子：对收到的试卷按学号排序试卷按学号排序。图书管理员将书籍按编号排序书籍按编号排序放置在书架上。医院门诊医生按病人到达的先后顺序将他们挂的号排按病人到达的先后顺序将他们挂的号排序序。手机里收到的短信短信通常是按收到的时间先后排序按收到的时间先后排序。教务处排课，按专业课、专业基础课、基础课程这种课程重要程序从高到低先后排课课程重要程序从高到低先后排课；或者按全校选修课、全院选修、必修课按选修面从宽到窄先后排课按选修面从宽到窄先后排课。……7信息学院信息技术教研室内排序和外排序内排序内排序：如果待排序的记录记录个数较少，整个排序过程中所整个排序过程中所有的记录都可以直接存放在内存中有的记录都可以直接存放在内存中，这样的排序叫做内排序(internalsorting)。外排序外排序：如果待排序的记录数量太大，内存无法容纳所有的记录，因此排序过程中还需要访问外存排序过程中还需要访问外存，这样的排序叫做外排序(externalsorting)。本章讨论内排序，本课程不讨论外排序不讨论外排序(外排序可通过其他教材或课程自学)。8信息学院信息技术教研室7.1排序问题的基本概念由于讨论的是内排序，在大部分情况下本章都是考虑基于考虑基于顺序存储的排序顺序存储的排序，即待排序的数据是存储在数组待排序的数据是存储在数组中。记录记录(record)：参与排序的元素称为记录参与排序的元素称为记录，记录是进行排序的基本单位。序列序列(sequence)：所有待排序记录的集合所有待排序记录的集合称为序列序列。所谓排序就是将序列中的记录按照特定的顺序排列起来。排序码排序码(sortkey)：每个记录中可能有多个域域(相当于结构体或类变量中的成员)，排序码是记录中的一个排序码是记录中的一个((或多个或多个))域，该域，该域的值作为排序运算中的依据域的值作为排序运算中的依据。排序域的类型可以是整数，也可以是字符串，甚至可以是组合类型甚至可以是组合类型。例如，右图中，排序码是{{游戏类别游戏类别,,编号编号}}，它包含了2个域。9信息学院信息技术教研室关键码关键码(key)(key)：唯一确定记录的一个或多个域唯一确定记录的一个或多个域。例如在学生记录中，学号是关键码，姓名不是学号是关键码，姓名不是。排序码不一定是关键码排序码不一定是关键码。例如可以按学号对学生记录进行排序，也可以按姓名对学生记录进行排序。如果排序码不是关键码，这时就可能有多个记录具有同一如果排序码不是关键码，这时就可能有多个记录具有同一个排序码个排序码，因而排序的结果...
