内排序(精简版)

《内排序(精简版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章内排序内排序知识点7.1排序问题的基本概念7.1.1补充：用系统函数实现排序7.2三种O(n2)的简单排序算法7.2.1插入排序法7.2.2冒泡排序法7.2.3直接选择排序法7.2.4简单排序算法的时间代价对比7.3Shell排序7.4基于分治法的排序7.4.1快速排序7.4.2归并排序排序无处不在在计算机应用软件中经常需要对所管理的各种数据进行处理，排序往往是这些数据处理中需要用到的核心运算。排序例子1：资源管理器。一级排序排序例子2：Excel提供的排序功能，最多可以选择3个关键字(也就是最多可以进行三级排序)，每个关键字都可以选择是增序还是减序

2、。二级排序排序例子3：回收站的排序功能，可以对已删除的文件按删除日期、修改时间等属性进行排序，当需要还原文件时，按删除日期排序将给用户提供重要的参考。日常生活中的排序例子以上例子是排序在计算机常用软件中的经典应用。日常生活中的排序例子：对收到的试卷按学号排序。图书管理员将书籍按编号排序放置在书架上。医院门诊医生按病人到达的先后顺序将他们挂的号排序。手机里收到的短信通常是按收到的时间先后排序。教务处排课，按专业课、专业基础课、基础课程这种课程重要程序从高到低先后排课；或者按全校选修课、全院选修、必修课按选修面从宽到窄先后排课。……内排序和外排序内排序：如果待

3、排序的记录个数较少，整个排序过程中所有的记录都可以直接存放在内存中，这样的排序叫做内排序(internalsorting)。外排序：如果待排序的记录数量太大，内存无法容纳所有的记录，因此排序过程中还需要访问外存，这样的排序叫做外排序(externalsorting)。本章讨论内排序，本课程不讨论外排序(外排序可通过其他教材或课程自学)。7.1排序问题的基本概念由于讨论的是内排序，在大部分情况下本章都是考虑基于顺序存储的排序，即待排序的数据是存储在数组中。记录(record)：参与排序的元素称为记录，记录是进行排序的基本单位。序列(sequence)：所有待

4、排序记录的集合称为序列。所谓排序就是将序列中的记录按照特定的顺序排列起来。排序码(sortkey)：每个记录中可能有多个域(相当于结构体或类变量中的成员)，排序码是记录中的一个(或多个)域，该域的值作为排序运算中的依据。排序域的类型可以是整数，也可以是字符串，甚至可以是组合类型。例如，右图中，排序码是{游戏类别,编号}，它包含了2个域。关键码(key)：唯一确定记录的一个或多个域。例如在学生记录中，学号是关键码，姓名不是。排序码不一定是关键码。例如可以按学号对学生记录进行排序，也可以按姓名对学生记录进行排序。如果排序码不是关键码，这时就可能有多个记录具有同

5、一个排序码，因而排序的结果就可能不唯一。一级排序、二级排序、…一级排序：对序列中的记录按一个排序码进行排序。二级排序：先按第一个排序码排序；对于第一个排序码相同的记录，则按第二个排序码排序。二级排序不减序列(增序)，不减序列(降序)给定一个序列R={r1,r2,…,rn}，其排序码分别为k={k1,k2,…,kn}，排序的目的就是将R中的记录按照特定的顺序重新排列，形成一个新的有序序列R'={r'1,r'2,…,r'n}，相应排序码为k'={k'1,k'2,…,k'n}，其中k'1≤k'2≤…≤k'n或k'1≥k'2≥…≥k'n，前者称为不减序列，后者称为

6、不增序列。如果没有重复的排序码，即k'1k'2>…>k'n，则前者称为增序，或者称为降序。在要求不很严格的情况下，也称不减序列为增序，称不增序列为降序。正序和逆序如果待排序序列正好符合排序要求，则称这样的序列为“正序”序列。如果把待排序序列逆转过来，也正好符号排序要求，则称这样的序列为“逆序”序列。说明如无特殊说明，本章在介绍各种排序算法时一般是对序列进行不减或增序排序，序列中的每个记录只有一个域，且为整数，这个域充当排序码。考虑到C++中数组下标都是从0开始计起的，本章讨论的大部分序列的下标也从0开始计起。因此，我们讨论的序

7、列为R={r0,r1,…,rn-1}。稳定和不稳定的排序算法如果存在多个具有相同排序码的记录，采用某种排序算法进行排序后这些记录的相对次序仍然保持不变，则这样的排序算法称为是稳定的(stable)，否则称为不稳定的。在某些应用领域中，可能要求尽量不要改变相同排序码的记录的原始输入顺序，这就需要采用稳定的排序算法。排序算法的时间复杂度排序算法太多了，因此有的时候就需要在多个排序算法之间进行取舍。评价一种排序算法的好坏主要是通过空间复杂度和时间复杂度两方面来衡量，尤其是时间复杂度。算法的时间复杂度一般通过排序过程中记录的比较和交换次数来衡量。(比较和交换往往是

8、排序算法中的基本运算)一般而言，自然是排序所需的时间越短的算法越好