等级考基础数据结构

等级考基础《数据结构与算法》东华大学计算机学院孙莉2016年2月1数据结构基本概念1.1数据结构的研究内容：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。归纳为三部分：逻辑结构、存储结构和运算集合。

存储结构的二种类型:

顺序存储结构—通过在存储器中的相对位置，表示数据的逻辑结构。非顺序存储结构（链式存储结构）

--由指针表示数据间的逻辑关系。1.2常用的数据结构(1)线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队

(2)树形结构：结构中的数据元素之间存在着一对多的层次关系。---非线性结构

(3)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。---非线性结构1．4算法与算法分析1.3算法与算法分析

算法的概念

算法是对特定问题求解步骤的一种描述

算法的基本特征：

1）可行性：组成算法的操作必须能够在计算机上实现。2）确定性：算法的每一步操作必须清晰无二义性。

3）有穷性：算法必须在有限步内结束；

4）有足够的情报：0个或多个输入；1个或多个输出；

算法描述的方法很多，如自然语言、框图、类C等例:求两个正整数m，n中的最大数MAX的算法（1）若m>n则max=m

（2）若m<=n则max=n

1、正确性：(1)没有语法错误；

(2)对于几组输入数据能够得出满足要求的结果；

(3)对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。

(4)对于一切合法的输入数据都能产生满足要求的结果。2、可读性：便于阅读、理解、调试、修改；3、健壮性：对不合法的输入能作出正确的反映与处理；4、高效性：执行时间短（时间复杂度）、需求存储空间省（空间复杂度）1.4评价算法标准

时间复杂度T（n）

以求解问题的基本操作的执行次数作为算法时间的度量。

1．4算法与算法分析O（n3）

称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；

例n阶矩阵相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

For(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]}

乘法加法执行次数均为n3

矩阵相乘的基本运算：乘法加法；

1．4算法与算法分析

算法空间复杂度

用执行算法所需的内存空间的大小作为算法所需空间的度量。

设执行算法所需的内存空间是问题规模n的某个函数g(n),则算法空间复杂度记作：S（n）=O(g(n))表示算法内存空间的增长率与g(n)的增长率相同例计算

解法1先计算x的幂,存于power[]中,再分别乘以相应的系数

#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];

for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}问题规模为n,算法时间复杂度:O(n)空间复杂度：O(N)2线性表

线性表是最简单、最常用的数据结构。栈、队列是特殊的线性表--线性结构

线性表是n个数据元素的有限序列，通常记作（a1,a2,a3,…,an

）。

姓名电话号码

蔡颖63214444

陈红63217777

刘建平63216666

王小林63218888

张力63215555...2.1线性表的概念例、英文字母表（A,B,C,D,EZ）。

某单位的电话号码簿。线性表的逻辑结构

2.1线性表的概念设A=（a1,a2,...,ai-1,ai,ai+1,…,an

）是一线性表，1）同一线性表中的元素必须是同一类型的；2）在表中ai-1

领先于ai，ai

领先于ai+1

，称ai-1

是ai

的前件，ai+1

是ai

的后件；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an用顺序存储结构存储的线性表——称为顺序表

2.2线性表的顺序存储和实现线性表（a1,a2,a3,...an）的顺序存储结构

2.2线性表的顺序存储和实现设线性表中每个数据元素占t个存储单元，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：

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

t其中Loc(a1)基地址，随机存取顺序存储结构、随机存取结构a1a2ai-1aiai+1ant个单元Loc(a1)Loc(ai)2.2线性表的顺序存储和实现

插入位置移动元素个数

1

n

2

n-1

in-i+1

n1

n+10

插入算法时间复杂度分析

算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。a1a2ai-1aiai+1an01i-1i-2n-1..2.娱2线性蜘表的逐顺序键存储物和实泳现由此么可见氧在尸顺序膛表中细插入娱一个锋元素旅，锤平均零要移蜘动表惹的一掀半元难素。剖表虫长为n的顺默序表朴，插遗入算堆法的搬时间本复杂央度为O（n）假设塘在线膛性表滑的任抱何位程置插职入元温素的经概率汽相同敢，即pi副=愚1/绿(n膜+1胖)设pi为在奖第i个元裹素之侧前插数入元匙素的贷概率素，在露长度惠为n的顺尺序表溪中插尝入一竞个元歼素，驼所需蓝移动牙元素废个数迁数学较期望都值为提：删除碗算法坏时间尝复杂述度分取析假设骑在线发性表慨的任禾何位锻置删烦除元烧素的偷概率浪相同葱，即pi岸=灶1/旗n删除所需财移动渣元素厅个数帅的数列学期斧望值扑：2.听3线性句表的往链式丛存储申和实驻现线性炎表的放链式揪存储胁结构散是用到一组代任意拢的存串储单怒元存服储线脖性表盲的各娘个数固据元鸡素。为了孤表示杜线性轮表中逃元素扬的先武后关槐系，蓄每个顾元素稠除需醋要存谢储自净身的定信息物外，螺还要州保存掌直接旱前趋延元素你或直先接后脂继元糟素的攻存储汪位置议。ai+1a1ai-1a2aian线性撑链表蛇的概衔念1线性澡链表2.刃3挪.棒1线性侦链表a4a3a1a2

0101010241014101010121014101610181020102210241026用链麻表存相储线冈性表寻时，忠数据坑元素驴之间梦的关籍系是肿通过保存促直接衔后继服元素屯的存公储位极置来莲表示谣的ai-1aia2a1ai+1nan结点括：数据佳元素福及直幕接后修继的蜡存储请位置横（地丢址）敲组成纠一个鸽数据直元素病的存占储结卫构，泉称为宰一个盗结点钢；结点爸的数妹据域剩：保存邻数据浅元素;结点过的指蕉针域怒：保存婶数据缓元素乱直接低后继妻的存森储地凑址;线性爹链表师有关贪术语2.勿3体.许1线性酬链表存储掉数据睡元素存储摊后继蛇结点存储吹地址结点数据域指针域2.马3涌.纤1线性黎链表头指部针：存放椒线性望链表闷中第狗一个崖结点疏的存跳储地拾址;空指著针：不指矛向任侍何结勒点，贵线性赶链表仇最后辟一个艘结点站的指喷针通慨常是睛空指铸针;头结亚点：链表水的第船一个抛元素禽结点轮前的皮附加宇结点疼；he杏ad是头餐指针ai-1aia2a1ai+1nan头结淹点空指酒针he耀ad线性棉链表锣的每代个结珠点中鞭只有统一个共指针汤域故也旗称为单链除表插入转结点(存a)q-猴>d圈et冻a=孤‘a针’;q-释>n乱ex师t=南p-什>肚ne奥xt移;p-惊>嫂ne村xt脚=匹q;he臂adzyxpyxzphe旬adaq4）删除房诚结点q=策p-喷>n尽ex笛t;p-粪>室ne颜xt帐=冰q-公>姓ne窑xt泡;fr荷ee雾(q徐);he剩adzyxqyxzqhe竖adpp随机存储武结构道、顺户序存取早结构1循环衣链表循环蜂链表蓄是将议线性霸链表疯的最荣后一居个结殃点的间指针馅指向骄链表倾的第左一个卧结点霉（首圾尾相即连的察单链划表）循环眠链表(a短)非空换表贱（b）空穷表headheada1an2双向潜链表3栈和暗队列栈是炕限定司仅能点在表将尾一颠端进面行插膊入、终删除性操作萄的线性桥表（a1,框a2,肢..浆.卖,喇ai秀-1,挺ai,舍ai+丝式1,杰…,惠an）插入删除什么亭是栈?3.耳1栈3.肉1栈将表般中允模许进赌行插搏入、仆删除娱操作陕的一早端称速为栈吃顶(T糊op感)，栈顶态的当触前位所置是略动态辛变化摔的，坐由一坡个栈摇顶指种针指恳示其遣位置犹。表的跌另一定端称作为栈核底(B幅ot傲to献m)。当栈井中没纽奉有元竞素时筐称为块空栈鉴。栈的凤插入秋操作咱称为霞进栈搏或入连栈，友删除额操作太称为妻出栈沸或退贴栈。3.馋1栈栈的坝示意宜图出栈进栈栈的选特点后进尿先出第一垦个进午栈的鹅元素盐在栈限底，宫最创后一骂个进解栈的软元素氏在栈肃顶，第一撇个出答栈的肆元素劫为栈棉顶元搭素，最后脂一个量出栈残的元野素为虑栈底皂元素栈顶栈底ana2a1B例:如果趣进栈油序列役为e1荣,e惠2,迷e3抖,e削4，则要可能宰的出风栈序突列是?A)获e程3,鼻e1低,e扇4,皮e2柄B工)推e2搜,e冲4,闷e3辽,e抱1艳C)堪e躁3,看e4邪,e改1,缘瑞e2梢D挽)任意监顺序3．2队列什么工是队急列队列唯是限浆定仅石能在煤表头销进行片删除请，表瓦尾进葵行插固入的线性纱表（a1,帆a2,央..嘉.铃,纠ai讨-1,瘦ai,圈ai+盆1,分…,辛an）插入删除3．3队列a1a2a3an入队浊列队头队尾出队钉列队汤列介的陕示邪意累图队列感的特窝点先进毯先出第一响个入邪队的墓元素亿在队乳头，拥最伐后一惕个入概队的研元素灭在队避尾，第一纤个出冻队的姜元素扫为队凑头元棵素，最后丘一个徒出队借的元叮素为睛队尾溪元素re殖arfr召on鞠tJ1re泛arfr赵on扣tJ2（a)空队饭列(b安)J胞1,丑J2相继速入队提列(c未)J床1出队(d档)J马3,典J4叼,巧J5和J6相继饮入队盗之后,J摇2出队re薪arfr圆on俱t0123453.撕3队列re贡arfr舞on震tJ5J4J3fr胀on古t,卖re郑ar为整捞数

又有J7入队,怎么办？

？J2J63.布3队列3币.循环些队列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b怖)队空(a估)队满J7rear3.宣3队列判分浴队空筛、队全满方变法：1）另鲁设一丝式个标反志S以区权分队蔑空、胶队满次。S=慨0队空绝：fr方on毅t=某re管ar赌;S=打1队满后：fr脊on滴t=软re威ar俊;2)或少兄用一车个空史间Re刷al蓝+1促=f荷ro证nt为满栈、扛队列奇的存谨储结墨构？fr系on酸t540312J6J7J8J4J5（c）rear4树和赔二叉搁树4．1树的盏定义树是n个结弹点的种有限寨集合T，当n=辽0时，勇称为姨空树炉；当n>尿0时，T满足福如下壤条件纺：在捏任一巨棵非肥空树更中：访（1）有域且仅多有一添个称既为根赶的结蚀点。爆（2）其渔余结劣点可吼分为M个互缺不相销交的免子集顷合，阁而且响这些本子集衫中的蜡每一窝个本互身又董是一周棵树评，也丢称为恳根的禾子树如。JIACBDHGFEKLM树的贝实例颠树呜可表拉示具猪有分双枝结睡构关鄙系的息对象例1．家蹈族族范谱设某堆家庭侵有13个成案员A、B、C、D、E、F、G、H、I、J、K、L、M，他惯们之询间的好关系发可用砍树表财示：JIACBDHGFEKLM计算链机中功树是赵常用介的数报据组喘织形荣式尽管姜有些届应用葱中数间据元爱素之药间并吃不存代在分哲支结亮构关宗系，很但为贝了便座于管休理和撕使用肾数据蛋，将术它们连用树带的形腥式来楚组织画。例2计算飞机的氧文件驳系统酿不捞论是DO尾S文件享系统沈还是wi糟nd亚ow文件和系统磁，所李有的俱文件纺都是寇用树壤的形戴式来面组织程的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C盘树的炮基愚本术拾语树的皮结点荐：包绑含一沫个数酬据元奸素及心若干崖指向子俊树的适分支星；孩子码结点黎：结目点的膊子树芬的根嗽称为凉该结略点的孩猾子，B、C是A的孩府子；双亲喜结点懒：B结点江是A结点洒的孩秒子，填则A结点渔是B结点术的双微亲；兄弟史结点盖：同沟一双乓亲的需孩子错结点瓦，H、I、J互为妖兄弟责；JIACBDHGFEKLM树的栽基不本术破语结点弯的层叮次：罪根结套点的啊层次胃定义家为1；根焦的孩犬子为留第二卡层，既依此猫类推傍；它树的体深度堤：树助中所雨有结土点的守层次隆的最驳大值障结扎点的瞧度：竞结点评子树辨的个狭数帝树的雁度：娱树中畅结点裤度的伴最大香值。幅叶间子结殿点：块度为0的结诱点；挽分胖枝结求点：帐度不兄为0的结葬点；JIACBDHGFEKLM4.搂2二叉元树二叉窗树的侍定义二叉东树：烤或您为空壁树，他或由悠根及背两颗花互不沃相交凝的左迁子树月、右帝子树烈构成验，并像且左雪、右切子树撇本身围也是称二叉罩树。

A

F

G

E

D

C

B二叉糊树中混每个迅结点佣最多琴有两呢个子左树；使既：代每个绘结点选度小怪于等偏于2;左、季右子晚树不泰能颠盖倒——有序佛树;(a伸)、(b卡)是不臂同的榜二叉粒树，(a造)的左胳子树协有四市个结允点，(b忙)的左乒子树接有两巨个结朽点(a抹)(b举)

G

E

D

C

B

A

F

G

E

D

C

BFA二叉奸树的青基本栏形态φ(a脑)空树(b酸)只有历根(c泊)右子迹树空(e陪)左子坚树空(d丛)左、当右子时树非订空二叉睁树的片性质性质1:在二清叉树挪的第i层上公至多汗有2i-朋1个结验点(i夸≥1植)。砌性质2:深度损为k的二沫叉树仗至多晌有2k-1个结奖点（k≥邻1）。性质3:对任掠意一否棵二摆叉树T，若运叶结楼点数梅为n0，而鞋其度喘为2的结畅点数市为n2，则n0=n2+1。二叉凝树存储推结构--胸-二叉泪链表二叉捏链表料中每住个结志点包摄含三淹个域卸：数谦据域骡、左右指针奇域、析右指忙针域

A

F

E

D

C

B二叉内链表蓄图示∧

D

AB∧C

∧∧E∧∧F∧二叉栋树的配遍历遍历：按某让种顺钞序访标问二除叉树早的每女个结拍点，狭而且碌每个钩结点惰仅被龄访问翠一次摊。访问倾：含义脆很广怀，可秆以是驴对结词点的珍各种低处理，如董修改亏结点邻数据漆、输组出结乏点数萝据。二叉齿树的底遍历宿方法二叉腐树由撞根、欠左子采树、惹右子蔬树三生部分筛组成二叉鱼树的滥遍历可以叫分解条为：改访问义根，镜遍历左子孤树和遍历右子钳树令：L：遍历仰左子覆树T：访问惩根结自点R：遍历顶右子抖树约定同先左尤后右,有三新种遍迎历方教法：TLR前序扔遍历饭、LTR中序惹遍历、LRT后序耕遍历惭。

A

F

G

E

D

C

B前（算先）射序遍缘瑞历（TLR）若二尝叉树穗非空援（1）访央问根率结点闯；（2）前微（先羽）序荐遍历腊左子识树；懂（3）前钓（先他）序培遍历颠右子新树；前（嫂先）西序遍烛历序穷列：A,B,柜D,E,G茫,C,F例：滨先序遍么历右估图所陕示的络二叉尊树（1）访示问根乎结点A（2）前宪（先塌）序傅遍历贞左子返树：缩慧即按TLR的顺尘序遍鹅历左子帅树（3）前唇（先啦）序鸡遍历贺右子逗树：赞即按TLR的顺专序遍时历右子怕树

A

F

G

E

D

C

B中序碎遍历参（LTR）若二颂叉树榨非空侧（1）中优序遍鸣历左跨子树蓄（2）访么问根恼结点（3）中喇序遍岛历右符子树中序恼遍历妹序列：D,挂B,化G,E,A,C,醒F例：中序次遍历桐右图薯所示晃的二羽叉树（1）中饶序遍酿历左药子树秋：即跟按LTR的顺用序遍游历左子笨树（2）访汽问根懒结点A（3）中镰序遍胞历右辱子树此：即漂按LTR的顺惜序遍璃历右子凉树

A

F

G

E

D

C

B后序报遍历近（LRT）若二姓叉树晓非空贴（1）后绘序遍扫历左伏子树赌（2）后应序遍皆历右奥子树（3）访码问根馒结点后序呈遍历荣序列决：D,纸G,E,B坡,F,墓C,A例：惜后序遍烧历右鸭图所浸示的苏二叉殊树（1）后辜序遍页历左绍子树予：即巧按LRT的顺熔序遍容历左子易树（2）后惰序遍双历右皇子树起：即欺按LRT的顺隙序遍胞历右子汪树（3）访脚问根剂结点A

A

F

G

E

D

C

B例:已知候一棵稿二叉沿树前杨序遍所历和跑中序竟遍历些分别舟为AB幼DE辫GC锯FH和DB帖GE圣AC恭HF，则森该二厕叉树爱的后绪序遍椅历为?A)宽G悉ED日HF植BC虚A速B采)蒸DG敢EB眨HF趟CA齿C焦)蜘AB健CD缴EF悔GH尽D)及A别CB帽FE勺DH匆GB5查找5.训1查找歇的基粥本概泥念查找捐（列客）表尊：由乖同一深类型壁的数续据元皱素（霉或记张录）纲构成侦的集刻合，终可菊利用奶任意以数据秩结构竞实现弯。逼关键洪字：岗数据热元素竭的某休个（币几个渣）数牲据项拌的值寻。如础果一悼个数黑据项硬可以跟唯一晃标识宇列表泽中的迷一个世数据晋元素横，录则称郊其为焦关键刑字。查找纱：宅根据吼给定膛的关拼键字零值，院在特锁定的票查找沫（列截）表垦中确卷定一鹊个其烈关键秩字与变给定雾值相鸭同的舱数据梦元素裹，并抬返回境该数旧据元拳素在撑列表辣中的单位置到。5．2线性撇表的晚查找5.袄2.闯1顺序姿查找--宝-最简召单的纽奉查找薪方法顺序班查找逮的基闲本思壤想从表撞的一广端开政始，垂顺序荣扫描谦线性首表，俗依次傍将扫掠描到灾的结扩点关餐键字皱和待科找的盗值Ｋ脏相比膨较，吨若相马等，盛则查闹找成蚁功，挖若整垫个表侍扫描肿完毕平，仍辈末找匹到关姨键字龙等于远Ｋ的柜元素搞，则争查找竭失败规。顺序音查找衰既适朱用于凭顺序纳表，离也适寨用于享链表柿。用顺饿序表狂，查末找可说从前肥往后绒扫描桶，也造可从株后往绳前扫近描，但若洋采用扭单链旱表，驱则只圾能从庙前往柜后扫战描。顺序俗查找蛋的表茄中元及素可我以是芹无序掏的。顺序绳查找兆算法息的性准能。才假设查列表巴长度报为n，那旅么查裹找第i个数错据元疼素时法需进沸行n-改i+室1次比趋较，恰即Ci=n隙-i仅+1。又曲假设店查找走每个友数据纠元素祸的概雹率相碍等，盾即Pi=1腔/n，闸则顺辞序查己找算往法的哲平均恼查找撞长度她为：顺序馅查找输的特东点顺序坐查找偶的优庭点是题算法缺简单虹，对侍查找躬表结备构无塞任何述要求略，无标论是怀用向脉量还窗是用谁链表鄙来存作放结料点，烈也无土论结废点之建间是辽否按男关键偶字有碧序或摊无序醉排，达它都殖同样稼适用慎。顺序押查找束的缺撤点是馆查找阻效率制低，驳当n较大躺时，索不宜污采用酷顺序转查找。5.急2.域2二分查找盆（折伸半查画找）1.二分沾查找扇的基参本思竟想要求佣表中剑元素港按关滋键字贩有序(升序就或降擦序)。假同设表任中元毙素为源升序你排列振。二分言查找菜的基声本思拥想是郑：首先础将表纱中间计位置毒记录再的关突键字热与查拌找关朝键字其比较联，如花果两磨者相懂等，扒则查雹找成战功；否则压利用态中间击位置涌记录浪将表弯分成毅前、址后两蒸个子扫表，皂如禽果中胶间位吵置记困录的叔关键沃字大尽于查揭找关叮键字芹，则盟进一仁步查锤找前度一子饱表，竿否则烟进一批步查疗找后践一子牛表。重复思以上帽过程稠，直间到找陕到满喘足条蜂件的拼记录杂，使预查找忍成功尝，或抄直到壁子表中不存盈在为陶止，优此时割查找父不成姓功。例如舱，假骨设给认定有卡序表进中关谣键字语为：{0森5,氧13屈,1担9,粉21粮,3产7,氧56柳,6浊4,岩74艳,8丛0,递88口,9乖2}，查首找K=帽21的情菠况：0扮1古2征3宣4株5盆6绪7拥8雁9仪1天00珠1盗2校3相4称5馒6球7淋8漏9嫂1煎00顺1希2丧3并4草5皂6术7六8除9牢1灯00只1唐2结3徒4找5茎6元7孟8允9昆1梨03.二分欠查找践的性票能分懂析二分君查找田的过匀程可投以用粥二叉统树来夸描述劈燕。把肢当前凤查找森区间浓的中械点作例为根沃结点纷，左蹲子区么间和宵右子矮区间帐分别稀作为卷根的蓝左子鹊树和影右子事树，鉴左子沙区间仰和右秃子区假间再冈按类曾似的霸方法租，由龟此得欲到的欢二叉医树称艳为二蠢分查号找的灿判定兔树。例如取，给差定的好关键镜字序呀列05爆,1材3,驳19舟,2窃1,拳37杏,5牧6,德64蒜,7断4,靠80滚,8促8,泼92，的棒判定覆树。0瘦1获2抓3迟4折5晕6版7轧8雅9鉴1剩0在长颤度为n的有却序线欧性表罚中进马行二西分查血找。男最坏笔的情参况下洽，需蔬要的拥比较岁次数浑为lo廊g2n6排序6．1基本提概念6.差1.劲1排序负定义排序帜就是挠把一踏组记满录（尾元素宇）按掌照某危个域记的值棍的递以增或捉递减球的次千序重颠新排疾列的娱过程店。(按学董号的语递增)表7-兽1学生截档案虑表学号姓名年龄性别99001王晓佳18男99002林一鹏19男99003谢宁17女99004张丽娟18女99005周涛20男99006李小燕16女在没无有声轨明的喂情形救下，蝴所有恨排序傻都按奋排序耐码的愉值递钱增排矛列。排序插入挠排序细（直虽插排省序、在希尔码排序晚）交换竟排序涛（冒那泡排赶序、兔快速糟排序膊）选择日排序培（胡直选谨排序贝、堆啊排序往）归并屈排序刻（二按路归难并排秤序）6．2插入应排序6.彼2.例1直接吧插入弄排序1．直两接插鸭入排愧序（St穴ra搞ig狠ht豆I术ns园er乒ti爆on株S庭or苍ti症ng）基本盐思想售：把n个待镰排序求的元区素看跨成一凉个有辩序表茅和一陷个无余序表窜，开始桥时有恨序表仍中只恭包含选一个赢元素待，无落序表厅中包缠含有n-陕1个元店素，排序浪过程联中每唤次从免无序材表中门取出戏第一活个元优素，颈把它跪的排伍序码依次点与有院序表纠元素已的排迁序码东进行浅比较拜，将问它插义入到梅有序亮表中的适爷当位救置，散使之瓦成为翠新的撇有序铁表。例如浆，n=定6，数念组R的六缴个排趴序码漠分别尾为：17，3，25，14，20，9。它错的直咐接插阳入排恐序的蝴执行堆过程乔如图7-决1所示劲。3．直垂接插裤入排标序的勾效率国分析直接焰插入册排序豪算法溪十分峰简单绸。空间:只需探要一锅个元贝素的乓辅助兆空间绍，用察于元缎素的沈位置续交换茅。时间:外层抖循环锈要进浴行n-钱1次插奏入，痰每次倡插入援最少番比较悟一次梁（正丑序）压，移舍动两午次；争最多帮比较i次，删移动i＋2次（胡逆序汤）（i=毅1，2，…，n-绍1）。直接四插入芝排序爹的时搅间复贝杂度贷为O（n2）。最坏姥情况帆比较n(滋n-奴1)络/26.边2.榆2希尔顾排序希尔黎排序(缩小跳增量宴排序):伍19院59年由D.泪L.令Sh您el臂l提出洪来的驻。基本巡寿思想好：先笋将整大个待趋排元弯素序帆列分体割成澡若干腰个子手序列研（由配“诱增量殊”确问定）火分别茅进行录直接兼插入钉排序硬，待浇整个浅序列摘中的弟元素信基本押有序晓（增针量足禽够小付）时负，再责对全拆体元事素进呼行一俩次直刻接插悉入排湖序。依因为既直接室插入需排序再在元椒素基议本有筋序的健情况市下（旗接近坏最好肌情况尝），衬效率谁是很拒高的仙。例如马，n=翠8，数罗组ar疑ra丘y[通]的八场个元饱素分壁别为剃：91，67，35，62，29，72，46，57。下顽面用州图7-逐2给出恩希尔责排序使算法测的执枣行过脊程。希尔服排序绣的效摄率分蓬析与增资量有魄关，最坏爱情况壤，希装尔排粉序的攻时间席复杂疯性在O（nl觉og2n）。6．3交换泰排序6.即3.齐1冒泡貌排序基本溉思想:对待渴排序堵序列银从后消向前粪（从面下标昆较大眠的元山素开既始）王，依旋次比伐较相险邻元怎素的帝排序坏码，给若发雨现逆吃序则氏交换陈，使遍排序表码较烦小的桑元素讽逐渐耕从后睛部移并向前色部，捎就象胞水底兆下的诊气泡休一样未逐渐责向上吗冒。例如读，n=亭6，数剑组R的六哗个排仍序码掠分别缩慧为：17，3，25，14，20，9。下械面用揭图7-明3给出与冒泡纹排序丝式算法碑的执拳行过峡程。冒泡副排序匙的效泳率分奴析若待锅排序堂的元蜡素为虽正序句，则党只需牺进行宁一趟挣排序量，比睛较次档数为尘（n-未1）次哨，移讨动元践素次乞数为0；若待锈排序昂的元吓素为敏逆序大，则臭需进镰行n-乔1趟排朗序，肃比较秀次数丧为(n2-n丹)/梁2，移摇动次云数为3(动n2-n协)释/2，最坏话情况滨比较n(扣n-忘1)瞧/2因此姥冒泡恨排序狡算法慕的时不间复掀杂度梁为O（n2）。师由于例其中芬的元提素移雀动较焰多，党所以赖属于磁内排宗序中带速度挺较慢粘的一澡种。6.犯3.洋2快速帜排序基本勇思想票是：会取待斤排序娇序列贼中的愁某个再元素侦（一迫般第狸一个典元素园）作圈为基夏准，款通过独一趟逗排序妄，将荷待排食元素廊分为制左右各两个主子序文列，左子豪序列仍元素缴的排肢序码朋均小雀于或么等于材基准设元素废的排竖序码董，右子链序列裁的排时序码挨则大蜜于基奋准元胸素的鹿排序没码，然后毒分别悉对两埋个子芝序列无继续使进行快速排序耕，直凡至整喜个序释列有蜻序。元素新的比怪较和粒交换方是从好两端故向中水间进胶行的屡，排玩序码堪较大返的元由素一岂次就授能够仿交换骆到后昌面，如排序甚码较购小的针记录遗一次亚就能确够交止换到莲前面缩慧，记柔录每盆次移瞧动的铁距离朵较远耕，因葱而总杰的比循较和踩移动捎次数委较少舅。例如喇，给炎定排孩序码宵为：膊（46，55，13，42，94，05，17，70），挣具体围划分烤如图7-乒4所示超。3．快六速排花序的干效率鼻分析若快越速排拖序出扛现最缘瑞好的捕情形禁（左全、右洪子区贪间的帮长度文大致滩相等题），快速炎排序泡的最首好时效间复呀杂度冈应为O（nl您og2n）。已经坦证明错，快逝速排乱序的怪平均沉时间权复杂沈度也供为O（nl眼og2n）。若快桃速排鸦序出常现最援坏的榆情形采（每更次能爆划分漂成两规个子沿区间婆，但浸其中愤一个务是空签），蝇则这胡时得弟到的壳二叉份树是朗一棵挠单分举枝树遭，总世的比皮较次洪数为n(常n-证1)允/2。因净此，快速丹排序谁的最福坏时涨间复霞杂度方为O(亡n2)。快速租排序掏所占喝用的冰辅助扫空间论为栈茅的深捆度，碰故最惯好的叔空间饮复杂优度为O（lo