数据结构中排序方法的研究作者：王海燕来源：《科技资讯》2012年第35期摘要：排序是数据处理领域中最常用的一种运算。
排序的目的之一是方便查找。
对于一个顺序存储的线性表，若不经过排序而查找，则时间复杂度为O（n），若在排序的基础上进行二分查找，则时间复杂度可提高到O（logn），效果是相当显著的。
关键词：数据结构排序方法中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2012）12（b）-0027-021 排序的基本概念排序就是把一组记录按照某个领域的值的递增（由小到大）或递减（由大到小）的次序重新排列的过程。
通常把用于排序的域称为排序域或排序项，把该域中的每一个值（它与一个记录相对应）称为排序码。
记录的排序码可以是记录的关键字，也可以是任何非关键字，所以排序码相同的记录可能只有一个，也可能有多个。
对于具有同一个排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。
2 排序的方法排序的方法很多，一般分为插入排序法、交换排序法、选择排序法、归并排序法四种。
2.1 插入排序法插入排序法包括直接插入排序和希尔排序。
（1）直接插入排序：直接插入排序是一种最简单的排序方法。
1）算法思想：直接插入排序的基本思想是：逐个处理待排序列中的记录，将其与前面已经排好序的子序中的记录进行比较，确定要插入的位置，并将记录插入到子序中。
具体做法如以下几点。
①开始时，把第①个记录看成是已经排好序的子序，这时子序中只有一个记录。
②从第②个记录起到最后一个记录，依次将记录和前面子序中的记录比较，确定记录插入的位置。
③将记录插入到子序中，子序记录个数加1，直至子序长度和原来待排序列长度一致时结束。
2）算法分析。
①直接插入排序的时间复杂度为O（n2）。
②直接插入排序是稳定的。
适用于记录个数较少的场合。
（2）希尔排序：希尔排序又称缩小增量排序，是对直接插入排序的一种改进。
《数据结构（C语言版第2版）》（严蔚敏著）第六章练习题答案第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。
（3）具有n个顶点的有向图最多有（）条边。
A．n B．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。
A．n B．2(n-1)C．n/2D．n2答案：B所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。
（7）下面（）算法适合构造一个稠密图G的最小生成树。
A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。
（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A．栈 B.队列 C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
数据结构复习重点谁让我找到你们了.第一章1.数据是信息的载体,它能够被计算机识别、存储和加工处理。
2.数据元素是数据的基本单位。
有些情况下，数据元素也称为元素、结点、顶点、记录。
3.数据结构指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容：①数据元素之间的逻辑关系，也称为数据的逻辑结构；②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；③数据的运算，即对数据施加的操作。
4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
按"值"是否可分解，可将数据类型划分为两类：①原子类型，其值不可分解；②结构类型，其值可分解为若干个成分。
5.抽象数据类型是指抽象数据的组织和与之相关的操作。
可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
6.数据的逻辑结构简称为数据结构。
数据的逻辑结构可分为两大类：①线性结构(~的逻辑特征是若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继)；②非线性结构(~的逻辑特征是一个结点可能有多个直接前趋和直接后继)。
7.数据存储结构可用四种基本的存储方法表示：①顺序存储方法(该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构)；②链接存储方法(该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构)；③索引存储方法(该方法通常是在存储结点信息的同时，还建立附加的索引表)；④散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。
8.非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。
因此，一个算法是一系列将输入转换为输出的计算步骤。
9.求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是"正确"的。
