长度为1时，排序结束。
例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。 采用冒泡排序法，具体操作步骤如下： 序列长度n=7
原序列 5 2 9 4 1 7 第一遍（从前往后） 5?? 2 9 4 1 7 2 5 9?? 4 1 7 2 5 4 9?? 1 7 2 3 4 1 9?? 7 2 5 4 1 7 9?? 第一遍结束后 2 5 4 1 7 6
第二遍（从前往后）
第二遍结束后
第三遍（从前往后）
第三遍结束
2 2 2 2 2 2 2 2
5?? 4 4 4 4 4?? 1 1
4 5?? 1 1 1 1 4 4 4 4 4
1 1 5 5 5 5 5 5 5 5 5
7 7 7?? 6 6 6 6 6 6 6 6
6 6 6 7 7 7 7 7 7 7 7
6 6 6 6 6 6 9 9 9 9 9 9 9 9 9 9 9 9
第四遍（从前往后） 2?? 1 1 2 第四遍结束 1 2
最后结果 1 2 4 5 6 7 9
扫描的次数，最多需要扫描n-1次，如果序列已经就位，则扫描结束。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，则说明数据排序结束。 2）快速排序法
冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进行交换，可以消除多个逆序。
快速排序的方法是：
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界线，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。
再将前后两个子表再进行相同的快速排序，将子表再进行分割，直到所有的子表均为空，则完成快速排序操作。
在快速排序过程中，随着对各子表不断的进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不用的子表记忆起来，这里可用栈来实现。
对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表进行分割。
这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。
2．插入类排序法 1）简单插入排序
插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
插入排序操作的思路：在线性表中，只包含第1个元素的子表，作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。
该方法与冒泡排序方法的效率相同，最坏的情况下需要n(n-1)/2次比较。 例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。 采用简单插入排序法，具体操作步骤如下： 序列长度n=7 5 2 9 4 1 7 6
插入排序后的结果
2）希尔排序法
希尔排序法的基本思想：
将整个无序序列分割成若干小的子序列分别进行插入排序。
子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。
k
增量序列一般取ht=n/2(k=1,2,?,[log2n])，其中n为待排序序列的长度。 3．选择类排序法 1）简单选择排序法
基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。
对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。
例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。 采用简单选择排序法，具体操作步骤如下：
2 2 2 1 1 1
?j=2 5 9 5 4 2 2 2
4
1 1
7 7 7
6 6 6 6
?j=3 9 4 5 4 4 4
?j=4 9 1 5 5 5
?j=5 9 7 7 6
?j=6 9 6 7
?j=7 9
原序列 第一遍扫描 第二遍扫描 第三遍扫描 第四遍扫描 第五遍扫描 第六遍扫描 排序结果
2）堆排序法
堆排序法属于选择类排序方法。
5 2 9 4 1 7 6 1 2 9 4 5 7 6 1 2 9 4 5 7 6 1 2 4 9 5 7 6 1 2 4 5 9 7 6 1 2 4 5 6 7 9 1 2 4 5 6 7 9 1 2 4 5 6 7 9
?hi?h2i堆的定义：具有n个元素的序列（h1,h2,?,hn），当且仅当满足??hi?h2i?1或hi?h2ihi?h2i?1（I=1,2,?,n/2）时称之为堆。
本节只讨论满足前者条件的堆。
由堆的定义看，堆顶元素（即第一个元素）必为最大项。 可以用一维数组或完全二叉树来表示堆的结构。 用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的最大项。
例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。 利用堆排序法将该序列进行排序。
5 2 4 1 7 9 6 4 2 1 7 9 5 6 2 4 1 5 9 7 6 无序堆 调整根结点 调整子树的根结点
建堆的过程
操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5<9，将5与9进行交换；整后，对左右子树进行堆调整，左子树的根结点2小于其左叶子结点5，调整；右子树的根结点5小于其左右子结点7和6，根据堆的要求，将5与7进行调整。
根据堆的定义，可以得到堆排序的方法： （1）首先将一个无序序列建成堆
（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。 三、例题分析 1．选择题
1）算法指的是
A）计算机程序 B）解决问题的计算方法
C）排序算法 D）解决问题的有限运算序列 【答案】D
2）线性表采用链式存储时，结点的存储地址 A）必须是不连续的 B）连续与否均可
C）必须是连续的 D）和头结点的存储地址相连续 【答案】Ｂ
3）将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为 A）O（1） B）O（n） C）O（m） D）O（m+n） 【答案】Ｃ
5）树型结构最适合用来描述 A）有序的数据元素 B）无序的数据元素
C）数据元素之间的具有层次关系的数据 D）数据元素之间没有关系的数据 【答案】C
6）若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树的结点数是 A）15 B）16 C）17 D）18 【答案】D
7）若某完全二叉树的深度为h，则该完全二叉树中至少有多少个结点
hh-1h-1h-1
A）2 B）2 C）2-1 D）2+1 【答案】B
8）在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该 A）只有左子树上的所有结点 B）只有左子树上的部分结点 C）只有右子树上的所有结点 D）只有右子树上的部分结点 【答案】A 9）设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为
A）front=front+1 B）front=(front+1)%(m-1) C）front=(front-1)%m D）front=(front+1)%m 【答案】D
10）用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是
A）选择排序 B）希尔排序 C）归并排序 D）快速排序 【答案】D 2．填空题
1）数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。
【答案】存储（或存储结构）
2）栈顶的位置是随着 操作而变化的。
【答案】进栈和退栈
3）已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。 【答案】384
4）对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。
【答案】进栈PUSH 出栈POP
5）在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个 ,且存在一条从根到该结点的 。
【答案】前驱 路径
6）给出下列二叉树的前序遍历序列 。
【答案】C A B E F D H G
7）数据的逻辑结构被分为___________、____________、___________和___________四种。
【答案】线性表 队列 栈 树
8）在一棵二叉树中，第5层上的结点数最多为_________。 【答案】16
9）以二分查我方法查找一个线性表时，此线性表必须是___________存储的________表。
【答案】顺序 有序
10）在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。
【答案】２ 四、小结
通过本章的学习，要求了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利用图形的方式表示数据结构；了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的线性表的基本运算；了解栈和队列的基本概念，并掌握它们的基本运算；了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循环链表的基本概念和基本操作；理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存储结构和遍历技术；掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；学会利用相关的排序技术实现无序数列的排序操作。