数据结构与算法二级培训

数据结构与算法数据结构与算法二级培训数据结构与算法二级培训全文共75页，当前为第1页。第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法与算法分析数据结构与算法二级培训全文共75页，当前为第2页。1.1什么是数据结构一、计算机解决问题的一般过程。1、建立数学模型。2、根据数学模型，设计算法。3、编写程序，调试直至问题的最终解决。二、数值问题与非数值问题。数值问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积。非数值问题就是问题中涉及的对象不能用数来表达的那些问题。数据结构与算法二级培训全文共75页，当前为第3页。1）数值问题例1已知：游泳池的长length和宽wide，求面积area。

分析：

问题涉及的对象：游泳池的长length宽wide，面积area；

对象之间的关系：area=lengthwide；main(){

intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);

}

数据结构与算法二级培训全文共75页，当前为第4页。2）非数值问题例2已知研究生选课情况，安排课程考试的日程。研究生选课情况表

姓名选修课1选修课1选修课1张ABE王CEF李DFA赵BF数据结构与算法二级培训全文共75页，当前为第5页。分析：

◆问题涉及的对象：课程；◆课程之间的关系：同一个研究生选修的不能按排在同一时间内考试；课程及课程之间的关系可用如下所示的图表示：DEFCBA顶点：表示课程；

边：同一研究生选修的课程用边连接数据结构与算法二级培训全文共75页，当前为第6页。课程考试安排问题转化为图的着色问题

用尽可能少的颜色为该图的每个顶点着色，使相邻的顶点着上不同的颜色；每一种颜色代表一个考试时间，着上相同颜色的顶点是可以按排在同一时间考试的课程；DEFCBAACEFBD

课程着色的过程红色：a，c；黄色：b，d；绿色：e；蓝色：f

即a,c可安排在同一时间考试，b,d可安排在同一时间考试;数据结构与算法二级培训全文共75页，当前为第7页。设G表示课程关系图，集合V包含图G中所有尚未着色的顶点，NEW表示可以用新颜色着色的顶点集合。I=1；

WHILEV非空DO

置NEW为空集合；

FOR每个vVDO

IFv与NEW中所有的结点间都没有边

从V中去掉v；将v加入NEW；

（第I天考试课程为NEW中顶点所对应的课程）

以某种形式输出NEW中顶点所对应的课程；

I=I+1；

数据结构与算法二级培训全文共75页，当前为第8页。

通过对上个问题的分析，在这个问题的分析解决的过程中我们遇到了以下几个问题：1、如何表示节点以及它们之间的关系（相邻接）2、在计算机中如何存储。3、相应的操作如何描述。（染色过程）数据结构与算法二级培训全文共75页，当前为第9页。3）数值问题与非数值问题的比较

数值问题已知游泳池的长length,和宽wide,求面积area。（1）问题涉及的对象：length,wide,area是实数可用数值表示；

（2）对象之间的关系：area=lengthwide

可用方程或函数表示；

（3）数据存储：可用程序设计语言中的实型变量存储；

（4）问题求解：用某种计算方法求解；数据结构与算法二级培训全文共75页，当前为第10页。已知研究生选课情况，安排课程考试的日程。1）问题涉及的对象：课程可用课程名表示,不能用数值表示2）对象之间的关系：同一研究生选修的课程不能安排在同一时间考试，同一研究生选修的课程之间有某种“冲突”关系——课程之间的这种关系不能用方程或函数表示3）数据及数据之间的关系如何存储？4）如何求解？数据结构与算法二级培训全文共75页，当前为第11页。

非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和操作等的学科。数据结构与算法二级培训全文共75页，当前为第12页。1.2基本概念和术语1、数据：一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。2．数据元素数据元素（也叫节点），它是组成数据的基本单位。在程序中通常作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。数据结构与算法二级培训全文共75页，当前为第13页。表1-1个人书库数据结构与算法二级培训全文共75页，当前为第14页。3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合N={0，±1，±2，……}，字母数据对象的集合C={‘A’,’B’,……’Z’}。4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。根据数据结构之间关系，通常有下列4类基本结构。集合线性结构树型结构图状结构数据结构与算法二级培训全文共75页，当前为第15页。数据结构的形式定义为：数据结构是一个二元组

Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集合。数据结构与算法二级培训全文共75页，当前为第16页。5、数据的逻辑结构：数据元素之间的逻辑关系。数据的存储结构：数据结构在计算机中的表示。本课程中介绍的存储结构有：顺序存储结构链式存储结构

索引结构散列结构6、数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。7、抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。数据结构与算法二级培训全文共75页，当前为第17页。抽象数据类型可以用下面的三元组来表示（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象数据类型：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据名。数据结构与算法二级培训全文共75页，当前为第18页。1.4算法和算法分析算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；它有5个重要特征。有穷性：确定性：相同的输入得到相同的输出。可行性：输入：输出：数据结构与算法二级培训全文共75页，当前为第19页。算法设计的要求：正确性：正确的含义，有四个层次。可读性：健壮性：效率和低存储量的要求：数据结构与算法二级培训全文共75页，当前为第20页。

一个用高级语言编写的程序在计算机上运行所需要的时间取决于下列因素：⑴依据算法所选用的策略。⑵问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。⑶书写程序的语言。语言的级别越高，其执行效率就越低。⑷编译程序所生成目标代码的质量。⑸机器指令执行的速度（硬件的速度）。与硬件的配置高低有关。数据结构与算法二级培训全文共75页，当前为第21页。

通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模n，或者说它是问题规模n的函数f(n)。【例】求累加求和intsum(intb[]，intn）｛

intsum=0;/*第1条定义并赋初值语句执行1次*/for（inti=0；i<n；i++）

sum+=b[i];/*n次*/returnsum;/*返回语句执行1次*/

｝数据结构与算法二级培训全文共75页，当前为第22页。

要精确地计算f(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作

T(n)=Ο(f(n))它表示随问题的规模n的增大，算法执行时间的增长率和f(n)相同。使用大Ο记号，Ο(f(n))称为算法的渐进时间复杂度，简称时间复杂度。数据结构与算法二级培训全文共75页，当前为第23页。例如，一个程序的实际执行时间为

2.7n3+3.8n2+5.3。则T(n)＝Ο(n3)。例、求下面程序段的时间复杂度。

s=0;for(j=1;j<=n;j++)for(x=1,k=1;k<=n;k++){x=x*k;s+=x;}数据结构与算法二级培训全文共75页，当前为第24页。{++x;a=0;}T(n)=O(1);//常量阶for(i=1;i<=n;++i){++x;s+=x;}T(n)=O(n);//线性阶for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}T(n)=O(n2)//平方阶数据结构与算法二级培训全文共75页，当前为第25页。通常将称Ο(1)为常数阶，Ο(n)为线性阶，O(n2)为平方阶。算法还可能呈现的复杂度有：对数阶Ο(log2n)，指数阶Ο(2n)等，不同数量级时间复杂度的关系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)数据结构与算法二级培训全文共75页，当前为第26页。常见函数的增长率数据结构与算法二级培训全文共75页，当前为第27页。

第2章线性表

2.1线性表概念及基本操作2.2线性表的顺序存储和实现数据结构与算法二级培训全文共75页，当前为第28页。2.1线性表概念及基本操作

例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。

姓名电话号码

蔡颖63214444

陈红63217777

刘建平63216666

王小林63218888

张力63215555...数据结构与算法二级培训全文共75页，当前为第29页。说明：设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继；数据结构与算法二级培训全文共75页，当前为第30页。3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；数据结构与算法二级培训全文共75页，当前为第31页。2.2线性表的顺序表示和实现

线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的。假没线性表中每个数据元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：

Loc(ai)=Loc(a1)+(i–1)k

这里Loc(ai)是第i个元素的存储位置,Loc(a1)是第1个元素的存储位置，也称为线性表的基址；数据结构与算法二级培训全文共75页，当前为第32页。线性表的顺序存储的基本操作1）初始化操作InitList_Sq(SqList&L)2）销毁操作DetroyList_Sq(SqList&L){

功能：回收为顺序表动态分配的存储空间

3）置空操作ClearList_Sq(SqList&L)

功能：若L已存在，重新将其置成空表数据结构与算法二级培训全文共75页，当前为第33页。5）插入操作ListInsert_Sq(&L,i,e)

参数：L：顺序表，i插入位置，e被插入元素;因为插入操作对顺序表进行修改,所以用了引用参数&L;

i的取值范围在1-ListLength_Sq(L)+1;功能：在顺序表L的第i个元素之前插入一个新元素e;6)删除操作ListDelete_sq(SqList&L,inti,ElemType&e)功能：删除顺序表L的第i个元素，并用e返回

数据结构与算法二级培训全文共75页，当前为第34页。3.1

栈

3.1.1栈的概念3.1.2栈的顺序存储和实现第3章栈和队列数据结构与算法二级培训全文共75页，当前为第35页。3.1.1抽象数据类型栈的定义栈是限定仅能在表尾一端进行插入、删除操作的线性表说明：设（a1,a2,a3,…,an）是一个栈1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素。

2）在表尾插入元素的操作称进栈操作，在表头删除元素的操作称为出栈操作;

（a1,a2,...,ai-1,ai,ai+1,…,an

）栈底栈顶进栈出栈数据结构与算法二级培训全文共75页，当前为第36页。cbafed栈操作演示数据结构与算法二级培训全文共75页，当前为第37页。3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶,第一个出栈的元素为栈顶元素；

4）栈的元素具有后进先出的特点,所以栈又称为后进先出表（LIFO表）

5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称为栈顶指针的变量指示栈顶的位置。数据结构与算法二级培训全文共75页，当前为第38页。栈的基本操作1）

初始化操作InitStack(&S)

操作结果：构造一个空栈S；2）销毁栈操作DestroyStack(&S)

初始条件：栈S存在。操作结果：销毁一个已存在的栈;

3）置空栈操作ClearStack(&S)

初始条件：栈S存在。操作结果：将栈S置为空栈;4）判空操作StackEmpty(S)

初始条件：栈S存在。操作结果：若栈S为空，则返回True，否则返回False;5）求栈长度操作StackLength(S）初始条件：栈S存在。操作结果：返回S元素的个数，即栈的长度。数据结构与算法二级培训全文共75页，当前为第39页。6）取栈顶元素操作GetTop(S,&e)

初始条件：栈S存在，且非空。操作结果：取栈顶元素，并用e返回;7）进栈操作Push(&S,e)

初始条件：栈S存在。操作结果：元素e进栈;8）退栈操作Pop(&S,&e)

操作结果：栈顶元素退栈，并用e返回;9）栈的遍历操作StackTraverse（S，visit（））初始条件：栈S存在。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失败。数据结构与算法二级培训全文共75页，当前为第40页。3.1.2栈的顺序存储和实现

栈的顺序存储结构也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。数据结构与算法二级培训全文共75页，当前为第41页。

栈操作图示topbasebasetopbasetopbasetopAABCDAB空栈A进栈BCD进栈DC出栈数据结构与算法二级培训全文共75页，当前为第42页。

3.2队列3.2.1队列的概念3.2.2循环队列

数据结构与算法二级培训全文共75页，当前为第43页。一什么是队列

队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入删除3.2.1队列的概念数据结构与算法二级培训全文共75页，当前为第44页。说明：设（a1,a2,

a3,...,an

）为一队列

1）表尾称作队尾，表头称为队头；

2）a1为队头元素，an为队尾元素；

3）在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；

4）元素按a1,a2,a3,...an

顺序入队，第一个入队的元素为a1

，最后一个入队的元素是an，

第一个出队的元素为a1，最后一个出队的元素是an；

5）队列具有先进先出的特点，所以又称为先进先出表（FIFO表）

数据结构与算法二级培训全文共75页，当前为第45页。队列的示意图

队列类似于日常的排队，新来的人站在队尾，队头的人进行事务处理后离队。队列通常设置两个变量分别指示队头元素位置和队尾元素的位置，这两个变量分别称为队头指针、队尾指针；a1a2a3an入队列队头队尾出队列数据结构与算法二级培训全文共75页，当前为第46页。二队列的基本操作1）初始化操作InitQueue(&Q)

功能：构造一个空队列Q；

2）销毁操作DestroyQueue(&Q)

功能：销毁已存在队列Q；

3）置空操作ClearQueue(&Q)

功能：将队列Q置为空队列；4）判空操作QueueEmpty(Q)功能：若队列Q为空,则返回True，否则返回False；

数据结构与算法二级培训全文共75页，当前为第47页。5）求队列长度QueueLength（LinkQueue&Q)6）取队头元素操作GetHead(Q,&e)

功能：取队头元素，并用e返回；

7）入队操作EnQueue(&Q,e)

功能：将元素e插入Q的队尾；

8）出队操作DeQueue(&Q,&e)

功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR；数据结构与算法二级培训全文共75页，当前为第48页。第4章树和二叉树数据结构与算法二级培训全文共75页，当前为第49页。4.1

树的有关概念1．树的概念树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。树是n个结点的有限集合，在任一棵非空树中：

（1）有且仅有一个称为根的结点。

（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念数据结构与算法二级培训全文共75页，当前为第50页。例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J}A是根，其余结点可以划分为3个互不相交的集合：

T1={B,E,F},T2={C,D},T3={D,H,I,J}这些集合中的每一集合都本身又是一棵树，它们是A的子树。

例如对于T1，B是根，其余结点可以划分为2个互不相交的集合：

T11={E}，T12={F}，T11,T12是B的子树。JIACBDHGFE数据结构与算法二级培训全文共75页，当前为第51页。从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）树是一种层次结构JIACBDHGFE数据结构与算法二级培训全文共75页，当前为第52页。

树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层：根结点的层定义为1；根的孩子为第2层结点 ，依此类推；

树的高度：树中最大的结点层．数据结构与算法二级培训全文共75页，当前为第53页。结点的度：结点子树的个数

树的度：树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点；

森林；互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；数据结构与算法二级培训全文共75页，当前为第54页。5树的基本操作1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);

数据结构与算法二级培训全文共75页，当前为第55页。8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Parent(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());数据结构与算法二级培训全文共75页，当前为第56页。4.2.1二叉树的定义二叉树：它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。

A

F

G

E

D

C

B

4.2二叉树数据结构与算法二级培训全文共75页，当前为第57页。

A

F

G

E

D

C

B

(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)

A

G

E

D

B

C

F(b)数据结构与算法二级培训全文共75页，当前为第58页。

2．二叉树的基本形态

φ数据结构与算法二级培训全文共75页，当前为第59页。4.3二叉树的遍历

遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事。

思考：二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？

数据结构与算法二级培训全文共75页，当前为第60页。二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：DLR、LDR、LRD

，分别称为：先序遍历、中序遍历、后序遍历。

A

F

G

E

D

C

B数据结构与算法二级培训全文共75页，当前为第61页。先序遍历（DLR）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；

先序遍历序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B数据结构与算法二级培训全文共75页，当前为第62页。中序遍历（LDR）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树中序遍历序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B数据结构与算法二级培训全文共75页，当前为第63页。后序遍历（LRD）若二叉树非空

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点后序遍历序列：D,G,E,B,F,C,A

A

F

G

E

D

C

B数据结构与算法二级培训全文共75页，当前为第64页。

e

d

c

b

f

a

+

*

/

-

-

后序遍历序列：a,b,c,d,-,*,+,e,f,/,-

中序遍历序列：a,+,b,*,c,-,d,-,e,/,f

先序遍历序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍历、中序遍历、后序遍历下图所示的二叉树数据结构与算法二级培训全文共75页，当前为第65页。一、顺序表及查找（线性表及查找）查找表组织：查找表用线性表表示。即将查找表的记录排成一个记录序列。L1=(45,53,12,3,37,24,100,61,90,78)基本思想：从表的最后一个记录（或第一个记录）开始，依次将记录的关键字与给定值比较，若相等：查找成功，否则，继续查找。第5章查找和排序5.1查找数据结构与算法二级培训全文共75页，当前为第66页。二、有序表及查找有序表：若线性表中的记录按关键字有序，则称为有序表。二分查找法（也称为折半查找法）基本思想：将查找范围中间位置的记录关键字与给定值比较：＜：继续在前半个表中用二分查找法查找=：查找成功，返回记录位置＞：继续在后半个表中中用二分查找法查找数据结构与算法二级培训全文共75页，当前为第67页。L2=(3,12,24,37,45,53,61,78,90,100)，查找Key=24的记录

1234567891031224374553617890100lowmidhigh1234567891031224374553617890100lowmidhigh24＜

45继续在前半个表中用二分查找法查找1234567891031224374553617890100Lowmidhigh24＞

12继续在后半个表中用二分查找法查找数据结构与算法二级培训全文共75页，当前为第68页。5.2.1插入排序

基本思想依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。直接插入排序

插入排序的关键：如何查找插入位置。直接插入排序是用顺序查找法定位插入位置。若采用二分查找法定位插入位置则得到另一种插入算法，二分插入排序

5.2排序数据结构与算法二级培训全文共75页，当前为第69页。例：待排记录4938659776132749

（49）38659776132749

（3849）659776132749

（384965）9776132749

（38496597）76132749

（3849657697）132749

（133849657697）2749

（13273849657697）49

（1327384949657697）数据结构与算法二级培训全文共75页，当前为第70页。

交换法排序基本思想：对待排序列中相邻元素进行比较，如果为逆序，则将这两个元素的位置交换。重复此操作直到整个序列全部有序为止。一、冒泡排序基本思路为：首先将第一个记录的关键字和第二个记录的关键字比较，若为逆序，则两个记录交换；然后比较第二个记录和第三个记录的关键字，……，直至第n-1个记录和第n个记录的关键字比较、交换结束为止。经过第一趟排序后，关键字最大(或最小)的记录被调整到最后一个记录的位置。下一趟排序时，这个关键字最大(或最小)的记录就不必考虑了。直到某一趟排序过程中没有进行交换操作为止。5.2.3快速排序数据结构与算法二级培训全文共75页，当前为第71页。二、快速排序 当冒泡排序在数据元素的关键字呈逆序时进行排序，需要进行多次比较和移动操作，数据元素移动是一步一步进行的，且有很多是重复的。快速排序是对冒泡排序算法的改进。

基本思想：快速排序又称为分区交换法，是通过对某关键字(支点)的比较，将各待排序列分成前后两部分，后半部分所有记录的关键字值大于等于支点的关键字值，前半部分所有记录的关键字小于等于支点的关键字值。将待排序列按关键字以支点分成两部分的过程，称为一次划分。对各部分不断的划分，直到整个序列按关键字有序为止。数据结构与算法二级培训全文共75页，当前为第72页。【例】一趟快速排序过程示例

r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]r[10]4328397698694515828

r[0]r[1]r[2]r[3]r[4]