下载文档原格式
数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科.数据: 所有能输入到计算机中并被计算机程序处理的符号的总称.数据元素: 在计算机上程序中通常作为一个整体进行考虑和处理.数据对象: 是性质相同的数据元素的集合,是数据的一个子集.数据类型: 一个值的集合和定义在这个值集上的一组操作的总称.线性表: 最常用却最简单的一种数据结构.栈:限定仅在表尾进行插入或删除操作的线性表. 栈顶:线性表尾端(表尾端)栈底:线性表头端(表头端)空栈:不含元素的空表. 队列:一种先进先出的线性表.队尾:在队列中,允许插入的一端.队头:在队列中.允许删除的一端.根的结点:在任意一棵非空树中,有且仅有一个特定的.结点的度:结点拥有的子树数.叶子: 度为0的结点.树的度: 树内各结点的度的最大值．非终端结点：度不为零的结点．孩子：结点的子树的根．双亲：该结点称为孩子的双亲．兄弟：同一个双亲的孩子之间．堂兄弟：双亲在同一层的结点．祖先：从根到该结点所经分支上的所有结点．孙子：以某结点为根的子树中的任一结点都称为该结点的孙子．树的深度：树中结点的最大层次．结点的层次：从根开始定义起，根为第一层，根的孩子为第二层．有序树：如果将树中结点的各子树看成从左到右是有次序的，就．．．．．（即不能互换）．无序树：（见有序树），否则称为无序树．森林：是m棵互不相交的树的集合．二叉树：是结点的有限集合，它可以为空，也可以是由一根结点和称为根的左右子树的两棵子树组成．满二叉树：一棵深度为k具有2k－1（应该是２的k次方再减1）结点的二叉树．完全二叉树：深度为Ｋ的，有n个结点的二叉树，当且仅当其每一个结点都与深度为Ｋ的满二叉树中编号从1至n的结点一一对应时．图：是一种较线性表和树更为复杂的数据结构．有向图／无向图：设ＶＲ是两个顶点之间的关系的集合，若＜v，w＞∈VR,则＜v，w＞表示从v到w的一条弧，此时的图称为有向图，／若＜v，w＞∈VR必有＜w，v＞∈VR，即ＶＲ是对称的，表示v和w之间的一条边，此时的图称为无向图．子图：假设有两个图Ｇ＝（Ｖ，｛Ｅ｝）和Ｇ＇＝（Ｖ＇，｛Ｅ＇｝），如果Ｖ＇包含于Ｖ且Ｅ＇包含于Ｅ，则称Ｇ＇为Ｇ的子图．完全图：有n（n－1）/2条边的无向图．邻接结点：孤立点:孤点的度:入度:对于有向图，以某顶点为弧头的弧的数目为该顶点的入度出度:以某顶点为弧尾的弧的数目为该顶点的出度路径:从树中一个结点到另一个结点之间的分支就构成这两个结点之间的路径路径长度:路径上经过的边或弧的数目叫路径长度回路:若一条路径上开始点和终止点相同则称此路径为回路。
关于多路归并排序外部排序⽐如⽂件内有1亿数据排序。
编程珠玑第⼀个case是有关⼀个技巧性解决外部排序问题的。
问题很巧妙的解决了，但⼀开始提到的利⽤归并排序进⾏外部排序的算法仍值得仔细探究⼀下，毕竟本科时学的不是很深⼊。
先来看内部排序中最简单的2路归并排序算法。
算法核⼼操作是将⼀维数组中前后相邻的两个有序序列归并为⼀个有序序列，给定数组中序列界限i、m、n，⽤2个下标变量分别从i和j=m+1开始逐个往后处理，先⽐较，⼩的写到结果序列的当前遍历下标k中，相应下标⾃增继续⽐较直到某个序列的下标⾛到边界，再将另外⼀个序列的剩余元素拷贝到结果序列中。
算法可⽤递归或递推实现，从相邻的两两元素开始不断调⽤上⾯的核⼼操作组成较长有序序列直到完成整个序列。
算法进⾏⼀趟归并就得到⼀个局部有序的完整新序列，n个元素共需要log2n趟归并，每趟完成⽐较操作n次（1次得到序列的1个值），得到的新序列写到结果序列空间中，下⼀趟之前要先将结果序列复制⼀份到临时空间，下⼀趟归并在临时空间上进⾏。
因此时间复杂度nlog2n，空间上除了原始序列空间n、结果序列空间n，还需要辅助临时空间n。
接下来看外部排序。
外部排序指的是⼤⽂件的排序，即待排序的记录存储在外存储器上，待排序的⽂件⽆法⼀次装⼊内存，需要在内存和外部存储器之间进⾏多次数据交换，以达到排序整个⽂件的⽬的。
外部排序最常⽤的算法是多路归并排序，即将原⽂件分解成多个能够⼀次性装⼊内存的部分，分别把每⼀部分调⼊内存完成排序。
然后，对已经排序的⼦⽂件进⾏多路归并排序。
多路归并排序算法在常见数据结构书中都有涉及。
从2路到多路（k路），增⼤k可以减少外存信息读写时间，但k个归并段中选取最⼩的记录需要⽐较k-1次，为得到u个记录的⼀个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的⽂件进⾏外排时，内部归并过程中进⾏的总的⽐较次数为s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，⽽(k-1)/log2k随k增⽽增因此内部归并时间随k增长⽽增长了，抵消了外存读写减少的时间，这样做不⾏，由此引出了“败者树”treeof loser的使⽤。
第11章 外部排序一、选择题1．下列排序算法中，其中（）是稳定的。
A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。
不稳定排序有：快速排序、堆排序、shell排序。
时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。
3．在下面的排序方法中，辅助空间为O（n）的是（）。
A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。
A．归并排序B．快速排序C．希尔排序D．堆排序【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。
5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．N B．2N-1 C．2N D．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。
最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序最好情况下的复杂度为O（n）。
6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。
插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。
将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。
【数据结构】排序——外部排序【数据结构】排序——外部排序外部排序是指⼤⽂件的排序，即排序的记录存储在外存储器上，在排序过程中需进⾏多次的内、外存之间的交换。
外部排序⽅法通常采⽤归并排序有外部排序基本上由两个相对独⽴的阶段组成。
按可⽤内存⼤⼩，将外存上含有n个记录的⽂件分成若⼲长度为l的字⽂件或段。
依次读⼊内存并利⽤有效的内部排序⽅法排序，将排序后得到的有序⼦⽂件（称为归并段或顺串），进⾏逐趟归并，直⾄得到整个有序⽂件为⽌。
在外部排序中实现两两归并，由于不可能将两个有序段及归并结果段同时存放在内存中的缘故，所以不仅要调⽤归并过程，还需要进⾏外存的读_写（对外存上信息的读_写是以“物理块”为单位的）。
耗费时间总时间=内部排序时间(产⽣初始归并段)+外存读写时间+内部归并时间内部排序时间=经过内部排序后得到的初始归并段的个数r * 得到⼀个初始归并段进⾏内部排序多需时间的均值外存读写时间=总的读写次数 * 进⾏⼀次外存读写时间的均值内部归并时间=归并的趟数s * n个记录进⾏内部归并排序的时间优化⽅法增⼤归并路数k减少初始归并段个数r以上两个⽅法都可以减少归并的趟数，进⽽减少读写磁盘的次数，提⾼外部排序速度多路平衡归并与败者树已知增加k可以减少s，从⽽减少总的读写次数。
如果只单纯的增加k⼜会导致内部归并时间增加。
为了使内部归并不受k的增⼤⽽影响，提出了败者树。
败者树的基本思想败者树是树形选择排序的⼀种变型，可视为⼀棵完全⼆叉树。
k个叶⼦节点分别存放k个归并段在归并过程中当前参加⽐较的记录，内部节点⽤来记忆左右⼦树中的“失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点。
若⽐较两个数，⼤的为败者、⼩的为胜利者，则根结点指向的数为最⼩数。
eg、设初始归并段为(10,15,31),(9,20),(6,15,42),(12,37),(84,95),利⽤败者树进⾏m路归并，⼿⼯执⾏选择最⼩的5个关键字的过程。
性能分析k-路归并的败者树的深度为[log2k]+1注意⚠ 在多路平衡归并中采⽤简单⽐较时，k越⼤，关键字的⽐较次数会越⼤。
解决大规模数据问题的外部排序算法外部排序是一种处理大规模数据的排序算法，由于内存限制，无法将所有数据加载到内存中进行排序。
所以，外部排序利用磁盘空间来进行数据的划分和排序，以解决大规模数据问题。
本文将介绍一种常用的外部排序算法——多路归并排序。
一、多路归并排序概述多路归并排序是一种基于分治思想的排序方法，它将大规模数据划分为多个小块，并在磁盘上对这些小块进行排序。
然后，再将排好序的小块进行归并，最终得到完整有序的数据。
多路归并排序多用于外排序，其主要特点是能够处理大规模数据，并且排序效率较高。
二、多路归并排序的实现步骤1. 数据划分首先，将大规模数据划分为多个小块。
可以通过读取数据集并将其划分为大小相等的块，每个块的大小受到内存大小的限制。
2. 内部排序对每个小块进行内部排序，常用的内部排序算法包括快速排序、归并排序、堆排序等。
选择合适的内部排序算法，将小块排序后存放在磁盘中。
3. 多路归并将排好序的小块进行多路归并。
多路归并即将多个有序的序列合并为一个有序序列。
在多路归并中，可以借助最小堆等数据结构，每次从多个序列中选择最小的元素，加入到有序序列中。
4. 写出结果将最终得到的有序序列写出到磁盘文件中。
三、多路归并排序算法的优化1. 外部排序的前提是磁盘I/O的次数尽可能少，因此可以采用合适的数据结构来减少读写次数，如B+树等。
2. 利用多线程或多进程进行归并操作可以加快排序速度。
可以将原始数据划分为多个小块，并利用多个线程或进程分别对这些小块进行排序和归并。
3. 预读数据是提高排序效率的一个关键。
可以采用预读技术，提前将数据加载到内存缓冲区中，减少磁盘I/O的次数。
4. 考虑数据的分布情况进行数据划分。
如果数据是有序的，可以将其均匀划分到不同的小块中，以充分利用有序性。
四、总结多路归并排序是一种有效解决大规模数据问题的外部排序算法。
通过将数据划分为多个小块，并采用多路归并的方式进行排序，可以充分利用磁盘空间和减少磁盘I/O次数。
外部排序---数据结构外部排序数据结构在计算机科学中，数据的排序是一项非常基础且重要的操作。
当数据量过大，无法一次性全部放入内存进行排序时，就需要用到外部排序这种技术。
想象一下，你有一个巨大的数据集，大到内存根本装不下。
这时候，内部排序算法，比如快速排序、冒泡排序等等，就显得无能为力了。
外部排序就像是一位超级英雄，专门来解决这种内存装不下的大问题。
外部排序的基本思路其实并不复杂，但实现起来却需要一些巧妙的策略。
它通常会将数据分成多个较小的部分，先在内存中对这些小部分进行排序，然后将排序好的小部分逐次合并，最终得到完全有序的数据。
为了更好地理解外部排序，让我们先来看看它的工作流程。
假设我们有一个非常大的文件需要排序，由于内存限制，我们不能一次性把整个文件读入内存。
所以，第一步就是将这个大文件分割成若干个大小适中的子文件，这些子文件能够被轻松地读入内存。
然后，我们在内存中使用一种内部排序算法，比如快速排序，对每个子文件进行单独排序。
接下来就是关键的合并步骤。
我们会从已经排序好的子文件中依次读取数据，然后将它们合并到一个新的文件中。
这个合并的过程就像是把几堆已经排好序的扑克牌重新整理成一整堆有序的扑克牌。
在合并的过程中，我们需要不断地比较来自不同子文件的数据，将较小的数据先放入新文件中。
那么，在这个过程中，有哪些关键的技术和要点呢？首先是数据的分割策略。
我们要确保分割出来的子文件大小合适，既能在内存中高效处理，又不会导致分割次数过多而增加额外的开销。
如果子文件分得太小，那么合并的次数就会增多，效率就会降低；如果分得太大，又无法在内存中进行排序。
其次是内存的使用。
在外部排序中，内存的使用需要非常精细地管理。
我们不仅要为读取和写入数据留出空间，还要为中间的比较和合并操作保留足够的缓冲区。
如果内存使用不当，可能会导致频繁的磁盘读写，大大降低排序的速度。
还有就是合并算法的选择。
常见的合并算法有二路归并和多路归并。
