数据结构 第十章-排序

本文提出了一种对文件或表格中的记录进行排序的新方法。该方法基于将文件或表格中的记录按大小顺序排列成关键词的原则。假设n个记录的文件是(R1，R2，Rn)和相应的关键字是(K1，K2，Kn)，排序是为了确定下面的排列p1，p2，pn，使得： kp1Kp20.Kpn以获得有序文件(Rp1，Rp2，Rpn)，学生成绩表，12345，学生编号名称，数学，外语，学生编号，名称，数学，外语，12345，学生编号，名称，数学，外语，学生编号，名称，数学，外语，总分，12345，12345，(a)无序表，(b)按学生编号排序表，(c)按数学分数排序表，(d)按总分排序表，2。假设在要排序的文件中，有两个记录R(i)和R(j)具有相同的关键字，其中R(i)位于R(j)之前，那么排序的稳定性是什么。在通过某种排序方法排序之后，R(i)仍然在R(j)之前，那么该排序方法被称为是稳定的。否则，排名方法就不稳定。示例序列(10，25，22，42，25，30，18) (10，18，22，25，25，30，42) (10，25，22，42，25，30，18) (10，18，22，25，25，30，42)，稳定排序，不稳定排序，12345，学生姓名，数学外语，学生姓名，数学外语，12345，(e)按数学排序的列表内部排序(internal sort )-指的是要排序的文件不大，并且可以在内存中一次完成的排序。也就是说，在分类过程中，分类过程不使用计算机外部存储器。分拣速度快。外部排序(external sorting)-指的是要排序的文件很大并存储在外部存储器中，不能一次转移到内存中的排序。也就是说，在排序过程中，需要访问外部存储。分拣速度很慢。本章主要讨论各种内部排序方法。4。要排序的记录和序列表(文件)的数据类型#defineMAXSIZE20/是typedefintKeyType的最大长度。/关键字typedefstruct/记录类型 keytypekey/关键字InfoTypeotherinfo；/其他数据类型矩形；/记录类型名称typedefstruct rechtypermaxsize 1；/r0被用作监视哨所长度；/实际表长度 seqlist/记录表类型或表和表长度分别定义和描述矩形最大尺寸1；/r0被用作监视哨所长度；/实际表格长度，5。排序算法分析(1)时间复杂度排序N条记录，要比较的关键词数；最佳案例；最坏的情况；平均来说，n条记录被排序，记录需要移动的次数；最佳案例；最坏的情况；平均事例(2)空间复杂性排序过程中所需的辅助存储空间量，文件中记录所占的空间除外。6。内部排序方法(1)在订单上插入排序：直接插入排序；半插入排序；双向插入排序；表插入排序；贝壳分类；交换排序：冒泡排序：单向冒泡排序、双向冒泡排序、快速排序、选择排序：简单选择排序；树选择排序；堆排序，合并排序2路合并排序k路合并排序基数排序多关键字排序最高优先级方法最低优先级方法链基数排序(2)直接插入单个链表排序，简单选择，冒泡排序，基数排序，DonaldErvinKnuth gardner (1938-)斯坦福大学教授1974年图灵奖获得者，计算机程序设计的艺术 ARETTOFUC PROGRAMING vol . 1:Basic Algorithms 1968 vol . 2:Semi-Digital Algorithms 1969 vol . 3:Sorting and Search 1973 vol . 4:Combination Algorithms，01010 计算机与排版，10.2插入排序算法基本思想是将待排序的记录插入到已排序的子文件中，以便插入后获得的子文件仍然是已排序的子文件。 为了插入记录，必须首先搜索有序的子文件，以确定记录的插入位置。根据搜索方法的不同，插入排序可以分为线性插入排序和半插入排序。前者使用顺序搜索，后者使用半搜索。，1。直接插入排序(线性插入排序)将文件设置为：()关键是：(1)。基，r2。钥匙，rn。键)首先，将初始文件中的记录R 1视为有序子文件；传递1:将r2插入到有序子文件中。如果r2。凯尔一世。键，交换r .I和r .I 1的位置；否则，就不会有交换。(i=1，2，n-2)在第二遍之后，第一个n-1关键词中的最大记录移动到rn-1的位置。进行n-1旅行，或者不需要交换记录。例如，第一次行程、第二次行程、第三次行程、第四次行程，k1=432121212121151515 k2=21434343431515212121 k3=898989151515282828 k4=15151515892828434343434343434 K5=282888944对于(I=0；j1) temp=aj；/交换记录aj=aj 1；aj 1=temp；对于(I=0；I1，真，假，I-，调整剩余i-1节点的二叉树，初始化堆，选择并调整n-1次，算法分析和评估：对于深度为k的堆，调整算法进行关键字比较的次数最多为2次(k-1)，建立n个元素的初始堆，调用HeapAdjust算法n/2次，关键字比较的次数总共不超过4n次。n个节点的完整二叉树深度是h=log2n1。要调整的层是h-1到1。基于第一层中节点的二叉树深度对应于h-L1，并且第一层中节点的最大数量是2i-1。因此，调整期间的比较键是2i-1 * 2 *(h-L1-1)=2i *(h-1)以使j=h-1，当i=h-1时，j=1当i=1时，j=h-12h-j * j=2h-1 * 2h-2 * 2.21 *(h-1)=2 h1-2h-22 h1=2 log 2 N2=4 * 2 log 2n=4n，算法分析与评估(续):n个节点的完整二叉树深度为log2n1，调整过程选择n-1次。比较的总数最多为2 (log2 (n-1) log2 (n-2).log22) 2n (log2n)。在最坏的情况下，算法的时间复杂度为o(4nlogn)o(nlogn)；交换只需要一个记录大小的辅助存储空间；堆排序不稳定。不建议对记录较少的文档进行堆排序，堆排序对较大的文档非常有效。(78，14，8，89，75，71，44，68，33)要排序的堆排序示例模拟记录的关键字是：(78，14，8，89，75，71，44，68，33)，它们是使用“大顶堆”排序方法排序的。从大到小的顺序是(89，78，75，71，68，44，33，14，8)。练习：已知要排序的序列是(503，87，512，61，908，170，897，275，653，462)。(1)建立一个堆(绘制第一步和最后一个堆的结果图)，希望首先输出最小值。(2)如何在输出最小值后得到次最小值。(并画出相应的结果图)，10.5合并排序的基本思想：将k(k2)个有序子文件合并在一起形成一个新的有序文件。同时合并k个有序子文件的排序过程称为k路合并排序。双向合并排序：对2个有序子文件进行合并排序。例如，订单文件A和A被合并到订单文件c中。A=(2，10，15，18，21，30) b=(5，20，