第二部分 核心讲义
【公共基础知识】
第1章 数据结构与算法
一、算法
1算法的基本概念
（1）算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。
【注意】算法不等于程序，也不等于计算方法。
（2）算法的基本特征
（1）可行性（Effectiveness）：算法中的每一个步骤必须能够实现，执行的结果要能够达到预期的目的。
（2）确定性（Definiteness）：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义性。
（3）有穷性（Finiteness）：算法必须能在有限的时间（合理的时间）内做完，即算法必须能在执行有限个步骤之后终止。
（4）拥有足够的情报：输入是否足够并正确，输出是否合理。初始状态是否正确。
2算法设计基本方法
（1）列举法
①基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。
②主要特点
算法比较简单，但列举情况较多时，算法工作量很大。
③注意事项
例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。
（2）归纳法
①基本思想
通过列举少量的特殊情况，经过分析，最后找出一般的关系。
②主要特点
a．比列举法更能反映问题的本质，可解决列举量为无限的问题；
b．可操作性低，不易归纳出一个具体数学模型；
c．归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。
（3）递推
①基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
②主要特点
a．初始条件或问题本身已给定，或通过对问题的分析化简得到；
b．递推本质上属于归纳法，递推关系式往往是归纳的结果；
c．数值型递推算法计算过程中必须注意数值计算的稳定性问题。
（4）递归
①基本思想
将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。
②主要特点
a．递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；
b．在可计算性理论和算法设计中占有重要地位；
c．递归算法比递推算法清晰易读，结构简练；
d．设计递归算法比递推算法容易，但是其执行效率较低。
③分类
a．直接递归。一个算法P显式地调用自己。
b．间接递归。算法P调用另一个算法Q，而算法Q又调用算法P。
④递归与递推的区别
递归与递推的区别主要在于二者实现方法的不同，表现为：
a．递归是从算法本身到达递归的边界的；
b．递推是从初始条件出发，逐次推出所需求的结果。
（5）减半递推技术
减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。
（6）回溯法
回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。
3算法复杂度
（1）时间复杂度
①定义
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量＝f（n），其中，n是问题的规模。
②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：
a．平均性态
平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
b．最坏情况复杂性
最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。
（2）空间复杂度
①定义
算法的空间复杂度一般是指执行这个算法所需要的内存空间。
②存储空间组成
a．算法程序占用的空间；
b．输入的初始数据占用的存储空间；
c．算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。
二、数据结构的基本概念
1概述
（1）数据处理概述
①定义
数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
②关键问题
大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。
（2）数据结构研究概述
①研究问题
a．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
b．在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
c．对各种数据结构进行的运算。
②研究目的
主要目的在于提高数据处理效率，包括：
a．提高数据处理的速度；
b．尽量节省在数据处理过程中所占用的计算机存储空间。
2数据结构的概念
（1）数据结构的定义
数据结构是指相互有关联的数据元素的集合。
一个数据结构应包含：
①表述数据元素的信息；
②表示各数据元素之间的前后件关系。
（2）数据的逻辑结构
①定义
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
②要素
a．数据元素的集合，通常记为D；
b．D上的关系，通常记为R，它反映了D中各数据元素之间的前后件关系。
③表示
一个数据结构B可表示为：B＝（D，R）
为反映D中各数据元素之间的前后件关系，一般用二元组来表示。
（3）数据的存储结构
【定义】数据的逻辑结构在计算机存储空间中的存放形式。
【注意】
①各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
②在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
③常用的存储结构有顺序、链接、索引等存储结构。
④采用不同的存储结构，其数据处理的效率是不同的。
3数据结构的图形表示
（1）在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的方框表示，称为数据结点（简称结点）；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。
（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称叶子结点），其余结点都称为内部结点。
（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。
4线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。
【注意】在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。
三、线性表及其顺序存储结构
1线性表的基本概念
（1）线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
（2）非空线性表的结构特征：
①有且只有一个根结点a1，它无前件；
②有且只有一个终端结点an，它无后件；
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
【说明】
①线性表中结点的个数n称为线性表的长度。
②当n＝0时，称为空表。
2线性表的顺序存储结构
（1）概述
顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。
（2）特点：
①线性表中所有元素所占的存储空间是连续的；
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（3）运算
在线性表的顺序存储结构下，可对线性表进行以下运算：
①插入：在线性表的指定位置处加入一个新的元素；
②删除：在线性表中删除指定的元素；
③查找：在线性表中查找某个（或某些）特定的元素；
④排序：对线性表中的元素进行整序；
⑤分解：按要求将一个线性表分解成多个线性表；
⑥合并：按要求将多个线性表合并成一个线性表；
⑦复制：复制一个线性表；
⑧逆转：逆转一个线性表等。
3顺序表的插入运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：
（1）首先处理以下三种异常情况：
①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；
②当i＞n时，认为在最后一个元素之后（即第n＋1个元素之前）插入；
③当i＜1时，认为在第1个元素之前插入。
（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。
4顺序表的删除运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：
（1）首先处理以下两种异常情况：
①当线性表为空（即n＝0）时为“下溢”错误，不能进行删除，算法结束；
②当i＜1或i＞n时，认为将第一个或者最后一个元素删除。
（2）然后从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。
（3）最后将线性表的长度减小1。
四、栈和队列
1栈及其基本运算
（1）栈的定义
栈是限定在一端进行插入与删除的线性表。
（2）栈的特点：
①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。
②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。
③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。
（3）栈的顺序存储及其运算
在栈的顺序存储空间S（1：m）中，top＝0表示栈空；top＝m表示栈满。
栈的三种运算：
①入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
a．首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
b．然后将栈顶指针进一（即top加1）。
c．最后将新元素插入栈顶指针指向的位置。
②退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
b．然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
c．最后将栈顶指针退一（即top减1）。
③读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
b．然后将栈顶元素赋给指定的变量。
【注意】这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。
2队列及其基本运算
（1）什么是队列
队列是指允许在一端进行插入，而在另一端进行删除的线性表。
（2）队列的特点
①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。
②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。
③队尾指针rear和排头指针front共同反映队列中元素变动情况。
④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。
（3）循环队列及其运算
循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s＝0；队列满的条件是s＝1且front＝rear。
队列的两种运算
假设循环队列的初始状态为空，即：s＝0，且front＝rear＝m。
①入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
a．首先判断循环队列是否满。当循环队列非空（s＝1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
b．然后将队尾指针进一（即rear＝rear＋1），并当rear＝m＋1时置rear＝1。
c．最后将新元素插入队尾指针指向的位置，并且置循环队列非空标志。
②退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
a．首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
b．然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。
c．再将排头指针指向的元素赋给指定的变量。
d．最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。
五、线性链表
1线性链表的基本概念
（1）线性表的顺序存储结构存在的缺陷：
①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。
②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。
③线性表的顺序存储结构不便于对存储空间的动态分配。
（2）链式存储结点组成：
①数据域：用于存放数据元素值。
②指针域：用于存放指针。
指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。
（3）线性链表
①定义：线性链表是线性表的链式存储结构。
②特点
a．各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；
b．各数据元素之间的前后件关系是由各结点的指针域来指示的；
c．每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。
为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。
（4）带链的栈
带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。
与顺序栈一样，带链栈的基本操作有以下几个：
①栈的初始化：建立一个空栈的顺序存储空间；
②入栈运算：在栈顶位置插入一个新元素；
③退栈运算：取出栈顶元素并赋给一个指定的变量；
④读栈顶元素：将栈顶元素赋给一个指定的变量。
（5）带链的队列
与顺序队列一样，带链队列的基本操作有以下几个：
①队列的初始化：建立一个空队列的顺序存储空间；
②入队运算：在循环队列的队尾加入一个新元素；
③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。
（6）双向链表
对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。
2线性链表的基本运算
（1）常见的线性表的运算
线性链表的运算主要有以下几个：
①插入：在线性链表中包含指定元素的结点之前插入一个新元素。
②删除：在线性链表中删除包含指定元素的结点。
③合并：将两个线性链表按要求合并成一个线性链表。
④分解：将一个线性链表按要求进行分解。
⑤逆转
⑥复制
⑦排序
⑧查找
（2）在线性链表中查找指定元素
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。
这种方法找到的结点p有两种可能：
①当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；
②当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。
（3）线性链表的插入
①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。
②插入过程：
在线性链表中包含元素x的结点之前插入一个新元素y。
a．从可利用栈取得一个结点，设该结点号为p，并置结点p的数据域为插入的元素值y。
b．在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。
c．最后将结点p插入到结点q之后。
为了实现这一步，只要改变以下两个结点的指针域内容：
第一，使结点p指向包含元素x的结点；
第二，使结点q的指针域内容改为指向结点p。
③插入特点：
a．不会发生上溢现象；
b．可方便实现存储空间动态分配；
c．不发生数据元素移动现象，只改变结点指针，提高插入效率。
（4）线性链表的删除
①定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。
②删除过程：
在线性链表中删除包含元素x的结点。
a．在线性链表中寻找包含元素x的前一个结点，设该结点序号为q；
b．将结点q后的结点p从线性链表中删除，也就是让结点q的指针指向包含元素x的结点p的指针指向的结点；
c．将包含元素x的结点p送回可利用栈。
③删除特点：
在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。
3循环链表
（1）与线性链表相比，循环链表具有的特点：
①在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
②循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
（2）与线性单链表相比，循环链表具有两方面优点：
①在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。而线性单链表做不到这一点。
②由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
【说明】循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。
六、树与二叉树
1树的基本概念
（1）树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。
（2）在树结构中，每个结点只有一个前件（父结点），没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件（子结点），没有后件的结点称为叶子结点。
（3）一个结点拥有的后件个数称为该结点的度。除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。
（4）根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度。
（5）在树中，叶子结点没有子树。
（6）用树来表示算术表达式的原则：
①表达式中的每一个运算符在树中对应一个结点，称为运算符结点；
②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；
③运算对象中的单变量均为叶子结点。
2二叉树及其基本性质
（1）二叉树定义
二叉树是一种很有用的非线性结构，树结构的特殊形式。
（2）二叉树的两个特点
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
（3）二叉树的基本性质
①在二叉树的第k层上，最多有2k－1（k≥1）个结点。
②深度为m的二叉树最多有2m－1个结点。
③在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
④具有n个结点的二叉树，其深度至少为[log2n]＋1，其中[log2n]表示取log2n的整数部分。
（4）满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
①满二叉树
除最后一层外，每一层上的所有结点都有两个子结点。
②完全二叉树
a．除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
b．对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p＋1。
c．满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。
③完全二叉树具有以下两个性质：
a．具有n个结点的完全二叉树的深度为[log2n]＋1。
b．设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k＝1，2，…，n）的结点有以下结论：
第一，若k＝1，则该结点为根结点，它没有父结点；若k＞1，则该结点的父结点编号为INT（k/2）。
第二，若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
第三，若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。
根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
3二叉树的存储结构
（1）在计算机中，二叉树采用链式存储结构。
（2）用于存储二叉树中各元素的存储结点由两部分组成：
①数据域
②指针域
4二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：
（1）前序遍历（DLR）
首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。
（2）中序遍历（LDR）
首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。该过程是一个递归的过程。
（3）后序遍历（LRD）
首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。该过程是一个递归的过程。
【注意】
①如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。
②如果知道了某二叉树的后序序列和中序序列，则可以唯一地恢复该二叉树
③如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。
七、查找技术
1顺序查找（顺序搜索）
（1）基本方法
查找成功：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到。
查找失败：若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素。
（2）以下两种情况只能采用顺序查找：
①线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
（3）顺序查找的缺陷
效率太低。
2二分法查找（对分查找）
（1）适用范围
只适用于顺序存储的有序表，在此所说的有序表是指线性表中元素按值非递减排列。
（2）具体方法
设有序线性表的长度为n，被查元素为x，则：
①将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；
②若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；
③若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找；
④这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
八、排序技术
1交换类排序法
（1）冒泡排序法
①定义：冒泡排序法是一种最简单的交换类排序方法，通过相邻数据元素的交换逐步将线性表变成有序。
②基本过程：
a．从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。
b．从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。
c．对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
③在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n－1）/2。
（2）快速排序法
①基本思想
从线性表中选取一个元素T，将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，这样就以T为分割线将线性表分割成前后两个子表。再将得到的子表按照这个过程继续下去，直到所有子表为空为止。
②快速排序在最坏情况下需要进行n（n－1）/2次比较，但实际的排序效率要比冒泡排序高得多。
2插入类排序法
（1）简单插入排序法
①定义：所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
②插入过程：
将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j－1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。
③这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n（n－1）/2次比较。
（2）希尔排序法
①基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。
②子序列的分割方法：
将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般取ht＝n/2k（k＝1，2，…，[log2n]），其中n为待排序序列的长度。
③如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为O（n1.5）。
3选择类排序法
（1）简单选择排序法
①基本思想：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n－1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。
②简单选择排序法在最坏情况下需要比较n（n－1）/2次。
（2）堆排序法
①堆的定义
具有n个元素的序列（h1，h2，…，hn），当且仅当满足
称之为堆。
②堆排序的方法：
a．将一个无序序列建成堆；
b．将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）；
c．反复做上一步，直到剩下的子序列为空为止。
③在最坏情况下，堆排序需要比较的次数为O（nlog2n）。