数据结构笔记

数据构造笔记

基础：数据构造与算法

(-)数据构造基本概念

数据(data)：是对客观事物的符号表达，在计算机科学中是指所有能愉入到计算机中并被

计算机程序处理的符号总称

数据元素(dataelement)：是数据H勺基本单位，在计算机中一般被当做一种整体进行考虑

和处理

数据对象(dataobject)：性质相似的数据元素的集合，是数据的一种子集

数据构造(datastructure)：互相之间存在一种或多种特定关系H勺数据元素的集合

4类基本构造：集合、线性构造、树形构造、图形(网状)构造

数据构造的形式定义为数据构造是一种二元组DataStructure=(D,S),其中D是数据元素

的有限集，S是D上关系的有限集

数据构造定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑构造

数据构造在计算机中H勺表达(映像)称为物理构造(存储构造)

计嵬机中表达信息的最小单位是二进制中的一位，叫做位（bit）,一到若干位构成一种位

串表达一种数据元素，这个位串称为元素或结点

数据构造之间关系在计算机中的表达有两种：次序映像、非次序映像，并由此得到两种存储

构造：次序存储、链式存储，前者运用相对位置表达数据元素间H勺逻辑构造，后者借助指针

任何一种算法口勺设计取决于数据（逻辑）构造，而实现依赖于存储构造

数据类型是•种值的集合和定义在这个值集上的•组操作的总祢

数据类型分两种：原子类型、构造类型，前者不可分解（例如int、char、floatsvoid）,

后者构造类型由若干成分按某种构造构成，可分解，成分既可以是非构造的也可以是构造口勺

（例：数组）

抽象数据类型（AbstractDataType）:是指一种数学模型及定义在该模型上日勺一组操作（P8）

抽象数据类型格式如下：

ADT抽象数据类型名｛

数据对象：（数据对象H勺定义〉

数据关系：〈数据关系口勺定义〉

数据操作：〈数据操作H勺定义＞

}ADT抽象数据类型名

基本操作格式如下：

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作成果：（操作成果描述〉

多形数据类型（polymorphicdatatype）：是指其值得成分不确定的数据类型（P9）

抽象数据类型可由固有数据类型来表达和实现

（-）算法（概念）和算法分析（时、空性能）

算法（algorithm）：对特定问题求解环节的一种描述

算法5特性：有穷、确定、可行、输入、输出

1、为方性：算法必须在可接殳口勺时间内执行有穷步后结束

2、确定性：每条指令必须要有确切含义，无二义性，并且只有唯一执行途径，即对相似H勺

输入只能得相似输出

3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完毕

4、输入：一种算法有一到多种输入，并取自某个特定对象合集

5、输出：一种算法有一到多种输出，这些输出与输入有着某些特定关系的量

算法设计规定（好算法）：对的性、可读性、强健性、效率与低存储需求

强健性是指对于规范规定以外的输入可以判断出这个输入不符合规范规定，并能有合理的处

理方式。

算法效率的度量：

（1）事后记录：程序运行结束后借助计算机内部计时功能，缺陷一是必须先运行根据算法

编制日勺程序，二是受限于计算机软硬件，导致掩盖了算法自身的优劣

（2）事前分析估计：

消耗时间影响原因：算法方略、问题规模、编程语言、编译程序产生的机器码质量、

机器执行指令的速度

撇开多种影响原因只考虑问题的规模（一般用整数量n表达），记为问题规模的困数

算法时间取决于控制构造（次序，分支，循环）和固有数据类型操作的综合效果

书写格式：T(n)=0(f(n))f(n)为nRj某个函数

时间复杂度：算法口勺渐近时间复杂度(asymptotictimecomplexity),它表达随问题规模日勺

增大，算法执行时间的增长率和f(n)的增长率相似

以循环最深层原操作为度量基准

频度：该语句反复执行的次数

算法的存储空间需求：

空间复杂度(spacecomplexity)：算法所需存储空间度量，记作S(n)=0(f(n)),

其中n为问题规模的大小

时间复杂度

空间复杂稳定性复杂性

排序方法平均情•况最坏情况最好情度

况

22

直接插入排O(n)O(n)0(100(1)稳定简单

序

希尔排序O(lllo&21l)O(nlog2ii)0(1)不稳定较复杂

22

冒泡排序O(n)O(n)0(11)0(1)稳定简单

2

快速排序O(idog2ik)O(n)O(nlog21l)O(idog2ii)不稳定较复杂

222

立接选择排O(n)O(n)O(n)0(1)不稳定简单

序

堆排序O(idog2ii)O(lllog21l)O(lllog2ll)0(1)不稳定较复杂

归并排序Q(I11OK211)0(11102211)O(lllog21l)O(n)稳定较复杂

层数排序O(<i(n+1))O(<i(it+r)>O(d(n+r)>0(11+1)稳定较复杂

bogcsdncorri/whuslei

一、线性表

(-)线性表基本概念

线性表（linearjist）：n个数据元素的有限序列

构造特点：存在唯一的被称作“第一种”、“最终一种”的数据元素，且除了第一种以外每

个元素均有唯一前驱，除最终一种以外均有唯一后继

在复杂线性表中存在：数据项—＞记录一文献，例如每个学生状况为一种记录，它由学号、性

别……数据项构成，多种学生无录构成一种文献

在形如在1,…,ai-1,ai.ai+1,an）中，ai-1领先于ai,ai领先于ai+1,且形成直

接前驱元素，宜接后继元素关系

元素个数n定义为线性表长度，n=0为空表

有关操作算法见书（P20）

（-）线性表次序存储构造和链式存储构造

（1）线性表次序表达和实现

线性表次序存储在一组持续日勺存储单元中，链式存储则不规定；次序构造可以随机访问，链

式构造可以无限扩容

确定存储位置（计凫公式）：

第i个元素：LOC（ai）=LOC（a1）+（i-1）*LL是偏移量，即每个元素占用存储单元

第ai+1个元素：LOC（ai+1）=LOC（ai）+La1（起始地址或基地址）

C语言下标从“0”开始,则表中第i个元素是L.elem[i-1]

当对线性表进行操作时，被操作元素背面日勺元素角标会对应变化（前移、后移），算法（P24）

（2）线性表链式表达和实现

特点：用一组任意的存储单元存储线性表的数据元素（存储单元不一定持续）

结点存储数据元素及直接后继的存储位置信息，两个域：数据域和指针域，指针域中存储的

信息称为指针或链，仅具有一种指针域故又称线性链表或单链表

链表的插入：先增长•条指针再修改原指针

头指针指向第一种数据元素的I存储位置，最终一种结点的指针为空（NULL）

链表表达措施及算法（P28）

单链表第一种结点前加一种头结点Head,其数据域可为空也可存储某些附加信息、（链长等）

假设p是指向线性表中i个元素（ai）的指针，则p->next是指向i+1个数据元索

在单链表中，获得第i个元素必须从头指针开始寻找，因此单链表是非随机的存储构造

线性表指逻辑构造，从抽象数据层面来说次序表和链表指物理存储构造

逻辑构造：离散、线性、层次、网状

应用见书算法

二、栈和队列

(-)栈的基本概念

栈(stack)是限定仅在表尾进行插入或删除操作的线性表

表尾为栈顶，表头为栈底，遵照后进先出原理((lastinfirston,LIFO),不含元素则

为空栈

操作：在栈顶插入(入栈)和删除(出栈)，栈初始化、判空、取栈顶元素（算法P45）

(-)栈的次序存储和链式存储

次序栈，即栈的次序存储构造是运用一组持续的存储单元依次寄存自栈底到栈顶H勺数据元

素，同步附设指针top指示栈顶元素在次序栈中的位置

初始栈时不应限定栈的最大容量，基本做法是先为栈分派一种基本容量，然后在应用过程

中，不够用再逐段扩大（算法P46）

（三）递归

栈与递归口勺实现：一种直接调用自己或通过一系列的调用语句间接地调用自己的函数，称

为递归函数

阶乘函数、2阶Fibonacci数列、Ackerman函数、3阶Hanoi问题（多阶呢？）（P54）

函数调用函数执行过程笔记（P56）

（四）队列

队列先进先出（firstinfirstout,FIFO）,队尾一端插入，队首一端删除元素（平常排队）

队列与栈均有八种基本操作（P59）,队列一般用链表实现，栈用次序表实现

双端队列（限定操作的队列）（P60）

（五）栈和队列的应用

链队列、循环队列（P60）,离散事件模拟（银行接待工作（P65））

（六）特殊矩阵的压缩存储

怎样存储矩阵的元，使矩阵的运算有效进行。高级语言常用二维数组存储阵元

面对如高阶矩阵，多值相似矩阵和多零元素矩阵进行压缩存睹节省空间

压缩存储：为多种值相似打勺元只分派一种空间，对零元不分派

值相似元素或零元素具有分布规律则称为特殊矩阵，反之为稀疏矩阵

详细应用与算法（P95）

三、树与二叉树

（一）树的基本概念

树是非线性数据构造，以分支关系定义的层次构造

树是n（n>=0）个结点的有限集

详见（P118）,基本术语（P120）

(-)二叉树

1.二叉树的定义及其重要特性：

二叉树是每个结点最多有两个子树的树构造。一般子树被称作“左子树”(leftsubtree)

和"右子树"(rightsubtree)«

性质:

1.

2.

3.

满二叉树：

完全二叉树：

4.

5.

2.二叉树的次序存储构造和链式存储构造

次序存储，用一组地址持埃的存储单元依次自上而下、自左至右存储完全二叉树上的结

点元素，即将完全二叉树上编号为i口勺结点依次存储在如上定义的一位数组卜标为i-1口勺

分量中。

123456789

链式存储，每个结点中至少包括三个域，［左指针，数据，右指针］,称作“二叉链表”

增长一种双亲指针域，则称作“三叉链表”详见P126-127

3.二叉树的遍历

遍历二叉树，每个结点均被访问一次，且仅有一次。在限定先左后右的访问序列后，有三

种遍历方式：光序（DLR）,中序（LDR）,后续（LRD）

P129算法6.1（波兰式）

层次遍历，无论那种遍历方式，对含n个结点的二叉树，时间复杂度都为O（n）,空间

复杂度也为O（n）o

4,线索二叉树的基本概念和构造

摘要：对于n个结点I均二叉树，在二叉链存储构造中6n+1（2n-（n-1））个空链域，运

用这些空链域寄存在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为

线索

概念：加上了线索的二叉链表称为线索链表，对应的二叉树称为线索二叉树（Threaded

BinaryTree）0

构造措施：

（三）树与森林

1.树的存储构造

链表构造：1.双亲表达法2.孩子表达法3.孩子兄弟表达法详见P135

2.森林与二叉树转换

左孩子右兄弟

3.树与森林的遍历

先序、中序遍历，详见P139

当以二叉链表做树口勺存储构造时，树的先序=二叉树先序、树的后序=二叉树中序

（四）树与二叉树日勺应用

1.二又排序树

二叉排序树（BinarySortTree）,又称二叉叁找树（BinarySearchTree）,亦称二叉搜

索树。

定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点H勺值均不不小于它的根结点的值：

<2）若右子树不空，则右子树上所有结点口勺值均不小于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

<4）没有键值相等的节点。

66

此图是BST此图是BST

查找:

环节：若根结点的关键字值等于查找的关键字，成功.

否则，若不不小于根结点的关键字值，递归查左子树.

若不小于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

2.平衡二叉树(AVL)

定义：它或者是一颗空树，或者具有如下性质口勺二叉树：它口勺左子树和右子树的深度

之差(平衡因子)口勺绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

平衡因子(bf)：结点的左子树的深度减去右子树H勺深度，那么显然-1<=bf<=1

83

4

图一，图二都是BST,但只有图一是AVLtree

3.哈夫曼(Huffman)树和哈夫曼编码

哈夫曼树是一类带权途径长度最短的树，又称最优树。

途径和途径长度概念：从树中一种结点到另一种结点之间的分支构成这两个结点之间H勺

途径，途径上的分支数目称为途径长度。

树的途径长度是从树根到每一结点的途径长度之和。

推广到一般状况，考虑带权结点：

结点的带权途径长度为从该结点到树根之间的途径长度与结点上的权值的乘积,树的

带权途径长度为树中所有叶子结点附带权途径长度之和，无作WPL=

△带权途径长度WPL最小的二义树称为最优二叉树或哈夫曼树

哈夫曼算法构造哈夫曼树（P145）

哈夫曼编码

前缀编码：设计长短不等的编码，任一字符的编码都不是另一种字符的编码的前缀

运用二叉树来设计前缀编码

约定左分支表达字符“0”

24

右分支表达字符“1”

则从根结点到叶子结点

的途径上分支字符构成

的字符串作为该叶子结

点字符的编码。

一般状况，当带有权值时，本质上就是设计一棵哈夫曼树，得到二进制前缀编码=哈夫

曼编码……算法详见P147

四、图

（-）图的基本概念

图是一种数据构造，加上一组基本掾作，构成的一种抽象数据类型详见（P156）

途中数据元素一般称为顶点，V是顶点日勺有穷非空集合；VR是两个顶点H勺关系集合，若

＜v,w＞属于VR,则＜v,w＞表达从v到w的弧，称v为弧尾（初始点），w尾弧头（终止点）

此时图是有向图，若＜v,w＞属于VR必有＜w,v＞属于VR,则以无序对＜v,w＞,表达v和

w口勺一条边，此时称图为无向图

完全图

有向完全图

边或弧很少（e＜nlogn）日勺图，称为稀疏图，反之为稠密图

边或弧所具有口勺有关数称为权，带权口勺图称为网

了图

连通图

（-）图的存储及基本操作

1.邻接矩阵法

用两个数组分别存储数据元素（顶点）的信息，和数据元素之间的关系（边或弧）的信息

算法详见（P161）

2.邻接表法

邻接表是图的一种链式存储构造。算法详见（P163）

（三）图的遍历

1.深度优先搜索（DFS）

类似于树的J先根遍历，可把图转化为树操作。图示及算法（P168）

2.广度优先搜索

类似于树的层次遍历，可把图转为树操作。详见（P169；

（四）图的基本应用

1.最小（代价）生成树（P173）

普里姆算法构造最小生成树:

克鲁斯卡尔算法构造最小生成树:

2.最短途径（P186）

在图中从顶点A到B,找一条所含边（弧）至少日勺途径，从A开始做广度优先搜索,

直到B结束，则称为最矩途径。

可推广H勺含权值H勺情形，此时最短途径度量是途径上权值之和

带权有向图：源点-＞终点

迪杰斯特拉算法:

3.拓扑排序

由某个集合上的偏序得到该集合H勺全序

偏序：若集合X上的关系R是自反的、反对称口勺和传递的，则称R是集合X上口勺偏序

关系；设R是集合上的偏序，假如对每个x,y属于X必有xRy或yRx,则称R是集

合X上的全序关系。洋见（P180）

4.关键途径（最长途径）（P183）

五、查找

(一)查找的基本概念

在某些(有序口勺/无序口勺)数据元素中，通过一定的措施找出与给定关键字相似的数据元

素H勺过程叫做查找。也就是根据给定的某个值，在查找表中确定一种关键字等于给定值的

记录或数据元素。

(-)次序查找法

1.次序查找：

关键：从数据的第一种元素开始，依次比较，直到找到目的数据或查找失败。

1.从表中的第一种元素开始，依次与关键字比较。

2.若某个元素匹配关键字，则查找成功。

3.若查找到最终一种元素尚未匹配关犍字，则查找失败。

2.时间复杂度：次序查找平均关键字匹配次数为表长口勺二分之一，其时间复杂度为0(n)。

3.次序查找的评估：次序查找时长处是对表无规定，插入数据可在0(1)内完毕。缺陷是时

间复杂度较大，数据规模较大时，效率较低。

(三)折半查找法

算法规定：折半查找规定线性表必须采用次序存储构造，并且表中元素按关键字有序排列。

查找过程：首先，假设表中元素是按升序排列，将表中间位置记录日勺关键字与查找关键字比

较，假如两者相等，则查找成功

否则运用中间位置记录将表提成前、后两个子表，假如中间位置记录的关键字不

小于查找关键字，则深入查找前一子表，否则深入查找后一子表。

反复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，

此时查找不成功。

(四)散列(Hash)表

哈希表定义：是根据关键码值(Keyvalue)而直接进行访问的数据构造。也就是说，它

通过把关键码值映射到表中一种位置来访问记录，以加紧查找的速度。这个映射函数叫做散

列函数，寄存记录的数组叫做散列表。

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包括该

关键字的记录在表中H勺地址，则称表M为哈希(Hash)表，函数f(key)为哈希(Hash)函数。

基本概念：

若关键字为k,则其值寄存在f(k)的存储位置上。由此，不需比较便可直接获得所查记

录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不一样的关键字也许得到同一散列地址，即k"k2,而f(k1)=f(k2),这种现象称为

冲突(英语：Collision)o具有相似函数值口勺关键字对该权列函数来说称做同义词。综

上所述，根据散列函数f(k)和处理冲突的措施将一组关键字映射到一种有限的持续的地

址集(区间)上，并以关犍字在地址集中的“像”作为记录在表中的存储位置，这种表便

称为散列表，这♦映射过程称为散列造表或散列，所得口勺存储位置称散列地址。

若对于关键字集合中的任一种关键字，经散列函数映象到地址集合中任何一种地址的概

率是相等的，则称此类散列函数为均匀散列函数(UrdfonrHashfunction),这就是使

关键字通过散列函数得到一种“随机的地址"，从而减少冲突°

(五)字符串模式匹配

子串的定位操作是要在主串S中找出一种与子串T相似的子串，一般把主串S称为目

的，把子串T称为模式，把从目的S中查找模式为T的子串的过程称为“模式匹配”.

1.Brute-Force算法的设计思想

Brute-Force是一般的模式匹配算法。将主串S的第1个字符和模式T的第1个字

符比较，若相等，继续逐•比较后续字符：若不等，从主用的下一字符起，重新与模式

的第一种字符比较，直到主串的一种持续子串字符序列与模式相等，返回值为S中与

T匹配口勺子序列第一种字符的序号，即匹配成功：否则，匹配失败，返回值0,

2.Brute-Force完法的特点:

每次碰到匹配不成功的状况，指针i都要移到本次匹配的开始位置的卜一位，称

这样的指针移动为回溯。指针的回溯越多，简朴模式匹配的执行次数越多

Brute-Force匹配算法的最坏时间复杂度为O(n*m),一般状况下BF算法口勺时间

复朵度为O(n+m)

3.KMP算法的改善

每当一-趟匹配过程中出现字符比较不等时，不需回溯指针i,而是运用已经得到的

“部分匹配”的成果将模式向右'滑动”尽量远的一段距离后，继续比较

KMP算法的时间复杂度可以到达O(m+n)

4.KMP和法的设计思想

假设以指针i和j分别指示主串和模式中正待比较的字符，令i的初值为0,j口勺初

值为0

若在匹配过程中，Si=Pj,则i和j分别增1,否则i不变，而j退到nextfj]的位置再比较,

若相等，则指针各自增1,否则j再退到下一种next值的位置，依次类推

若令next[j]=k,则next[j]表明当模式中第j个字符与主串中对应字符失配时，在模式中需重

新和主串中该字符进行比较H勺字符H勺位置

模式串的next函数定义为

0当j=1

<Max{k|1<k<j且'PF2・・・Pk.产Pj.k+iPj-k+2…Pj，}

next[j]=

当此集合不空时

11其他情况

例如:J12345678

模式串abaabcac

next[j]01122312

4z=2

主串acabaabaabcacaabc

第一趟

模式ab

fj=2〃E[2]=1

Ii=2

主串acabaabaabcacaabc

第二趟

模式a

f;=1〃ezz[l]=O

|t=3-*|:=8

主串acabaabaabcacaabc

第三趟

模式abaabc

fJ=1----►}-6〃=46]=3

It=8----►1:=14

主串acabaabaabcacaabc

第四趟

模式(ab)aabcac

f>=3--*t>=9

利用模式的next函数进行匹配的过程示例

（六）查找算法的分析及应用

六、排序

(一)排序的基本概念

将杂乱无章的数据元素，通过一定口勺措施按关犍字次序排列的过程叫做排序。

分内部排序利外部排序，若整个排序过程不需要访问外存便能完毕，则称此类排序问题为

内部排序。反之，若参与排序的记录数量很大，整个序列的排序过程不也许在内存中完毕，

则称此类排序问题为外部排序。内部排序口勺过程是一种逐渐扩大记录的有序序列长度的过

程。

(-)插入排序

直接插入排序基本思想是每一步将•种待排序的记录,插入到前面已经排好序的有序序列

中去，直到插完所有元素为止。

有序:待排序

427865

<00

27865

对待排序的序列逐个插入，直到插完为止

©

所有元素全部插入，排序完成

23456

（三）气泡排序

冒泡排序口勺基本思想是，对相邻的元素进行两两比较，次序相反则进行互换，这样，每一

趟会将最小或最大的元素“浮”到顶端，最终到达完全有序

相邻元素两两比较，反序则交换

第一轮完毕，将最大元素9浮到数组顶话

31427865

1▲▲▲上

同理,第二轮将第二大元素8浮到数组顶端

排序完成

（四）简朴选择排序

简朴选择排序是最简朴直观的一种算法，基本思想为每•趟从待排序的数据元素中选择最

小（或最大）H勺一种元素作为首元素，直到所有元素排完为止，简朴选择排序是不稳定排

序。

在算法实现时，每一趟确定最小元素的时候会通过不停地比较互换来使得首位置为目前

最小，互换是个比较耗时的操作。其实我们很轻易发现，在尚未完全确定目前最小元素之

前，这些互换都是无意义的。我们可以通过设置一种变量min,每一次比较仅存储较小元

素的数组下标，当轮循环结束之后，那这个变量存储的就是目前最小元素的下标，此时再

执行互换操作即可。代码实现很简朴，一起来看卜。

（五）希尔排序

希尔排序是基于插入排序的，首先回忆一下插入排序，假设插入是从左向右执行的，待插入

元素口勺左边是有序的，且假如待插入元素比左边口勺都小，就需要挪动左边的所有元素，如下

图所示：

图1和图2:覆入右边的temp柱需要oute厢己位左边的五个柱子都向右挪动

如图3所示,相比插入排序，格尔排序是这样做的：对回定问国的元森侬插入排序，然后减小间国,重

要做插入排序，宜到间隔减小为鼠

m3和蜃4:outer<2$#Dinner-h<iz^e¥^?8AJ1f)?

效汨量大的图形看这个过程更容易形象地把娃算法特点，妇图5和6，忌元森数量等于100:

图5和图6：间隔分别为40和13执行完插入排序后的效果

相比简朴插入排序，大间隔地做插入排序有两个好处：

-、大间隔直接导致需要挪动的数据稀少，且数据挪动的效率高，图5中•次挪动可以

跨越40个位置：

二、通过前一步大间隔的插入排序后，整个数组从整体上粗略地看己经有了明显的次序,

后一步小间隔H勺插入排序时，一部分操作是不需要挪动数据的，再次减少了挪动数据的次数。

间隔的序列：间隔的常用序列,通过递归表达：h=3*h+l«(1,4,13,40,121...)

希尔排序的效率：“没有理论上分析希尔排序H勺效率的结论，多种基于试验的评估，估计它

的时间级从0(阴(3/2))到O(N，(7/6))”-⑴。

(六)迅速排序

迅速排序算法日勺方略是这样H勺：苜先把数组用某个值分为两个子数组，且称这个值为分组值，

一种子数组中的元素均不不小于分组值，另一子数组则均不小于等于分组值，这里日勺子组内

并不排序；然后，再分别对两个子组进行再分组，反复递归这个过程，直到最终每两个元素

作为一组进行再分组，整个数组就排好序了。

分组过程详细如下：同步从左往右和从右往左扫描数组，记扫描标识位为LP和RP。在

LP一边，若发现元素不不小于分组值则跳过(即向右移动一位检查下-•种元素)，否则等

待RP的扫描；RP若发现元素不小于等于分组值跳过，直到找到不不小于分组值的元素，然

后LP和RP位置的元素互换，反复这个过程，直到LP和RP相遇。

如图7,8所示，以11号元素为分组值，LP停在。号位置，RP跳过10号，停在图7

中的9号位置(粉色柱)，然后0号和9号互换，后续反复这个过程。

Enteringquicksort。；willpartition(0-11)

图7和屋8：以11号柱作为分组值，0号和9号柱子将交换

至9：100个元素的数组经过两次分组后的效果

分组值的选择，可以想见，理想的分组值应当是待分组元索的中值，这样分组后子组在

数量少几乎是二分之一对二分之一，不过找中值无疑增长了算法的工作量。图7中采用了更

简朴的方式，直接选数组最右边的元素为分组值，分组结束后，再把这个值互换到LP和RP

相遇口勺位置，假如初始数组是从大到小排序打勺，这种状况3选择最右边的元素作为分组值,

其辨别度就很差了。更好用的措施是所谓的取首尾中三项数据的中值或者平均值。

通过对算法过程的描述可知，其时间更杂度应当为：O(N*logN),比简朴排序和希尔排

序都要快。

(七)堆排序

堆排序是运用堆这种数据构造而设计的一种排序算法，堆排序是一种选择排序，它的最

坏，最佳，平均时间豆杂度均为O(nlogn),它也是不稳定排序。首先简朴理解下堆构造。

堆是具有如下性质的完全二叉树：每个结点的值都不小于■或等于其左右孩子结点的值，

称为大顶堆；或者每个结点时值都不不小于或等于其左右孩子结点的值，称为小顶堆。如下

图：

787

同步，我们对堆中的结点按层进行编号，将这种逻辑构造映射到数组中就是下面这个样子

012345678

po45402025353010

该数组从逻辑，讲就是一种堆构造，我们用筒朴H勺公式未描述一下堆的定义就是：

大顶堆：arr[i]>=arr[2i+l|&&arr(i]>=arr[2i+2]

小顶堆：arr[i]<=arr[2i+l|&&arr[i]<=arr[2i+2]

堆排序的基本思想是：招待排序序列构导致一种大顶堆，此时，整个序列的最大值就是

堆顶的根节点。将其与末尾元素进行互换，此时末尾就为最大值。然后将剩余n：个元素重

新构导致一种堆，这样会得到n个元素的次小值。如此反复执行，便能得到一种有序序列了

(八)基数排序

基数排序(RadixSort)基本思想是：将整数按位数切割成不一样的数字，然后按每个位数

分别比较。

详细做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从

最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完毕后来，数列就变

成一种有序序列。

基数排序图文说明

基数排序图文说明

通过序又描组(53,3,542,748,14,214,154,63,616)