高中信息技术-竞赛班数据结构专项培训教程-05矩阵的压缩存储教案

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 2 3 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。

1.课程设计的目的(1> 熟练使用 C ++语言编写程序，解决实际问题。

(2> 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。

(3> 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

(4> 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

2.需求分析问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。

基本要求：1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。

2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。

特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。

最常见的特殊矩阵有对称矩阵、上(下>三角矩阵、对角矩阵等。

b5E2RGbCAP 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。

p1EanqFDPw3.矩阵的压缩与解压缩问题的设计图1-14.调试分析图1-2程序运行界面图1-3 程序运行界面图1-4 文件的输入5.小结经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。

以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！DXDiTa9E3d6、参考文献[1]严蔚敏，吴伟民编著. 数据结构(C 语言版>--北京: 清华大学出版社，2007.2[2]严蔚敏，吴伟民M宁编著. 数据结构题集(C 语言版>--北京: 清华大学出版社，2007.3[3]网上搜索相关程序作为参考附录：#include <iostream>#include<fstream>using namespace std。

信息学竞赛中的算法与数据结构讲解教案一、引言信息学竞赛是一种基于计算机科学和数学的竞争形式，其中算法与数据结构是竞赛中最为核心和关键的内容之一。

本教案将详细讲解信息学竞赛中常用的算法和数据结构，并提供相关示例和题目，以帮助学生深入理解和掌握这些知识点。

二、算法1. 算法的概念算法是一系列解决问题的步骤或方法。

在信息学竞赛中，算法常被用于解决各种问题，如排序、查找、图遍历等。

掌握不同类型的算法对于竞赛成绩的提升至关重要。

2. 常见算法类型及其应用（1）排序算法：- 冒泡排序：通过相邻元素的比较和交换来实现排序。

- 快速排序：通过选择一个基准元素将数组分为两部分，一部分小于基准元素，一部分大于基准元素，再分别对两部分递归排序。

- 归并排序：将数组分为若干个子数组，分别对子数组进行排序，然后再依次合并得到有序数组。

这些排序算法在竞赛中经常用到，学生需要了解它们的原理和实现。

（2）查找算法：- 二分查找：针对有序数组，在每次查找过程中将查找范围缩小一半，直到找到目标元素或查找范围为空。

- 哈希表查找：通过将目标元素映射到一个固定位置来进行查找，具有较快的查找速度。

（3）图算法：- 图的遍历：深度优先遍历（DFS）和广度优先遍历（BFS）是图的常用遍历方法。

DFS通过递归或栈实现，BFS通过队列实现。

- 最短路径算法：迪杰斯特拉算法和弗洛伊德算法分别用于求解单源最短路径和多源最短路径问题。

3. 算法示例（1）示例一：冒泡排序给定一个整数数组，按照从小到大的顺序进行冒泡排序。

```cppvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);}}}}```（2）示例二：二分查找给定一个有序整数数组和一个目标值，使用二分查找算法返回目标值在数组中的下标（如果不存在则返回-1）。

第4讲稀疏矩阵压缩存储下——教学讲义“列序”递增转置法的思考：采用稀疏矩阵存储方法，可否降低时间复杂度？（提示：通过降低对稀疏矩阵三元组的扫描次数实现）方法二:“一次定位快速转置”法【算法思想】在方法一中,为了使转置后矩阵的三元组表B仍按“行序递增”存放,必须多次扫描被转置矩阵的三元组表A,以保证按被转置矩阵列序递增进行转置。

因此要通过双重循环来完成。

改善算法的时间性能,必须去掉双重循环,使整个转置过程通过一重循环来完成,即只对被转置矩阵的三元组表A扫描一次,就使A中所有非零元的三元组“一次定位”直接放到三元组表B的正确位置上。

为了能将被转置三元组表A中的元素一次定位到三元组表B的正确位置上,需要预先计算以下数据:( 1 )待转置矩阵三元组表A每一列中非零元素的总个数(即转置后矩阵三元组表B的每一行中非零元素的总个数)。

( 2 )待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置(即转置后矩阵每一行中第一个非零元素在三元组表B中的正确位置)。

为此,需要设两个数组分别为num[]和position[]。

其中num[ col]用来存放三元组表A第col列中非零元素总个数(三元组表B第col行中非零元素的总个数)。

position[ col]用来存放转置前三元组表A中第col列(转置后三元组表B中第col行)中第一个非零元素在三元组表B中的存储位置(下标值)。

num[ col]的计算方法:将三元组表A扫描一遍,对于其中列号为col的元素,给相应的num 数组中下标为col的元素加1 。

说明:在num[ col]的计算中,采用了“数组下标计数法”。

position[ col]的计算方法:①position[ 1 ]=1 ,表示三元组表A中,列值为1的第一个非零元素在三元组表B中的下标值;②position[ col]=position[ col-1 ]+num[ col-1 ]。

其中2 ≤col≤A.n。

信息压缩一、单元分析本单元是高一信息技术的第一单元，为后面信息技术的各模块奠定基础。

本单元注重从实际生活出发，理解信息的概念，掌握信息处理的方法，比如获取、存储、加工、表达和传输等（信息意识）；学习信息技术，认识信息技术的基础知识（信息意识）；通过活动开展的形式，了解信息技术的发展和最新技术（信息意识）；培养信息安全意识，能够自觉遵守相关法律法规与伦理道德规范（信息意识、信息社会责任）。

重点在于理解信息数字化的存储方式、编码方式以及压缩方式，培养学生的信息数字化意二、教材分析本节课的教学内容是“1.2信息与数字化”小节中的最后一节课，也是对之前学习内容——计算机中文字、声音、图像的编码方式的拓展与应用。

因为信息的压缩是从实际生活角度出发的一种信息编码方式，解决现实生活中的存储与传输问题。

然而，信息压缩的两种类型以及具体的压缩方式比较抽象，学生难以直观的感受。

因此，需要涉及相关的活动，让学生在实践过程中区分两种压缩类型并理解其中的压缩原理。

三、学情分析在此之前，学生学习并理解了文字、声音、图像的编码方式，为该节课的知识奠定了基础。

同时，大部分学生使用过压缩软件，对压缩软件的使用方法有一定的了解和掌握，但是学生并不理解压缩的原理以及两种主要的压缩方式，且此部分的知识相对抽象且专业，直接用教授法学生往往只能“知其然”而“不知其所以然”。

因此，可借助学生对压缩软件的掌握，设计两种压缩类型的实践活动，通过实践探索的方式让学生在观察中理解压缩原理，区分不同的压缩类型。

四、教学目标1.知识与技能（1）知道信息压缩的必要性，理解信息压缩的实质。

（2）区分无损压缩与有损压缩，知道两者之间的压缩原理和适用范围。

（3）选择合适的压缩工具对信息进行压缩。

2.过程与方法（1）通过不同内容的压缩活动，理解压缩的原理（2）通过文本和图片的压缩前后内容对比，理解无损与有损压缩的区别，以及适用范围3.情感态度与价值观（1）体会信息压缩在数据存储与存储中的实际意义（2）在实践探究中体验如何进行数据压缩，感悟信息压缩中的智慧。

芯衣州星海市涌泉学校§8图§图的根本概念图：图是数据构造G ＝(V ，E)，其中V 是结点的有穷非空集合，结点的偶对为边，E 是边的集合。

图中的结点又称为顶点。

无向图与有向图：假设图中每条边都是没有方向的，那么称为无向图；无向图中的边表示图中顶点的无序对，即〔u,v 〕和〔v,u 〕表示同一条边。

如图8.1.1V 〔G1〕＝{1,2,3,4,5}E 〔G1〕＝{(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}假设图中每条边都是有方向的，那么称其为有向图；有向图的边表示图中顶点的有序偶对；在有向图中，箭头表示边的方向。

如图8.1.2V 〔G2〕＝{1,2,3,4}E 〔G2〕＝{(1,2),(1,3),(2,4),(3,2),(4,3)}度、入度、出度：在一个有向图中，把以结点V 为终点的弧的数目称为V 的入度；把以结点V 为始点的弧的数目称为V 的出度。

入度和出度之和为该的结点的度。

如图8.1.2中，顶点V3的入度为2，出度为1，度为3。

途径、途径长度：图中从VS 到VP 的一条途径是指一串由顶点所成的连续序列VS ,Vi1,Vi2,……,Vin,VP，且其中(VP,Vi1),(Vi1,Vi2),……,(Vin,VP)都是E 上的边。

途径上所包含边的数目称为途径长度。

图8.1.2图8.1.1简单途径、简单回路：假设一条途径的顶点序列中，顶点不重复出现，那么称此途径为简单途径。

起点和终点一样的途径称为回路或者者环。

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。

连通图、强连通图：在无向图G1中，假设从顶点Vt 到Vs 有途径，那么称Vt 和Vs 是连通的。

假设对于图中任意两个顶点都是连通的，那么称G1为连通图。

在有向图G2中，假设每一对顶点Vi,Vj ，从Vi 到Vj 和从Vj 到Vi 都存在途径，那么称G2为强连通图。

子图、生成子图：在图G ＝〔V ，E 〕和图G'=〔V',E'〕中，假设V V'，E E'，那么称图G'是图G 的子图。

《数据压缩》教学设计方案（第一课时）一、教学目标1. 理解数据压缩的基本概念，掌握数据压缩的基本原理。

2. 学会使用常见的压缩和解压缩工具，了解不同的压缩格式。

3. 掌握一些常见的压缩算法，能够根据实际需求选择合适的压缩方法。

二、教学重难点1. 教学重点：数据压缩的基本原理和常见的压缩格式。

2. 教学难点：不同压缩算法的选择和应用，以及压缩和解压缩过程中的实际问题处理。

三、教学准备1. 准备相关的PPT课件，包含图片、视频和音频等素材。

2. 准备压缩和解压缩工具软件，如WinRAR、7-Zip等。

3. 准备一些常见的压缩文件，如ZIP、RAR等。

4. 准备一些实际案例，用于教学演示和实践操作。

四、教学过程：本节课的教学过程主要分为五个环节，分别是课前预习、新课导入、知识讲解、实践操作和课堂小结。

1. 课前预习：在课前布置预习任务，让学生自行了解数据压缩的基本概念和常见压缩算法。

可以通过布置作业或者在线平台进行预习。

2. 新课导入：首先通过一个小型互动游戏来展示数据压缩的实际应用，引发学生兴趣。

同时，简单介绍数据压缩的重要性，引入本节课的主题。

3. 知识讲解：通过图文并茂的方式详细介绍数据压缩的基本原理和方法，包括有损压缩和无损压缩两种类型。

同时，介绍常见的压缩算法如RAR、ZIP等。

4. 实践操作：组织学生进行实践操作，尝试使用常见的压缩软件进行文件压缩和解压操作，让学生亲身体验数据压缩的过程。

教师进行指导，解答学生操作过程中遇到的问题。

5. 课堂小结：对本节课所学的知识进行总结，强调重点和难点。

同时，鼓励学生分享自己的心得体会和收获，增强学习效果。

6. 课后拓展：布置课后作业，要求学生自行选择一种压缩算法进行实践操作，巩固所学知识。

同时，推荐一些相关的阅读材料和网站，鼓励学生继续深入学习数据压缩相关知识。

教学设计方案（第二课时）一、教学目标1. 理解数据压缩的基本概念和原理。

2. 掌握常见的数据压缩格式和算法。

§9 内部排序在《数据结构》里,排序一般分为：插入排序、交换排序、选择排序、归并排序和基数排序五种.写在前面的话：在看下面的各种算法之前,请先想想,如果给你一个无序的数列,你如何去排序？设计出你自己的算法.还有没有其它方法？相信自己的能力,排序算法是连小学生都可以设计出的！不希望以后听到这样的话：“排序的算法我忘了……”,排序算法不是背出来的！§9.1 插入排序(Insertion Sort)基本思想：每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序；直到待排序数据元素全部插入完为止.排序过程：【示例】： [初始关键字] [49] 38 65 97 76 13 27 49J=2(38) [38 49] 65 97 76 13 27 49J=3(65) [38 49 65] 97 76 13 27 49J=4(97) [38 49 65 97] 76 13 27 49J=5(76) [38 49 65 76 97] 13 27 49J=6(13) [13 38 49 65 76 97] 27 49J=7(27) [13 27 38 49 65 76 97] 49J=8(49) [13 27 38 49 49 65 76 97]§9.2选择排序基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完.排序过程：【示例】：初始关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13 [38 65 97 76 49 27 49]第二趟排序后 13 27 [65 97 76 49 38 49]第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [49 97 65 76]第五趟排序后 13 27 38 49 49 [97 97 76]第六趟排序后 13 27 38 49 49 76 [76 97]第七趟排序后 13 27 38 49 49 76 76 [97]最后排序结果 13 27 38 49 49 76 76 97§9.3 冒泡排序 (BubbleSort)基本思想：两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止.排序过程：设想被排序的数组R［1..N］垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止.【示例】：49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 3849 49 49 49 4976 97 6549 49 49 49 4913 76 9765 65 65 65 6527 27 7697 76 76 76 7649 49 4976 97 97 97 97【练习1】请分别用以上三种算法完成.同学们进行了身体素质测量,其中立位体前屈的成绩是以XX . XX cm来记录的,这个成绩不可能超过100,当有可能为负数（当指尖碰不到足时）,现有若干同学的成绩,请帮他们排序.输入：第一行正整数 n （有n个同学）第二行 n个成绩输出： n个成绩从大到小的排列§9.4 快速排序 (Quick Sort)基本思想：在当前无序区R[1..H]中任取一个数据元素作为比较的"基准元素",用此基准元素将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准元素则位于最终排序的位置I 上,即R[1..I-1]≤R[I]≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止. 排序过程：——将数列从小到大排序以第一个元素作为基准,设两指针i 和j,初始时i 指向区间第一个元素,j 指向最末一个元素；先移动j 指针,如果j 元素比i 元素大,j 指针前移,否则若j 小于i,则交换i 和j .交换i 和j 后,移动i 指针,如果i 元素比j 元素小,i 指针后移,否则若i 大于j,则交换i 和j .再移动j 指针,……,轮流移动i 指针和j 指针,直到j = i .将数列分成两部分,分别进行上述过程.【示例】： 初始关键字 ,j 指针左移 ［49 38 65 97 76 13 27 49］第一次交换后 ,j 指针不动,i 指针右移 ［27 38 65 97 76 13 49 49］第二次交换后 ,i 指针不动,j 指针左移 ［27 38 49 97 76 13 65 49］第三次交换后 ,j 指针不动,i 指针右移 ［27 38 13 97 76 49 65 49］第四次交换后,i 指针不动,j 指针左移 ［27 38 13 49 76 97 65 49］j 指针左移,遇i 指针 ［27 38 13 49 76 97 65 49］（递归过程）初始关键字 ［49 38 65 97 76 13 27 49］一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］三趟排序之后 13 27 38 49 49 ［65］76 97最后的排序结果 13 27 38 49 49 65 76 97i j i j i j j i i j j i参考程序：Procedure Parttion(L, H : Integer; var I : integer);{对无序区R[L,H]做划分,I返回出本次划分后已被定位的基准元素的位置} beginI:=L; J:=H; X:=R[I]; {初始化}RepeatWhile (R[J]>=X) And (I<J) Do J:=J–1;{J指针左移,查找第1个小于基准的元素} If I<J Then R[I]:=R[J]; {相当于交换R[I]和R[J]}While (R[I]<=R[J]) And (I<J) Do I:=I+1;{I指针右移,查找第1个大于基准的元素} If I<J Then R[J]:=R[I];Until I=J;R[I]:=X; {基准X已被最终定位}end; {Parttion}Procedure QuickSort(S,T:Integer); {对R[S..T]快速排序}beginIf S<T Then begin {当R[S..T]为空或只有一个元素是无需排序} Partion (S,T,I); {对R[S..T]做划分,返回I}QuickSort (S,I-1); {递归处理左区间R[S,I-1]}QuickSort (I+1,T); {递归处理右区间R[I+1,T]}end;end; {QuickSort}【练习2】请将给出的单词按字典排序. （利用字符串比较）输入：从文件word.in读入第一行正整数n以下n行每行一个单词输出：写入文件word.out中按字典排序,每行一个单词§9.5 堆排序(Heap Sort)基本思想：堆排序是一树形选择排序,在排序过程中,将R[1..N]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素.堆的定义:N个元素的序列K1, K2, K3, ……, Kn. 称为堆,当且仅当该序列满足特性： K i≤K2i K i≤K2i+1 (1≤ i≤ [N/2])堆实质上是满足如下性质的二叉树：1．是一棵完全二叉树；2．树中任一结点的值均大于等于（小于等于）其孩子结点的值；3．树根的值是最大的（最小的）例如序列10, 15, 56, 25, 30, 70就是一个堆,它对应的完全二叉树如下图所示.这种堆中根结点（称为堆顶）的关键字最小,我们把它称为小根堆.反之,若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆.这棵二叉树的存储,既可以用链表的方式存储,也可以用顺序表（一维数组S）的方式存储.采用顺序表的存储结构如上图所示,若某结点为S[ i ],则其左右子树分别为S[ 2i ]和S[ 2i+1 ].堆的调整：在介绍从一个无序序列建堆的方法前,我们先看如何在一个已建成的堆中,若在输出堆顶的最小值之后,调整剩余的n-1个元素的序列,重又建成一个一个堆.设图9－1为一个几建成的小根堆.图9－1输出堆顶元素后,以堆中最后元素代替之,如图9－2 (a).此时根结点的左右子树均为堆,则仅需自上而下进行调整即可.首先以新堆顶元素与其左右子树根结点的值比较,由于右子树根结点的值小于左子树根结点的值,且小于根结点的值,则将根结点的值69与右子树根结点的值11交换, 如图9－2(b).由于69替代了11之后破坏了右子树的“堆”,需进行和上述相同的调整,直至叶子结点.调整后的状态如图9－2 (c).这个过程可称为“筛”.( a ) ( b ) ( c )图9－2 调制建新堆的过程输出堆顶元素后的调整过程如下：procedure sift ( var S : array [ 1..n ] of integer ; k , m : integer );{ 假设S[k+1. . m]为小根堆,调整S[k]使整个序列S[k . . m]满足堆的性质 }begini:=k; j:=2*i; x:=S[k]; finish:=false;while (j<=m) and (finish=false) do beginif (j<m) and (S[ j ]>S[ j+1 ]) then j:=j+1;{若存在右子树,且右子树根结点的值更小,则沿右分支调整}if x<=S[ j ] then finish:=trueelse beginS[ i ] := S[ j ]; i :=j ; j :=2*i ;end;end; {whie}S[ i ]:=x;end;排序过程：从一个无序序列建堆的过程就是一个反复调整的过程.将无序数列看成一棵完全二叉树,从最后一个非叶子结点i开始进行调整以该结点为根的子树,然后在调整以i-1为根的子树,……这样,在原序列的尾部形成有序区并逐步向前扩大到整个序列.【例】：对无序序列42,13,91,23,24,16,05,88建立大跟堆【练习】对输入的无序序列进行堆排序.输入：第一行： n第二行： n个整数输出：将n个整数按从小到大排序输出§9.6 排序算法的比较和选择1. 选取排序方法需要考虑的因素：(1) 待排序的元素数目n；(2) 元素本身信息量的大小；(3) 关键字的结构及其分布情况；(4) 语言工具的条件,辅助空间的大小等.2. 小结：(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序.由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好.(2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜.(3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序. 快速排序是目前基于比较的内部排序法中被认为是最好的方法.(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明：当文件的n个关键字随机分布时,任何借助于"比较"的排序算法,至少需要O(nlog2n)的时间.(5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构.。