内部排序算法的性能分析

❶ 常用的数据排序算法有哪些,各有什么特点举例结合一种排序算法并应用数组进行数据排序。

排序简介
排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章介绍常用的如下排序方法，并对它们进行分析和比较。

1、插入排序（直接插入排序、折半插入排序、希尔排序）；
2、交换排序（起泡排序、快速排序）；
3、选择排序（直接选择排序、堆排序）；
4、归并排序；
5、基数排序；

学习重点
1、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；
2、掌握插入排序(直接插入排序、折半插入排序、希尔排序)、交换排序（起泡排序、快速排序）、选择排序（直接选择排序、堆排序）、二路归并排序的方法及其性能分析方法；
3、了解基数排序方法及其性能分析方法。

排序（sort）或分类

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序对象--文件
被排序的对象--文件由一组记录组成。
记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。
注意：
在不易产生混淆时，将关键字项简称为关键字。

2．排序运算的依据--关键字
用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。

排序的稳定性

当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

排序方法的分类

1．按是否涉及数据的内、外存交换分
在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
注意：
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

2．按策略划分内部排序方法
可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

排序算法分析

1．排序算法的基本操作
大多数排序算法都有两个基本的操作：
(1) 比较两个关键字的大小；
(2) 改变指向记录的指针或移动记录本身。
注意：
第(2)种基本操作的实现依赖于待排序记录的存储方式。

2．待排文件的常用存储方式
（1） 以顺序表(或直接用向量)作为存储结构
排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）

（2） 以链表作为存储结构
排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；

（3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)
排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。

3．排序算法性能评价
（1） 评价排序算法好坏的标准
评价排序算法好坏的标准主要有两条：
① 执行时间和所需的辅助空间
② 算法本身的复杂程度

（2） 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。
非就地排序一般要求的辅助空间为O(n)。

（3） 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

文件的顺序存储结构表示

#define n l00 //假设的文件长度，即待排序的记录数目
typedef int KeyType； //假设的关键字类型
typedef struct{ //记录类型
KeyType key； //关键字项
InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义
}RecType；
typedef RecType SeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵
注意：
若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。
【例】关键字为字符串时，可定义宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，则定义重载的算符"<"更为方便。

按平均时间将排序分为四类：

（1）平方阶(O(n2))排序
一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序
如快速、堆和归并排序；

（3）O(n1+￡)阶排序
￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序
如桶、箱和基数排序。

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
①待排序的记录数目n；
②记录的大小(规模)；
③关键字的结构及其初始状态；
④对稳定性的要求；
⑤语言工具的条件；
⑥存储结构；
⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。
当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。
箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于"比较"的方法来排序。
若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最终结果是：
R[0].key≤R[1].key≤…≤R[n-1].key
则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。

❷ 我想具体了解一下中国传媒大学数字媒体艺术专业网络多媒体方向和数字媒体理论与实践方向的区别

同学你查错了吧？

工程硕士
计算机技术专业分成四个方向：

01网络多媒体技术

02传媒信息安全

03数字娱乐与动画技术

04游戏制作

你报考的是网络多媒体技术对吗？那你初试要考四门课程，分别是：

①政治

②俄、日、英语（二）选一

③数学（二）

④程序设计

PS附上
中国传媒大学专业学位研究生入学考试
《程序设计》考试大纲

一、考试的总体要求
本考试大纲适用于报考中国传媒大学工程硕士的计算机技术领域全日制专业学位研究生入学考试。《程序设计》是计算机科学与技术及相关学科的重要基础，主要考核内容包括基于数据结构的程序设计和基于操作系统的程序设计两大部分。要求考生对计算机科学与技术学科的基本知识、基本理论、基本方法有较深入、系统的理解，掌握各种数据结构的定义和实现算法，掌握操作系统所涉及的关键内容，对C语言的基本知识有较深入的了解，掌握程序设计的基本方法，并具有综合运用所学知识分析问题和解决问题的能力。

二、考试的内容
（一） 程序设计基础
1、C语言的基本数据类型、各种运算符和表达式、基本控制结构。
2、数组的定义、数组元素的引用、数组的初始化，掌握与字符串相关的库函数。
3、函数的定义语法，函数调用中参数的传递机制；局部变量和全局变量的有效范围。
4、结构体类型变量的定义、结构体变量的引用、结构体变量的初始化方法，结构体数组的定义、初始化和结构体数组的应用，共同体变量的定义和使用方法。
5、地址和指针的基本概念，如何使用指针来处理数组、字符串以及结构体，函数指针的基本概念以及使用。
6、FILE的定义以及对文件进行的各种操作的库函数。
（二） 线性表
1、 线性表的定义和基本操作
2、 线性表的实现
（1）顺序存储结构：实现顺序表的查找、插入、删除、合并、分解等操作的程序设计。
（2）链式存储结构：实现单链表、循环链表、双向链表、双向循环链表的生成、查找、插入、删除、遍历以及链表的分解和归并等操作的程序设计。
3、线性表的应用：从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点，即其各自适用的场合。运用顺序表和链表的特点解决复杂的应用问题。
（三）栈、队列和数组
1、栈和队列的基本概念
2、栈和队列的顺序存储结构和链式存储结构及应用
（1）栈与递归的关系。
用递归解决的几类问题：问题的定义是递归的；数据结构是递归的；以及问题的解法是递归的。
典型递归问题的算法以及如何将递归算法转换为非递归算法。
（2）在程序设计中，常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据。在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法、图的深度优先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。
3、特殊矩阵的压缩存储：对称矩阵、对角矩阵、三角矩阵在压缩存储时的下标变换公式。
（四）树与二叉树
1、二叉树
（1）二叉树的定义及其主要特征：二叉树的五个性质及证明方法，并把这种方法推广到K叉树。
（2）二叉树的顺序存储结构和链式存储结构：二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合。
（3）二叉树的遍历
二叉树的先序，中序和后序遍历算法以及按层次遍历。遍历是基础，在基本遍历算法的基础上实现二叉树的其它算法。
（4）线索二叉树的基本概念和构造
线索化算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点）。
（5）二叉排序树
二叉排序树的建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树的算法。
2、树、森林
（1）树的概念和存储结构
（2）森林与二叉树的转换
（3）树和森林的遍历
树与森林的遍历，有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。
（五）图
1、图的概念、存储及基本操作
（1）邻接矩阵法
（2）邻接表法
2、图的遍历
深度优先搜索和广度优先搜索是图的两种基本的遍历算法以及基于这两种基本的遍历算法的程序设计。
3、图的基本应用及其复杂度分析
（1）最小（代价）生成树
（2）最短路径
（3）拓扑排序
（4）关键路径
（六）查找
1、查找的基本概念
2、顺序查找法、折半查找法
3、散列（Hash）表及其查找
4、查找算法的分析及应用
（七）内部排序
1、 排序的基本概念
2、插入排序
3、冒泡排序
4、简单选择排序
5、希尔排序
6、快速排序
7、堆排序
8、二路归并排序
9、各种内部排序算法的比较
各种排序方法的算法思想及程序设计、手工模拟排序过程、性能分析（包括时间复杂度、空间复杂度、稳定性）。
10、内部排序算法的应用
（八）进程管理
1、进程概念、进程的状态与转换
2、进程同步
（1）进程同步的基本概念
（2）实现临界区互斥的基本方法
（3）信号量：PV原语的含义
（4）经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题。
重点掌握 PV 操作的概念、流程，以及 PV 操作在同步与互斥问题中的应用。
3、死锁的概念及处理策略

三、考试的基本题型
本试卷满分为150分，其中：基于数据结构的程序设计 120分、基于操作系统的程序设计 30分。
主要题型有：选择题、综合应用题、程序设计题等。

四、考试的形式及时间
笔试，不需要任何辅助工具。考试时间为三小时。
希望采纳

❸ 急求排序算法性能分析程序

排序算法全集【附C++代码】

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。

对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N＊N)（因为没有使用word，所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。

现在，让我们开始吧：

一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。

1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include ＜iostream.h＞

void BubbleSort(int＊ pData，int Count)
{
int iTemp;
for(int i＝1;i＜Count;i++)
{
for(int j＝Count-1;j＞＝i;j--)
{
if(pData[j]＜pData[j-1])
{
iTemp ＝ pData[j-1];
pData[j-1] ＝ pData[j];
pData[j] ＝ iTemp;
}
}
}
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
BubbleSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞10，9，7，8-＞10，7，9，8-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，10，8，9-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次

其他：
第一轮：8，10，7，9-＞8，10，7，9-＞8，7，10，9-＞7，8，10，9(交换2次)
第二轮：7，8，10，9-＞7，8，10，9-＞7，8，10，9(交换0次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2＊(n-1)＊n。
现在注意，我们给出O方法的定义：

若存在一常量K和起点n0，使当n＞＝n0时，有f(n)＜＝K＊g(n)，则f(n) ＝ O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）

现在我们来看1/2＊(n-1)＊n，当K＝1/2，n0＝1，g(n)＝n＊n时，1/2＊(n-1)＊n＜＝1/2＊n＊n＝K＊g(n)。所以f(n)
＝O(g(n))＝O(n＊n)。所以我们程序循环的复杂度为O(n＊n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），
复杂度为O(n＊n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因，我们通常都是通过循环次数来对比算法。

2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include ＜iostream.h＞
void ExchangeSort(int＊ pData，int Count)
{
int iTemp;
for(int i＝0;i＜Count-1;i++)
{
for(int j＝i+1;j＜Count;j++)
{
if(pData[j]＜pData)
{
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
}
}
}
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
ExchangeSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7-＞8，10，9，7-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，9，10，8-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次

其他：
第一轮：8，10，7，9-＞8，10，7，9-＞7，10，8，9-＞7，10，8，9(交换1次)
第二轮：7，10，8，9-＞7，8，10，9-＞7，8，10，9(交换1次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次

从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2＊(n-1)＊n，所以算法的复杂度仍然是O(n＊n)。由于我们无法给出所有的情况，所以
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。

3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中
选择最小的与第二个交换，这样往复下去。
#include ＜iostream.h＞
void SelectSort(int＊ pData，int Count)
{
int iTemp;
int iPos;
for(int i＝0;i＜Count-1;i++)
{
iTemp ＝ pData;
iPos ＝ i;
for(int j＝i+1;j＜Count;j++)
{
if(pData[j]＜iTemp)
{
iTemp ＝ pData[j];
iPos ＝ j;
}
}
pData[iPos] ＝ pData;
pData ＝ iTemp;
}
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
SelectSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞(iTemp＝9)10，9，8，7-＞(iTemp＝8)10，9，8，7-＞(iTemp＝7)7，9，8，10(交换1次)
第二轮：7，9，8，10-＞7，9，8，10(iTemp＝8)-＞(iTemp＝8)7，8，9，10(交换1次)
第一轮：7，8，9，10-＞(iTemp＝9)7，8，9，10(交换0次)
循环次数：6次
交换次数：2次

其他：
第一轮：8，10，7，9-＞(iTemp＝8)8，10，7，9-＞(iTemp＝7)8，10，7，9-＞(iTemp＝7)7，10，8，9(交换1次)
第二轮：7，10，8，9-＞(iTemp＝8)7，10，8，9-＞(iTemp＝8)7，8，10，9(交换1次)
第一轮：7，8，10，9-＞(iTemp＝9)7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2＊(n-1)＊n。所以算法复杂度为O(n＊n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)＜＝n
所以我们有f(n)＝O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include ＜iostream.h＞
void InsertSort(int＊ pData，int Count)
{
int iTemp;
int iPos;
for(int i＝1;i＜Count;i++)
{
iTemp ＝ pData;
iPos ＝ i-1;
while((iPos＞＝0) && (iTemp＜pData[iPos]))
{
pData[iPos+1] ＝ pData[iPos];
iPos--;
}
pData[iPos+1] ＝ iTemp;
}
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
InsertSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}

倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7(交换1次)(循环1次)
第二轮：9，10，8，7-＞8，9，10，7(交换1次)(循环2次)
第一轮：8，9，10，7-＞7，8，9，10(交换1次)(循环3次)
循环次数：6次
交换次数：3次

其他：
第一轮：8，10，7，9-＞8，10，7，9(交换0次)(循环1次)
第二轮：8，10，7，9-＞7，8，10，9(交换1次)(循环2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)(循环1次)
循环次数：4次
交换次数：2次

上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)＜＝
1/2＊n＊(n-1)＜＝1/2＊n＊n。所以其复杂度仍为O(n＊n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘＝’操作。正常的一次交换我们需要三次‘＝’
而这里显然多了一些，所以我们浪费了时间。

最终，我个人认为，在简单排序算法中，选择法是最好的。

二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。

1.快速排序：
#include ＜iostream.h＞

void run(int＊ pData，int left，int right)
{
int i，j;
int middle，iTemp;
i ＝ left;
j ＝ right;
middle ＝ pData[(left+right)/2]; //求中间值
do{
while((pData＜middle) && (i＜right))//从左扫描大于中值的数
i++;
while((pData[j]＞middle) && (j＞left))//从右扫描大于中值的数
j--;
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
i++;
j--;
}
}while(i＜＝j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j);
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right);
}

void QuickSort(int＊ pData，int Count)
{
run(pData，0，Count-1);
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
QuickSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}

这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k＝log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2＊(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n＊(n/n) ＝ n+n+n+...+n＝k＊n＝log2(n)＊n
所以算法复杂度为O(log2(n)＊n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)＊n)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。

三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include ＜iostream.h＞
void Bubble2Sort(int＊ pData，int Count)
{
int iTemp;
int left ＝ 1;
int right ＝Count -1;
int t;
do
{
//正向的部分
for(int i＝right;i＞＝left;i--)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData;
pData ＝ pData[i-1];
pData[i-1] ＝ iTemp;
t ＝ i;
}
}
left ＝ t+1;

//反向的部分
for(i＝left;i＜right+1;i++)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData;
pData ＝ pData[i-1];
pData[i-1] ＝ iTemp;
t ＝ i;
}
}
right ＝ t-1;
}while(left＜＝right);
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
Bubble2Sort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}

2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include ＜iostream.h＞
void ShellSort(int＊ pData，int Count)
{
int step[4];
step[0] ＝ 9;
step[1] ＝ 5;
step[2] ＝ 3;
step[3] ＝ 1;

int iTemp;
int k，s，w;
for(int i＝0;i＜4;i++)
{
k ＝ step;
s ＝ -k;
for(int j＝k;j＜Count;j++)
{
iTemp ＝ pData[j];
w ＝ j-k;//求上step个元素的下标
if(s ＝＝0)
{
s ＝ -k;
s++;
pData[s] ＝ iTemp;
}
while((iTemp＜pData[w]) && (w＞＝0) && (w＜＝Count))
{
pData[w+k] ＝ pData[w];
w ＝ w-k;
}
pData[w+k] ＝ iTemp;
}
}
}

void main()
{
int data[] ＝ {10，9，8，7，6，5，4，3，2，1，-10，-1};
ShellSort(data，12);
for (int i＝0;i＜12;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
呵呵，程序看起来有些头疼。不过也不是很难，把s＝＝0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。

四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char＊ strData);
CMyData();
virtual ~CMyData();

int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char＊ GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator ＝(CMyData &SrcData);
bool operator ＜(CMyData& data );
bool operator ＞(CMyData& data );

private:
char＊ m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////

MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}

CMyData::~CMyData()
{
if(m_strDatamember !＝ NULL)
delete[] m_strDatamember;
m_strDatamember ＝ NULL;
}

CMyData::CMyData(int Index，char＊ strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize ＝ strlen(strData);
m_strDatamember ＝ new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}

CMyData& CMyData::operator ＝(CMyData &SrcData)
{
m_iIndex ＝ SrcData.m_iIndex;
m_iDataSize ＝ SrcData.GetDataSize();
m_strDatamember ＝ new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return ＊this;
}

bool CMyData::operator ＜(CMyData& data )
{
return m_iIndex＜data.m_iIndex;
}

bool CMyData::operator ＞(CMyData& data )
{
return m_iIndex＞data.m_iIndex;
}
///////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////
//主程序部分
#include ＜iostream.h＞
#include ”MyData.h”

template ＜class T＞
void run(T＊ pData，int left，int right)
{
int i，j;
T middle，iTemp;
i ＝ left;
j ＝ right;
//下面的比较都调用我们重载的操作符函数
middle ＝ pData[(left+right)/2]; //求中间值
do{
while((pData＜middle) && (i＜right))//从左扫描大于中值的数
i++;
while((pData[j]＞middle) && (j＞left))//从右扫描大于中值的数
j--;
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
i++;
j--;
}
}while(i＜＝j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j);
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right);
}

template ＜class T＞
void QuickSort(T＊ pData，int Count)
{
run(pData，0，Count-1);
}

void main()
{
CMyData data[] ＝ {
CMyData(8，”xulion”)，
CMyData(7，”sanzoo”)，
CMyData(6，”wangjun”)，
CMyData(5，”VCKBASE”)，
CMyData(4，”jacky2000”)，
CMyData(3，”cwally”)，
CMyData(2，”VCUSER”)，
CMyData(1，”isdong”)
};
QuickSort(data，8);
for (int i＝0;i＜8;i++)
cout＜＜data.m_iIndex＜＜” ”＜＜data.GetData()＜＜”＼n”;
cout＜＜”＼n”;

❹ 几种常见的排序算法的实现与性能分析(数据结构)的报告

可参考 ：
http://blog.csdn.net/stubbornpotatoes/article/details/7513509

http://hi..com/shismbwb/item/404c94898cfd2855850fab24

❺ 选择排序，快速排序，冒泡排序，堆排序，插入排序，基排序的程序的运行速度

分析如下：
冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。

冒泡排序2：它是冒泡排序的改良（一次下沉再一次上浮），最优情况和最坏情况与冒泡排序差不多，但是一般情况下它要好过冒泡排序，它一次下沉，再一次上浮，这样避免了因一个数的逆序，而造成巨大的比较。如（2,3,4,…,n-1,n,1），用冒泡排序需要n(n-1)/2次比较，而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次，第一轮1将上移一位，第二轮1将移到首位，第三轮将发现无数据交换，序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法，只适合于数据基本有序的排序。

快速排序：它同样是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为O(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。

直接选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。

堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

直接插入排序：简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

希尔排序：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为1，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。

归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

按平均时间将排序分为类：
(1) 平方阶(O(n2))排序
各类简单排序，例如直接插入、直接选择和冒泡排序；
(2) 线性对数阶(O(nlog2n))排序
如快速排序、堆排序和归并排序；
(3) O(n1+§))排序
§是介于0和1之间的常数。希尔排序便是一种；
(4) 线性阶(O(n))排序
本程序中的基数排序，此外还有桶、箱排序。

排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
事实上各种排序方法个有优缺点适用于不同的场合：
排序（Sorting)
插入排序（insertion sort）:直接插入排序 希尔排序（shell's sort）(缩小增量排序Diminishing increment sort)
交换排序：冒泡排序（bubble sort）快速排序（quick sort）
选择排序:直接选择排序（straight selection sort），堆排序；
归并排序（merge sort）：
分配排序：箱排序（Bin sort）,基数排序（radix sort）
更多的自己研究一下。

排序方法的选取主要考虑算法的性能与资源占用。也就是速度和占用的存储空间。
希望对你有所帮助！

❻ 用c语言完成：1.哈夫曼编码/译码器2.内部排序算法的性能分析

我把网上的程序修改了一下，并整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;

typedef struct
{
int weight;//结点权值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;

typedef char** HUFFMANCODE;//动态分配数组存储哈夫曼编码表

typedef struct
{
int key; /*关键字*/
}RecordNode; /*排序节点的类型*/

typedef struct
{
RecordNode *record;
int n; /*排序对象的大小*/
}SortObject; //待排序序列

HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼树中各结点的数据，没初始值的赋值为0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循环从森林中选择最小的两棵树组建成一颗新树
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}

void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;++i)//逐个字符求哈夫曼编码
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*从叶子结点到根结点求逆向编码*/
if(ht[father].lchild==child)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char*)malloc((n-start)*sizeof(char));//为i个字符编码分配空间
strcpy(hc[i],&cd[start]);//从cd复制哈夫曼编码串到hc
}
free(cd);//释放工作空间
for(i=1;i<=n;++i)
{
printf("\n%c的编码:",str[i]);
printf("%s\n",hc[i]);
}
}

void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);

printf("\n请输入字符(一次性连续输入所求的字符):");/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n请输入%c的权值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;

ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);

}

void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}

void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}

void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}

void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}

void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}

void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("请输入待排序的随机数个数：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比较如下");
for(j=0;j<5;j++)
{
printf("\n\n对%d个数进行排序，结果为：\n",k);
printf("1.插入排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.选择排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希尔排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回车继续\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n对%d个随机数进行5次排序，平均比较次数和平均移动次数为：\n",k);
printf("1.插入排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.选择排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希尔排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}

void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}

void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}

main()
{
int i,j,k;
while(1)
{
printf("请选择要运行的功能：\n");
printf("1.哈夫曼编码译码器\n");
printf("2.内部排序性能分析\n");
printf("3.退出该程序\n\n");
printf("你的选择为：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}

❼ C++中排序的算法分析(文字分析)

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。

现在，让我们开始吧：

一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n
所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。

二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step个元素的下标
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。

四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index,char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
int i,j;
T middle,iTemp;
i = left;
j = right;
//下面的比较都调用我们重载的操作符函数
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
template <class T>
void QuickSort(T* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
CMyData data[] = {
CMyData(8,"xulion"),
CMyData(7,"sanzoo"),
CMyData(6,"wangjun"),
CMyData(5,"VCKBASE"),
CMyData(4,"jacky2000"),
CMyData(3,"cwally"),
CMyData(2,"VCUSER"),
CMyData(1,"isdong")
};
QuickSort(data,8);
for (int i=0;i<8;i++)
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}

❽ 求助期末数据结构课设，

什么时候截止？
我有《内排序算法分析》的C++代码和分析报告，分析九个内排序算法的，当时大一写的。你要的话，我去取。最好宽限几天，这几天比较忙。呵呵，其实吧，这东西还是在参考别人的基础上自己写好 ^_^
如果着急的话，我给你个C++的停车场的程序。这个问题简单一点，代码比较少，虽然可以实现全部功能，但代码量可能达不到要求。。。
给个邮箱，我把工程文件全发给你，如果你需要的话。

❾ 急！ 内部堆排序算法的实现！！！包括大根堆的实现和小根堆的实现！！！要完整的！！！

1、 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意：
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。

4、堆排序与直接插入排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。

5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

（1）用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。

（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

（3）堆排序的算法：
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i；
BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i>1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换
Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
} //endfor
} //HeapSort

（4） BuildHeap和Heapify函数的实现
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。
① Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。
具体的算法

②BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。
具体算法。

5、大根堆排序实例
对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见。

6、 算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。

❿ 我是湖南邵阳职业技术学院的专科学生，学的是计算机科学与技术，然后明年升考吉首大学的 计算机科学与应用

《微机原理》考试大纲
第一章 概述
1.计算机中的数和编码系统
（1）理解计算机中的数制的概念，会应用；（2）掌握二进制编码的方法；
（3）掌握二进制运算的规则；（4）掌握带符号数的表示方法及表示范围；
2.了解计算机的硬件和软件的划分及功能
3.微型计算机的结构
（1）了解微型计算机的外部结构；
（2）了解微型计算机的内部结构；
4. Intel 8088的结构
（1）掌握8088的寄存器结构；（2）掌握8088的功能结构；
（3）掌握存储器组织；
第二章 8088的指令系统
1.掌握8088的寻址方式
（1）立即寻址（2）直接寻址（3）寄存器寻址（4）寄存器间接寻址（5）变址寻址（6）基址加变址的寻址方式
2.掌握8088标志寄存器中的9个标志位
3.掌握8088的指令系统
（1）数据传送指令（2）算术运算指令（3）逻辑运算指令
第三章 汇编语言程序设计
1.正确掌握汇编语言的格式；
2.了解语句行的构成，会应用；
3.理解指示性语句，会正确使用；
4.掌握基本的汇编语言程序设计
（1）循环程序设计（2）参数传送技术（3）子程序设计
第四章 8088的总线操作和时序
1.基本概念
（1）正确理解指令周期、总线周期和T状态的概念；
（2）掌握CPU的时序和存储器以及外设的时序概念；
2. 8088的总线
（1）掌握8088的两种组态的区别；
3.掌握8088典型时序
（1）存储器读周期（2）存储器写周期（3）中断响应周期
4.最大组态下的8088时序与最小组态的8088时序区别
5.计数器和定时器电路Intel 8253-PIT
（1）了解8253-PIT芯片的主要功能及内部结构；（2）会写8253-PIT的控制字；（3）掌握8253-PIT的工作方式；（4）掌握8253-PIT编程步骤；
第五章 半导体存储器
1.解半导体存储器的分类
2.读写存储器RAM
（1）了解基本存储电路（2）理解RAM的结构(3)掌握RAM与CPU的连接要考虑的主要问题；会根据连接图写出寻址范围
第六章 输入和输出
1.了解输入输出的寻址方式
2.掌握CPU与外设数据传送的方式
（1）无条件传送方式（2）查询传送方式（3）中断传送方式（4）直接数据通道传送（DMA）
第七章 中断
1.中断的引入
（1）理解为什么要用中断（2）掌握中断系统的功能
2.最简单的中断情况
（1）掌握CPU响应中断的条件（2）掌握CPU对中断的响应
4. 8088的中断方式
（1）掌握两条外部中断请求线及使用
（2）掌握内部中断类型号
（3）掌握8088中断优先权次序
（4）掌握8088中断向量表的大小、中断向量的个数及中断入口地址的求法
（5）掌握8088中的中断响应和处理过程
第八章 并行接口片子
1.了解可编程的输入输出接口芯片8255A-5的功能和结构
2.掌握8255A各端口的工作方式及功能

教材：《微型计算机系统原理及应用》 周明德, 清华大学出版社
参考书：
1、《微型计算机原理与接口技术》李兰友等编，南开大学出版社，2001年版�
2、《计算机电路基础》王金刚编，南开大学出版社，2001年版�

考题类型及分数分布：
本课程考试试题类型填空题、分析程序题、简答题、综合应用题四种形式，其中填空题20分、分析程序题15分、简答题20分，综合应用题20分
《数据结构》考试大纲
第一章 绪论
一、学习目的和要求
本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。
本章要了解数据的抽象类型定义。理解算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法。
二、课程内容
第一节 什么是数据结构
第二节 基本概念和术语
第三节 抽象数据类型的表示与实现
第四节 算法和算法分析
三、考核知识点
1、 合适的数据结构在解决实际应用问题中的关键性；以及学习《数据结构》的意义。
2、 数据、数据元素、数据项、数据结构等基本概念。
3、 数据结构的四种逻辑结构和两种存储结构表示方法。
4、 抽象数据类型的表示和实现
5、 算法的五个特点。
6、 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。
7、 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。
四、考核要求
1. 识记
1) 数据结构的基本概念和术语。
2) 合适的数据结构在解决实际应用问题中的关键性，以及学习《数据结构》的意义。
3) 数据结构的四种逻辑结构和两种存储结构表示方法。
2. 领会
1) 算法的描述和分析：算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度
第二章 线性表
一、学习目的和要求
本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。
本章重点是熟练掌握顺序表和单链表上实现的各种基本运算及相关的时间性能分析，难点是在循环链表和双向链表存储结构中各种基本运算的实现。
二、课程内容
第一节 线性表的类型定义
第二节 线性表的顺序表示和实现
第三节 线性表的链式表示和实现
三、考核知识点
1、 线性表的类型定义
2、 顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析
3、 链式表示和实现，单链表、双链表、循环链表链接方式上的区别；
4、 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。
5、 循环链表上尾指针取代头指针的作用
6、 单循环链表上的算法与单链表上相应算法的异同点。
7、 双向链表的定义和相关算法。
8、 顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。
四、考核要求
1. 识记
1) 线性表的逻辑结构特征；
2) 线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。
2. 领会
1) 顺序表和链表的比较，各自的优缺点。
2) 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
3. 综合应用
1) 顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析。
2) 单链表、双链表、循环链表链接方式上的区别；
3) 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。
4) 循环链表上尾指针取代头指针的作用，
5) 单循环链表上的算法与单链表上相应算法的异同点。
6) 双链表的定义和相关算法。
第三章 栈和队列
一、学习目的和要求
本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列。
本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理
二、课程内容
第一节 栈
第二节 栈的应用举例
第四节 队列
三、考核知识点
1、 栈的抽象数据类型的定义
2、 栈的表示和实现
3、 栈的简单应用
4、 抽象数据类型队列的定义
5、 队列的链式表示和实现
6、 队列的顺序表示和实现
四、考核要求
1. 领会
1) 栈和队列的特点，栈和队列各自的使用情况。
2. 综合应用
1) 栈的逻辑结构特点，栈与线性表的异同。
2) 顺序栈和链栈上实现进栈、退栈等基本算法。
3) 利用栈解决简单的实际问题。
4) 队列逻辑结构特点，队列与线性表的异同。
5) 顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。
6) 顺序队列的“假溢出”现象及其采用循环队列进行解决的方法。
第四章 串
一、学习目的和要求
本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法，这也是难点。
二、课程内容
第一节 串类型的定义
第二节 串的表示和实现
三、考核知识点
1、 串的定义、空串、空格串、子串、主串、串相等。
2、 串的基本操作。
3、 串的顺序存储结构及在顺序存储结构下基本操作的实现。
4、 串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。
5、 串的链式存储表示
四、考核要求
1. 领会
1) 串的有关概念及其基本运算
2. 简单应用
1) 串的三种存储表示
2) 使用串解决与串相关的简单的应用问题
第五章 数组和广义表
一、学习目的和要求
本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求熟悉这些内容。
本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头表尾的运算，难点是稀疏矩阵的压缩存储表示下转置运算。
二、课程内容
第一节 数组的定义
第二节 数组的顺序表示和实现
第三节 矩阵的压缩存储
第四节 广义表的定义
第五节 广义表的存储结构
三、考核知识点
1、 数组的顺序存储结构。
2、 二维数组的按行存储及按列存储和计算数组元素的地址计算公式。
3、 矩阵的压缩存储、特殊矩阵的表示。
4、 广义表的定义和操作(HEAD和TAIL)
5、 广义表的2种存储结构
四、考核要求
1. 领会
1) 多维数组的逻辑结构特征
2) 多维数组的顺序存储结构及其地址计算方式
3) 特殊矩阵和稀疏矩阵的概念
4) 稀疏矩阵的压缩存储方式——三元组表
5) 稀疏矩阵的两种转置运算算法
6) 广义表的概念、广义表和线性表的联系
7) 广义表表头和表尾的概念及广义表两个特殊的基本运算，取表头和取表尾。
8) 广义表的两种存储结构
第六章 树和二叉树
一、学习目的和要求
本章的目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。本章重点是掌握二叉树及其二叉树的遍历。难点是掌握与树有关的简单应用。
二、课程内容
第一节 树的定义和基本术语
第二节 二叉树
第三节 遍历二叉树和线索二叉树
第四节 树和森林
第六节 赫夫曼树及其应用
三、考核知识点
1、 树的定义和术语。
2、 二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构——顺序表示法和链表表示法。
3、 二叉树的三种遍历方法及相应的递归算法。
4、 二叉树线索化的目的及其实质。
5、 树的存储表示法——孩子表示法、双亲表示法、孩子兄弟表示法。
6、 树和森林及二叉树的转换方法。
7、 树和森林的遍历
8、 树的路径长度、树的带权路径长度、赫夫曼树（最优二叉树）的构造方法。
9、 赫夫曼编码方法
四、考核要求
1. 领会
1) 树的逻辑结构特征
2) 树的不同表示方法
3) 树的常用术语及含义
4) 二叉树线索化的目的及实质
5) 在中序线索树中查找给定结点的中序前驱和中序后继的方法
6) 树和森林与二叉树之间的转换方法
7) 树的各种存储结构及其特点
8) 树的遍历方法
2. 简单应用
1) 二叉树的定义及树与二叉树的差别
2) 二叉树的性质，了解相应的证明方法
3) 二叉树的两种存储结构、特点及适用范围
4) 最优二叉树和前缀编码的概念及特点
5) 赫夫曼算法的思想
6) 根据给定的叶结点及其权值构造出相应的最优二叉树
7) 根据最优二叉树构造对应的赫夫曼编码
3. 综合应用
1) 二叉树的三种遍历算法，理解其执行过程
2) 根据不同的遍历方法，应能得出其相应的结点访问次序
3) 以遍历算法为基础，设计有关算法解决简单的应用问题
第七章 图
一、学习目的和要求
本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。本章重点是掌握图的两种存储结构上实现的遍历算法。难点是图的应用算法：最小生成树，求最短路径以及拓扑排序。只要求掌握这些算法的基本思想及时间性能。
二、课程内容
第一节 图的定义和术语
第二节 图的存储结构
第三节 图的遍历
第四节 图的连通性问题
第五节 有向无环图及其应用
第六节 最短路径
三、考核知识点
1、 图的逻辑结构特征
2、 图的常用术语及含义
3、 图的邻接矩阵表示法存储结构
4、 邻接表表示法
5、 图的深度优先遍历
6、 图的广度优先遍历
7、 生成树和最小生成树
8、 构造最小生成树的PRIM算法思想和时间性能
9、 构造最小生成树的Kruskal算法思想和时间性能
10、 拓扑排序
11、 关键路径
12、 关于最短路径的算法——Dijkstra算法思想
四、考核要求
1. 领会
1) 图的逻辑结构及特征
2) 图的常用术语及含义
3) 生成树和最小生成树的概念
4) 对给定的图遍历，画出深度优先和广度优先生成树或森林
5) Prim和 Kruskal算法的基本思想、时间性能及这两种算法各自的特点
6) 要求对给定的连通图，根据Prim和Kruskal算法构造最小生成树
7) 最短路径的含义
8) 求单源点的最短路径问题的Dijkstra算法的基本思想和时间性能
9) 拓扑排序的基本思想和步骤
10) 拓扑排序不成功的原因
11) 对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列
2. 简单应用
1) 图的邻接矩阵表示法和邻接表表示法
2) 根据应用问题的特点选择合适的存储结构
3) 连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法。
4) 确定两种遍历的顶点访问序列
5) 图的两种遍历和树的遍历之间的关系
6) 两种遍历算法分别使用的数据结构（栈和队列）
7) 利用图的遍历解决简单的应用问题
第九章 查找
一、学习目的和要求
本章的目的是介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。难点是二叉排序树上的删除算法。
二、课程内容
第一节 静态查找表
第二节 动态查找表
第三节 哈希表
二、 考核知识点
1、 查找的定义关键字、查找、平均查找长度
2、 静态查找表的查找算法（顺序查找、折半查找、分块查找(索引顺序表的查找)） 及其效率(最坏和平均长度)。
3、 二叉排序树的查找算法及其效率。
4、 平衡二叉树的定义。
5、 哈希法的特点
6、 哈希函数和散列地址。
7、 构造哈希函数的几种方法。直接寻址法、除留余数法、平方取中法、折叠法、数字分析法。
8、 处理冲突的方法：开放寻址法和链地址法。开放寻址法又分为线性探测再散列、二次探测再散列和伪随机探测再散列。
四、考核要求
1. 识记
1) 查找在数据处理中的重要性
2) 查找成功、不成功的含义
2. 简单应用
1) 顺序查找、折半查找、分块查找的基本思想、算法实现和查找效率分析
2) 顺序查找中“监视哨”的作用
3) 比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出 合适的查找方法
4) 二叉排序树和二叉平衡树的定义、特点
5) 二叉排序树的插入、删除、建树和查找算法及时间性能
6) 建立一棵二叉排序树的过程就是对输入序列的排序过程，输入序列对所建立的二叉排序树形态的影响
7) 哈希表、哈希函数、哈希地址（散列地址）、装填因子等有关概念
8) 哈希函数的构造方法和解决冲突的方法
9) 哈希表和其它表的本质区别
第十章 内部排序
一、学习目的和要求
本章的目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想和排序过程。难点是这四类排序算法的实现。
二、课程内容
第一节 概述
第二节 插入排序
第三节 快速排序
第四节 选择排序
第五节 归并排序
第六节 基数排序
第七节 各种内部排序方法的比较讨论
三、 考核知识点
1、 排序的目的、分类和排序方法的稳定性的定义。
2、 插入排序：直接插入排序的算法、折半插入排序的算法、希尔排序的思想。
3、 选择排序的思想
4、 堆排序的方法、堆的定义、初始堆的建立。
5、 起泡排序的思想。
6、 快速排序的算法、快速排序的最坏情况时间复杂度的分析。
7、 归并排序的思想。
8、 基数排序的思想及特点。
四、考核要求
1. 识记
1) 排序在数据处理中的重要性
2) 排序方法稳定性的含义
3) 排序方法的分类及算法好坏的评判标准
2. 领会
1) 归并排序的基本思想和算法实现，以及时间性能分析
2) 针对给定的输入序列，能写出归并排序的排序过程
3) 基数排序的基本思想
4) 分配排序和其它几类排序方法的区别
3. 简单应用
1) 堆、极小堆、极大堆、堆顶等有关概念和定义
2) 堆的性质及堆与完全二叉树的关系
3) 直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析
4) 针对给定的输入序列，写出堆排序的排序过程
5) 比较各种排序算法的优缺点
6) 根据实际问题的特点和要求选择合适的排序方法
4. 综合应用
1) 直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析
2) 直接插入排序中“监视哨”的作用
3) 针对给定的输入序列，要能写出直接插入排序的排序过程
4) 起泡排序的基本思想
5) 快速排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析，了解算法的稳定性
6) 枢轴元素的选择对排序的影响
7) 针对给定的输入序列，能写出快速排序的排序过程
第十二章 文 件
一、学习目的和要求
本章的目的是介绍存储在外存上的数据结构（文件）的有关概念、各种文件及其特点、组织方式及其查询和更新操作，要求对这些内容做一般性的了解，本章不是重点。。
二、课程内容
第一节 有关文件的基本概念
第二节 顺序文件
第三节 索引文件
第四节 ISAM文件和VSAM文件
第五节 直接存取文件
第六节 多关键字文件
三、考核知识点
9、 文件的基本概念
10、 常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件
11、 顺序文件的特点及查找方法
12、 索引文件的组织方式
13、 索引顺序文件常用的有两种：ISAM文件和VSAM文件
14、 散列文件（直接存取文件）的特点及优点
15、 两种多关键字文件的组织方法：多重表文件和倒排表
四、考核要求
1. 识记
1) 文件的基本概念
2) 常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件
3) 顺序文件的特点及查找方法
4) 索引文件的组织方式
5) 索引顺序文件常用的有两种：ISAM文件和VSAM文件
6) 散列文件（直接存取文件）的特点及优点
7) 两种多关键字文件的组织方法：多重表文件和倒排表

教材：《数据结构》（C语言版）严蔚敏 吴伟民 编着，清华大学出版社1996年版。

考题类型及分数分布：
本课程考试试题类型填空题、问答题、综合应用题三种形式，其中填空题20分、问答题25分，综合应用题30分。
这是2010考试的考纲，我想2011年考纲不会有太大的变化