第六章 外排序算法(2012)

算法设计与分析C语⾔描述（陈慧南版）课后答案第⼀章15P1-3. 最⼤公约数为1。

快1414倍。

主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。

第⼆章32P2-8.（1）画线语句的执⾏次数为log n 。

(log )n O 。

划线语句的执⾏次数应该理解为⼀格整体。

（2）画线语句的执⾏次数为111(1)(2)16jnii j k n n n ===++=∑∑∑。

3()n O 。

（3）画线语句的执⾏次数为。

O 。

（4）当n 为奇数时画线语句的执⾏次数为(1)(3)4n n ++，当n 为偶数时画线语句的执⾏次数为 2(2)4n +。

2()n O 。

2-10.（1）当 1n ≥ 时，225825n n n -+≤，所以，可选 5c =，01n =。

对于0n n ≥，22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。

（2）当 8n ≥ 时，2222582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。

对于0n n ≥，22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。

（3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以22582()n n n -+=Θ。

2-11. (1) 当3n ≥时，3log log n n n <<，所以()20log 21f n n n n =+<，3()log 2g n n n n =+>。

可选 212c =，03n =。

对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。

注意：是f (n )和g (n )的关系。

相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：1、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。

反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。

假如变成a1,a4, a2,a3,a5就不是稳定的了。

2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

功能：选择排序输入：数组名称（也就是数组首地址）、数组中元素个数算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。

算法复杂度O(n2)--[n的平方void select_sort(int *x, int n){int i, j, min, t;for (i=0; i<n-1; i++) /*要选择的次数：0~n-2共n-1次*/{min = i; /*假设当前下标为i的数最小，比较后再调整*/for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/{if (*(x+j) < *(x+min)){min = j; /*如果后面的数比前面的小，则记下它的下标*/}}if (min != i) /*如果min在循环中改变了，就需要交换数据*/{t = *(x+i);*(x+i) = *(x+min);*(x+min) = t;}}/*功能：直接插入排序输入：数组名称（也就是数组首地址）、数组中元素个数算法思想简单描述：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。

排序有哪几种方法排序是计算机科学中非常重要的概念之一，它指的是将一组元素按照某种规则进行重新排列的过程。

排序算法可以分为多种类型，包括插入排序、交换排序、选择排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

下面我将详细介绍每种排序方法的原理、特点和应用场景。

1. 插入排序（Insertion Sort）插入排序是一种简单且直观的排序算法。

它的原理是将一个未排序的元素逐个地插入到已排序的部分中，最终形成一个完全有序的序列。

具体操作是从第二个元素开始，将其与前面已排序的元素逐个比较并插入到正确的位置。

插入排序的时间复杂度为O(n^2)，适用于小规模或部分有序的序列。

2. 交换排序（Exchange Sort）交换排序包括冒泡排序和快速排序。

冒泡排序（Bubble Sort）的原理是从头到尾依次比较相邻的两个元素，如果顺序不对则交换位置，一轮下来可以将最大的元素移动到末尾。

快速排序（Quick Sort）使用了分治的思想，通过选择一个基准元素将序列分成左右两部分，左边的元素都小于该基准值，右边的元素都大于该基准值，然后递归地对左右两部分进行快速排序。

交换排序的平均时间复杂度为O(nlogn)，适合用于排序大规模随机数据。

3. 选择排序（Selection Sort）选择排序的原理很简单：每一次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

具体操作是通过不断找到最小元素的索引，然后将其与第一个未排序元素交换，如此循环直到所有元素都被排序。

选择排序的时间复杂度为O(n^2)，适用于简单的排序需求。

4. 归并排序（Merge Sort）归并排序采用了分治的思想，将一个序列递归地分成两个子序列，直到每个子序列只有一个元素，然后将两个有序的子序列合并成一个有序的序列。

具体操作是比较两个子序列的第一个元素，将较小的元素放入结果序列，然后再比较较小元素所在子序列的下一个元素与另一个子序列的第一个元素，直到所有元素都被放入结果序列。

数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。

3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。

4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。

5.以三元组顺序表存放的稀疏矩阵的转置算法。

6.⼆叉树的性质及其四种遍历算法。

7.森林与⼆叉树的相互转换。

8.WPL、前缀编码的概念，哈夫曼树的构造算法。

9.图的相关概念，邻接矩阵及邻接表的存储结构。

10.图的深度优先/⼴度优先遍历算法。

11.最⼩⽣成树的两种算法。

12.拓扑排序的意义和算法。

13.最短路径算法。

14.顺序表、有序表的查找算法。

15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。

16.哈希表的相关概念，常⽤的冲突处理⽅法。

17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。

注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。

2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。

其他的算法则可能会出现在“算法题”中。

⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。

（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。

（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。

A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。

A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。

A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。

常见排序算法及其对应的时间复杂度和空间复杂度排序算法经过长时间演变，⼤体可以分为两类：内排序和外排序。

在排序过程中，全部记录存放在内存，则成为内排序；如果排序过程中需要使⽤外存，则称为外排序，本⽂讲的都属于内排序。

内排序有可以分为以下⼏类：（1）插⼊排序：直接插⼊排序、⼆分法插⼊排序、希尔排序（2）选择排序：直接选择排序、堆排序（3）交换排序：冒泡排序、快速排序（4）归并排序（5）基数排序排序⽅法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性复杂性直接插⼊排序O(n2)O(n2)O(n)O(1)稳定简单希尔排序O(nlog2n)O(n2)O(n1.3)O(1)不稳定较复杂直接选择排序O(n2)O(n2)O(n2)O(1)不稳定简单堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定较复杂冒泡排序O(n2)O(n2)O(n)O(1)稳定简单快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定较复杂归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定较复杂基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(n+r)稳定较复杂⼀、插⼊排序•思想：每步将⼀个待排序的记录，按其顺序码⼤⼩插⼊到前⾯已经排序的字序列的合适位置，直到全部插⼊排序完为⽌。

•关键问题：在前⾯已经排好序的序列中找到合适的插⼊位置。

•⽅法：直接插⼊排序插⼊排序的最好情况是数组已经有序，此时只需要进⾏n-1次⽐较，时间复杂度为O(n)最坏情况是数组逆序排序，此时需要进⾏n(n-1)/2次⽐较以及n-1次赋值操作（插⼊）平均来说插⼊排序算法的复杂度为O(n2)空间复杂度上，直接插⼊法是就地排序，空间复杂度为(O(1))⼆分插⼊排序最坏情况：每次都在有序序列的起始位置插⼊，则整个有序序列的元素需要后移，时间复杂度为O(n2)最好情况：待排序数组本⾝就是正序的，每个元素所在位置即为它的插⼊位置，此时时间复杂度仅为⽐较时的时间复杂度，为O(log2n)平均情况：O(n2)空间复杂度上，⼆分插⼊也是就地排序，空间复杂度为(O(1))。

广工数据结构课程设计一、课程目标知识目标：1. 让学生掌握数据结构的基本概念，包括线性表、树、图等结构的特点及应用场景。

2. 使学生了解不同数据结构在计算机存储和处理中的优势与局限性，如时间复杂度和空间复杂度分析。

3. 帮助学生掌握常见算法的设计思想及其在数据结构中的应用，如排序、查找等。

技能目标：1. 培养学生运用数据结构解决实际问题的能力，能够根据问题需求选择合适的数据结构进行建模。

2. 提高学生编写高效算法代码的能力，能够对常见数据结构及其算法进行熟练编程实现。

3. 培养学生运用所学知识进行项目设计和团队协作的能力。

情感态度价值观目标：1. 激发学生对数据结构课程的兴趣，培养其主动探索和钻研的精神。

2. 培养学生具备良好的逻辑思维能力，严谨的科学态度和团队协作精神。

3. 使学生认识到数据结构在实际应用中的重要性，提高其运用计算机知识解决实际问题的自信心。

课程性质分析：本课程为广工数据结构课程设计，旨在帮助学生将理论知识与实际应用相结合，提高其编程实践能力和问题解决能力。

学生特点分析：学生已具备一定的编程基础，掌握了C/C++等编程语言，但对数据结构的应用和算法设计尚处于入门阶段。

教学要求：结合课程性质和学生特点，注重理论与实践相结合，以项目驱动教学，使学生在实践中掌握数据结构知识，提高编程能力。

通过课程目标分解，确保学生在课程结束后能够达到预期学习成果，为后续课程和实际工作打下坚实基础。

二、教学内容1. 线性表：介绍线性表的定义、特点及存储结构，包括顺序存储和链式存储。

以教材第二章内容为基础，讲解线性表的插入、删除、查找等基本操作。

- 教学安排：2课时- 教材章节：第二章 线性表2. 栈与队列：讲解栈和队列的基本概念、性质及用途，分析它们在解决实际问题中的应用。

- 教学安排：2课时- 教材章节：第三章 栈和队列3. 树与二叉树：阐述树的基本概念、性质和存储结构，重点讲解二叉树的性质、遍历方法及应用。

《数据结构》课程大纲一、课程简介课程名称：数据结构学时/学分：68/4先修课程：程序设计教学目标：在学生已掌握了结构化程序设计和面向对象程序设计的基础上，进一步介绍数据结构和算法设计/分析的基本知识。

本课程围绕着数据结构的思想、方法、实现和应用等方面，培养学生掌握设计一个有效的算法和数据结构的能力，以及用计算机解决问题的能力。

主要内容：以数据的逻辑关系为线索，介绍了线性关系、树状关系、集合关系和图型关系的数据元素的存储及处理方法、每个数据结构对应的类的C++实现、以及每个数据结构的主要应用。

二、教学内容第一章绪论主要内容：数据结构的研究内容、算法分析。

教学目标：了解数据结构研究的内容，掌握算法的时间复杂度及空间复杂度的计算。

重点与难点：什么是数据结构，如何计算算法的时间复杂度。

第二章线性表主要内容：线性表的顺序实现和链接实现。

教学目标：理解顺序存储和链接存储，熟练掌握顺序表和各种链接表的实现方法，掌握如何将一个数据结构封装成类。

重点与难点：如何用面向对象的方法封装一个类。

第三章栈主要内容：栈的顺序实现和链接实现，栈的主要应用。

教学目标：熟练掌握顺序栈和链接栈的实现，了解栈的主要应用。

重点与难点：如何用栈消除递归、计算算术表达式和检查程序中的括号配对。

第四章队列主要内容：队列的顺序实现和链接实现、队列的应用。

教学目标：熟练掌握顺序队列和链接队列的实现，了解排队系统模拟的基本思想。

重点与难点：循环队列的实现，排队系统的模拟。

第五章树主要内容：树和二叉树的实现，以及树的应用。

教学目标：熟练掌握二叉树的链接实现。

重点与难点：二叉树的实现。

第六章优先级队列主要内容：基于树的优先级队列的实现和应用。

教学目标：熟练掌握二叉堆的实现，掌握基于二叉堆的优先级队列的实现，了解多服务台的排队系统的模拟。

重点与难点：二叉堆、多服务台的排队系统的模拟。

第七章集合与静态查找表主要内容：无序表和有序表的查找。

教学目标：熟练掌握顺序查找和二分查找，了解分块查找。

数据结构（Python版）教学大纲及教案第一章：引言1.1 课程介绍数据结构的重要性Python在数据结构中的应用课程目标和学习内容1.2 数据结构的基本概念什么是数据结构数据的抽象和表示常见数据结构类型1.3 Python编程环境Python安装和配置Python编程基础常用数据类型和操作第二章：线性表2.1 线性表的定义和性质线性表的概念线性表的顺序存储结构线性表的链式存储结构2.2 线性表的基本操作线性表的插入和删除操作线性表的查找和排序操作线性表的常见算法实现2.3 Python中的线性表实现Python列表的使用Python元组的使用Python集合的使用第三章：栈和队列3.1 栈的定义和性质栈的概念栈的顺序存储结构栈的链式存储结构3.2 栈的基本操作栈的入栈和出栈操作栈的应用实例栈的算法实现3.3 队列的定义和性质队列的概念队列的顺序存储结构队列的链式存储结构3.4 队列的基本操作队列的入队和出队操作队列的应用实例队列的算法实现第四章：线性表的拓展4.1 双向链表双向链表的概念双向链表的存储结构双向链表的基本操作4.2 栈和队列的拓展栈的应用拓展队列的应用拓展栈和队列的其他变体4.3 Python中的拓展实现Python中的双向链表实现Python中的栈和队列实现第五章：非线性结构5.1 树的概念和性质树的基本概念树的存储结构树的遍历和操作5.2 常见的树结构二叉树binary search tree（BST）平衡树（AVL树）堆（Heap）5.3图的概念和性质图的基本概念图的存储结构图的遍历和操作5.4 Python中的非线性结构实现Python中的树结构实现Python中的图结构实现第六章：排序算法6.1 排序算法的概念与重要性排序算法的定义排序算法的作用排序算法的分类6.2 内部排序算法冒泡排序选择排序插入排序快速排序归并排序堆排序6.3 外部排序算法外部排序的概念外部排序的策略外部排序的实现6.4 Python中的排序算法实现Python内置的排序函数自定义排序函数第七章：查找算法7.1 查找算法概述查找算法的定义查找算法的作用查找算法的分类7.2 内部查找算法顺序查找二分查找分块查找7.3 哈希查找哈希查找的原理哈希函数的设计哈希冲突的解决方法7.4 Python中的查找算法实现Python内置的查找函数自定义查找函数第八章：树的高级应用8.1 平衡树（AVL树）平衡树的概念平衡树的性质平衡树的插入与删除8.2 红黑树红黑树的概念红黑树的性质红黑树的插入与删除8.3 堆（Heap）堆的概念堆的性质堆的插入与删除8.4 Python中的高级树结构实现Python中的平衡树实现Python中的红黑树实现Python中的堆实现第九章：图的算法9.1 图的算法概述图的算法的作用图的算法的分类9.2 深度优先搜索（DFS）DFS的概念DFS的实现DFS的应用9.3 广度优先搜索（BFS）BFS的概念BFS的实现BFS的应用9.4 最短路径算法迪杰斯特拉算法贝尔曼-福特算法Dijkstra算法A算法9.5 Python中的图算法实现Python内置的图库自定义图算法实现第十章：综合案例与实践10.1 数据结构在实际应用中的重要性数据结构在软件开发中的应用数据结构在数据分析中的应用数据结构在中的应用10.2 综合案例分析案例一：社交网络分析案例二：推荐系统案例三：网络爬虫10.3 实践项目项目一：实现一个简单的链表项目二：实现一个平衡二叉树项目三：实现一个图的搜索算法重点和难点解析重点环节1：线性表的基本概念和性质线性表的定义和特点线性表的顺序存储结构及其操作线性表的链式存储结构及其操作重点环节2：栈和队列的基本概念和性质栈的定义、特点和操作队列的定义、特点和操作栈和队列的典型应用场景重点环节3：线性表的拓展双向链表的结构和操作栈和队列的拓展形式Python中的实现方法和技巧重点环节4：非线性结构树的概念、分类和操作图的概念、分类和操作Python中的非线性结构实现方法重点环节5：排序算法和查找算法常见排序算法的原理和实现常见查找算法的原理和实现算法的时间复杂度和空间复杂度分析重点环节6：树的高级应用平衡树（AVL树）的概念和性质红黑树的概念和性质堆（Heap）的概念和性质Python中的高级树结构实现方法重点环节7：图的算法图的算法分类和应用场景深度优先搜索（DFS）和广度优先搜索（BFS）的原理和实现最短路径算法的原理和实现Python中的图算法实现方法重点环节8：综合案例与实践数据结构在实际应用中的重要性和作用社交网络分析、推荐系统和网络爬虫等案例的分析和实践实践项目的选题、实现方法和技巧本文主要分析了“数据结构（Python版）”教学大纲及教案中的重点环节，包括线性表、栈和队列、线性表的拓展、非线性结构、排序算法和查找算法、树的高级应用、图的算法以及综合案例与实践。

十大排序算法选择排序选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。

这样，经过i遍处理之后，前i个记录的位置已经是正确的了。

选择排序是不稳定的。

算法复杂度是O(n ^2 )。

class SelectionSorter{private int min;public void Sort(int[] arr){for (int i = 0; i < arr.Length - 1; ++i){min = i;for (int j = i + 1; j < arr.Length; ++j){if (arr[j] < arr[min])min = j;}int t = arr[min];arr[min] = arr[i];arr[i] = t;}}}冒泡排序冒泡排序方法是最简单的排序方法。

这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。

在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。

所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。

如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。

显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。

在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。

一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。

冒泡排序是稳定的。

算法时间复杂度是O(n ^2){public void Sort(int[] arr){int i, j, temp;bool done = false;j = 1;while ((j < arr.Length) && (!done))//判断长度{done = true;for (i = 0; i < arr.Length - j; i++){if (arr[i] > arr[i + 1]){done = false;temp = arr[i];arr[i] = arr[i + 1];//交换数据arr[i + 1] = temp;}}j++;}}}快速排序快速排序是对冒泡排序的一种本质改进。

数据结构c语言版第三版习题解答数据结构是计算机科学中非常重要的一门学科，它研究如何在计算机中存储和组织数据，以便有效地进行检索和操作。

数据结构的知识对于编写高效的程序和解决复杂的问题至关重要。

在学习和理解数据结构的过程中，解决习题是一种非常有效的方法。

本文将为读者提供《数据结构C语言版（第三版）》习题的解答。

1. 第一章：绪论第一章主要介绍了数据结构的基本概念和内容，包括算法和数据结构的概念、抽象数据类型（ADT）以及算法的评价等。

习题解答中，我们可以通过分析和讨论的方式对这些概念进行加深理解。

2. 第二章：算法分析第二章主要介绍了算法的基本概念和分析方法，包括时间复杂度和空间复杂度的计算方法。

习题解答中，我们可以通过具体的算法实例来计算其时间和空间复杂度，加深对算法分析的理解。

3. 第三章：线性表第三章主要介绍了线性表的概念和实现，包括顺序表和链表两种实现方式。

习题解答中，我们可以通过编写代码实现线性表的基本操作，并分析其时间和空间复杂度。

4. 第四章：栈和队列第四章主要介绍了栈和队列的概念和实现，包括顺序栈、链栈、顺序队列和链队列四种实现方式。

习题解答中，我们可以通过编写代码实现栈和队列的基本操作，并分析其时间和空间复杂度。

5. 第五章：串第五章主要介绍了串的概念和实现，包括顺序串和链串两种实现方式。

习题解答中，我们可以通过编写代码实现串的基本操作，并分析其时间和空间复杂度。

6. 第六章：树第六章主要介绍了树的概念和实现，包括二叉树、哈夫曼树和赫夫曼编码等内容。

习题解答中，我们可以通过编写代码实现树的基本操作，并分析其时间和空间复杂度。

7. 第七章：图第七章主要介绍了图的基本概念和实现，包括图的表示方法和图的遍历算法等。

习题解答中，我们可以通过编写代码实现图的基本操作，并分析其时间和空间复杂度。

8. 第八章：查找第八章主要介绍了查找算法的基本概念和实现，包括顺序查找、二分查找、哈希查找等内容。

外排序置换选择算法
外排序（External Sorting）是一种处理大量数据的排序算法，当数据量太大，无法一次性装入内存时，就需要使用外排序。

置换-选择排序（Replacement-Selection Sort）是外排序的一种算法。

置换-选择排序的基本思想是：
1. 从待排序的数据中提取一个长度为K的子序列（K为常数），然后利用任何有效的内部排序算法对这个子序列进行排序。

2. 将排序后的子序列与原始数据记录进行比较，找出并输出所有比排序后子序列大的记录。

3. 重复步骤1和2，直到所有记录都排好序为止。

置换-选择排序的时间复杂度为O(n^2)，其中n为待排序的数据量。

这是因为每次提取的子序列长度为常数K，所以需要比较的次数为O(n/K)，而提
取子序列和内部排序的时间复杂度均为O(n)。

因此，总的时间复杂度为
O(n^2)。

置换-选择排序的优点是简单易实现，适用于数据量较大且内存受限的情况。

但是，由于其时间复杂度较高，对于大规模数据的排序效率较低。

因此，在
实际应用中，通常会采用其他更高效的外部排序算法，如多路归并排序、基数排序等。

外部排序算法-基于堆排序（最⼤堆）+最⼤赢者树外部排序，则是每次进⾏部分排序，然后将各组部分排序的结果合并，再次排序得到最终的结果．本⽂中的程序⽤最⼤堆和最⼤赢者树完成了⼀个外部排序算法，基本思想如下：将Ｎ个元素的⼤数组拆成每个元素为Ｍ的⼦数组，得到X=(N/M)个⼦数组；对这Ｘ个⼦数组，依次使⽤堆排序进⾏排序；初始化最⼤赢者树：取出这Ｘ个⼦数组的最⼤元素，初始化⼀颗Ｘ个元素的最⼤赢者树；每次从最⼤赢者树弹出⼀个最⼤值后，再从对应最⼤堆⾥⾯取出⼀个次⼤元素，补充进最⼤赢者树；不停循环步骤４，直到所有最⼤堆⾥的元素都被弹出．外存交互⽅式为了便于分别管理⼦数组，这⾥使⽤⽂件存放每⼀个⼦数组，⼀个⼦数组存放到⼀个⽂件⾥⾯，记录下来其对应的⽂件名。

使⽤vector<string> fileNames记录每⼀个⼦数组⽂件名称。

⼦数组内部排序这⾥使⽤c++ 提供的快速排序算法。

从原始的输⼊⽂件⾥⾯⼀次读⼊vector<int> arr，这⾥将arr⼤⼩,即每⼀个⼦数组⼤⼩，设置为heap_size。

当数组存满时，便排序后写⼊外存⽂件，再清空数组。

if(arr.size()==heap_size){sort(arr.begin(),arr.end(),greater<int>());//降序排列out.open(fileNames[i++]);if (!out){cout << "⽂件不能打开" <<endl;return -1;}for(int s:arr){out<<s<<" ";}out<<endl;out.close();arr.clear();}最⼤赢者树c++提供了现成的堆：优先队列，这⾥为了找到堆中每⼀个元素所属于哪⼀个⼦数组（⽂件），堆⾥存放的是元素和其对应的⼦数组的外存位置（⽂件名）：pair<int,string> = make_pair(待排序元素，所在⽂件名)，采⽤⾃定义堆排序：根据待排序元素⼤⼩构建⼀个⼤顶堆/**⾃构建⽐较函数**/struct cmp{bool operator()(Pair a, Pair b) {return a < b; //利⽤pair的重载运算符}};priority_queue<Pair, vector<Pair>, cmp > Tree; //使⽤⼤顶堆构造最⼤赢者树初始化⼤顶堆后删除每⼀个⼦数组⽂件的头⼀个元素（最⼤值），表⽰该元素由外存引⼊内存。