传智播客C和C与数据结构基础讲义

1、百度文库传智播客C和C+丐数据结构基础讲义传智扫地僧1、数据结构概念数据结构相关概念疑惑1、我学完了 C语言，可是现在感觉还是写不出代码。2、为什么会有各种各样的程序存在？3、程序的本质是什么？程序是为了具体问题而存在的程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏？数据结构起源 计算机从解决数值计算问题到解决生活中的问题'现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系 不是研究复杂的算法数据结构中的基本概念数据-程序的

2、操作对象，用于描述客观事物 (int a, int b,)/数据的特点：可以输入到计算机/可以被计算机程序处理数据是一个抽象的概念，将其进行分类后彳#到程序设计语言中的类型。如：int, float, char数据元素：组成数据的基本单位数据项：一个数据元素由若干数据项组成数据对象-性质相同的数据元素的集合(比如：数组，链表)68歉据敕据对象数据对象敷搪无费数据兀素敦据元素数据元数据41数据货2数据事1数据项2敦希项1数据项2 敷据事1数提项2答：物理结构亦称t是数据的迎再结构在计算机存储器内的表示（或映像）o它JwL jWL rv*-TJH J r I J"%口存储结构可分为4大类

3、：顺序.斐为 亲小散列最常用的存骨捕狗为： 顺序存的转树借助元素在存储卷 中的相 对位置末 袤示I数据元素间的逻辑关京铤式存储结构借助指示元素存储地址的指计襄示数据元素间的遑辑关系,数据的邃粗结构与存储结构密切相关算法设计K超辑结构笄法实现存储结构解什么是数据的运算操作或处理答：在数据的逗樽结构上定义的操作,。数据的存储结构上实现-I I I * BF,最常用的数据运算有S种：插入、删除、修女、查找、排序CM=VO /次at算法C ( 4H8 )法 5 nDUD (2*1)法D J n2 )n 112L- _.3I 21629 I4n 3203ig9n =1048102G1IftOn w 10

4、040810020 001IOOOO森 IQOO.4008LJ 0002 000 0011。画) <XK)次数M»G (in1)舞法H(3n+i 施 I ( 2r>z*3n+1 1246。 Z81715:n 5501666n« 1020031231n = 1002000030120 301n- LOOO2 000 0(103 0Ot2 003001n - IdOOO200 000000wool200 030 001n - 100t00020 000 000 000300 00120000 300 001n - 1.000,0002 000 000 000 000

5、3 OOOOOl200 000 1000 OOI执行次她离政I at非正式水*巴，0(1)2m+3L OCn)城业阶3nJ + 2n+l0(/)平方阶51ogjn+201OClop/j)H数降2n+ 5nio£n+ 19Ot/iloRrt)nlogu 阶6n*+2nJ+ln + 4。(“)二 .r 0(2")立方阶2Tt找4t阶0(1 )< 0(Jogn)< Oln) < O(dogn)< 0(/) < 0( )< 02"0")UJ. 工 J- 口 U 口 XJ.UJ._l数字n出现的次数放在新开辟的内存空间倒色n-1

6、的位置把每一个数字的中间结果给堞存下来一先来一个大家最感兴趣的.一年里的星座列表，是不是线性表呢？如图3-2-2所白 金 双 巨 狮 处 天 射 库 水 双羊牛,子蟹子女,稗手羯瓶鱼级中同学的友谊关系N:NB.公司中的上下级关系1:NC冬天图书馆排队占座关系D.花名册上名字之间的关系1:1线性表的操作创建线性表销毁线性表清空线性表将元素插入线性表将元素从线性表中删除获取线性表中某个位置的元素获取线性表的长度线性表在程序中表现为一种特殊的数据类型线性表的操作在程序中的表现为一组函数C语言描述=线性表的设计与实现ADT抽象层数据Z勾（C语言版）.严蔚敏_吴伟民.扫描版.pdfp44页人生财富库积累

7、#ifndef _WBM_LIST_H_#define _WBM_LIST_Htypedef void List;typedef void ListNode;341顺序存储定义说这么多的线性表，我们来看看线性表的两种物理结构的第一种一序存储结 构*性衰的总体存佛堵胸,指的是用一段地址连嫌的存簿元依次 存储畿性裳的鼓据元素r线性衣（皿 ,而）的喉序存储示意图如下：薪 a? Ab.i a $图"I*表以序寺施，健者沟曜口和也我的身临长F是网，'不同打假把t5 | 口 0 " 6 9 夕/I r方隹for（i=lenBthi； i2眠；1） Ifill. - uLl-1.

8、“-LEJ/ i - 3".卷五1奉- P“I 国 / & &） ?I巧 口0 k喇余空间n个结点（新的存储映像）蟒结成一个链表，即为线性裘（皿，I,，"）的情 式存储结构，因为此错表的每个结点中只包含一个指针域，所以叫做单链表.单榜表 正是通过每个给点的指针域将线惟表的数据元素技其逻辑次序链接在一起，如图324ixkfltypedef struct .tas.LinkListN?de LinkListtlode; struct _taf_LinkListNod&LinkLi£tNod&* rityt .：端点指针域正乂type d

9、ef struct _tag_LinkList -LirLkListWD(l& header： int length;TLinkList;一一定义st rict ValueLinkListNode header: int v： k数据元素定义示例插入元素操作* *9nade-Miext w current->next;node;curjreiileitrrftn tcurr«!n f - >neitJkcurrenc->nexc =it a de因去科"彳年产"一个匕皆保.行，一弓迪百current匚 CEGLt“01 rijde->

10、;£it = LArr&jfLl->nexl, 2 current>nei1 = nod?;:指针搭瞰就把谁的地幽喻指针?分清楚链表的操作逻辑和辅聃指曾变量之间的关卷GUETCDt/理存故地除的下点位置1 et= curricnt -z'neat;i指料拈iM蜘:把老的世址廊官推升£片常定范书的挨丰巴羯胡窜毛计克至之同的美第理耦cijrrent->ncxl = ret->nTzt共结点尾结点游标slider近六十年代出生的人，应该也就是我们父母那一薪，当年计划经济制度下，他们 的生活祓社会安排好了I先科员再科长、后处长再局长，混到哪算

11、哪；学徒.技工、 高级技工；教师、中皴我师、高fil教师，总之无论乘个行业都稔排辈.这钳的生活 如何让人奋发努力.所以经济发展缓慢,就豫苑们的线性表的顺序存储结构一样，位 置是推好的，一切都得慢慢来.可见.梦适环境是很卷培养出坚强品格，被安排好的人生，也很难做出伟大事 业#市场经济社会下，机会就大参了，你可以从社会的任何一个位置开始起步.只要 你真有决心，没有人可以拦着你.帘实也证期.无论出身是什么,之前是凄苦还是富 足，都有出人头地的一天。当然I这也就意味着，面临的竞争也是空前激烈的，一不 小心，你的位置就可能俄人插足，甚至你就得out出局这也多像我们线性表的链式 ， 存储结构,任何位置都可

12、以插入和删除*a 不怕苦，吃苦半辇子，怕吃苦.吃苦一草子*如果你觉得上学读书是受罪，假设 你可以活到B0岁.其实你最多也就吃了 20年苦,用人生四分之 的时间来换取瓮余 时阚的幸福生活，这点苦不你啥口再说了,跟背我学习，这也能算是吃苦？好了，今天课就到这，下i乱I普通插入元素（:和单链表是一样的）I3已经存在的和单窿表是一样的current/ ®nodeL / * i cu匚匚？nt->口匕xt = node;node'>nextnext->prenode'>prenext;node;current:，一A,fcurrentcurrent- &

13、#39;nextnext;next- precurrent;nullnentnesi=current-Jnent若植人第一个匕点，与耳判的打班樽傕否通冏人代和国足rmdje*>prg： - current ntJ?t->pre - 2fo .jiE-ie->njexC,一工上工 I w current->neit - 口口蛇: nr rentcurrent在尾部地 、元京变二.(1母阻甘Liitfit- pre = cumenlJieri巾体装出一W律后小蚪或emreht- »en rei-5hexT首先它是一个也就是说，栈元素具有线性关系I WJ前驱后继美系

14、.只不 过它是一种埼殊的线性表而已-定义中兑是在线性表的表足进行插入用删除操作，这 里表尾是指栈顶，而不是栈底.它的特殊之处就在于限制了这个毅性表的插入和蒯除位置，它始终只在栈顶进 行这也就使得：栈底是固定的，最先避栈的只能在栈底.栈的插入操作，叫作进栈，也称压钱.人栈。类似产弹人弹求,如图42*2所 示平极的蒯除操作，叫作出栈.也有的叫作弹栈 如同弹夹中的子弹出匕 w, A 2 3 所示.£飞在设一更部 L II!.乩/ 丁：丁更市、戕的错点群守inell尹,1_ 二 "口日二讲完了咳的顺序存储结构.我们现在来看，书的链式存储结构，简称为链栈.想想书,栈只是林劭来做插入和

15、坍除操作，栈顶放在拚去的头部还是尾部呢？由 于单盘表右头指针，血攫值指斜也是必须的.那十吗不让它喃合二为一呢，所跟比较 好的办法是把或顺放在单的表的从邮（如国46门所示葭 月外，都已芬布了愧顶在头 那广，甲链表中比较常用的头陆点也就失去了意义，通常对r链恍来说，是不需要头 结点电段底transformtexp)(创述桂5;"Mi i= )(it( expUJ 为妁字)<OutpuT(expli)； else if I expU)为衿号? (岫物explilCUUS <=性及符号伏光版) output (W5n<);poptsn )Pu4h5, expi)； else

16、 if(已卬门力左括号)( Push(5. expi); else if( expli)为右插号)( khilet K原存号不为芟括号)( outpu 口画&行号h Pop(S>从S甲弹出左括号一 else 报聃.停止鼻；while Si?e(S) > “砧(expj -=) ) 叫卬ut (理r®存号片 PoMS);J1computE忙卬) 翎建楼S;1=0；gillie( expi !空10 ) if( expfi为野字)(Push(S, expi)h else if( expi为符号)1从柱中弹出右捧作触；2.从栈中弹出左搔作软；3,概据符号进行运算；Pus

17、h (stack,结果);)else (报错停止鬲环;if( (Size(5) = L) <expi =) ) 煤作条线和客服系统中，都是应用r 神数据结构来实现刚才提到的先进先出的 排队功能，这就是队列.队列(queue I是艮北忤在一端进行插入操作.而在另一端进行除操作的线性衰口队列是一种先进先出(Fiet In Firat Out)的线性表，简称FIFO.允许插入的一 裁称为队尾，允许删除的一端称为队头,唱过队列是q=(ai, a九.aj.那么 位就是队头兀素，而小是队尾元素.这样我们就可以删除时，总是从at开始，而插 入时，列在后.这也比莪符合我们通常生活中的习惯，排在第一个的优

18、先出列，最 后来的当排在队缶最后，如图41tM所示.队列在程序设计中用得非常频繁前面我们已经举了两个例子，再比如用键盘进 行各种字句或数字的输入，到显示器上如记事本软件上的输曲.其实就是队列的典型鼠头闲致遍来模按队列. 从迎冕的国史入苴刊从数盥的。号位百出队列I- L 33456? 日I 目国对尾廖靓表来使纵队列，出鼠用肝尾部 AKX?J 从健老的Q号位置出队列需要于1,1列羊点=辘表给占=入链表率n对阿HPDCPDd.总1 j 己止所百箱点出队列，然后辉成籍点的内存 /蔚敏吴伟民.扫描版.pdf p124数据结构数据：数据Z构（C语言版）.严蔚敏吴伟民.扫描版.pdf p127QIDijTj

19、TX®®<s<a7Xrt 7<j)OOG)Q ©G ©f JkJif |1 JJ, =_x. .(ii) fi.o ( lj <0XaZW CDQ性质4:具有n个结点的完全二叉树的深度必为log2n + 1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i,其右孩子编号必为 2i + 1;其双亲的编号必为i/2 （i=1时为根，除外）二叉树的存储结构/一、顺序存储结构、/按二叉树的结点 自上而卜、从左至右”编号，用一组连续的存储单兀存储。答：一律转为完全二叉树！讨论：不是完全二叉树怎么办？方法很

20、简单，将各层空缺处统统补上虚结点”，其内容为空二、链式存储结构二叉树的表示二叉树表示法P127 页 /*typedef struct BiTNodeint data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;*/struct BiTNodeint data;struct BiTNode *lchild, *rchild;typedef struct BiTNode BiTNode;typedef struct BiTNode * BiTree;树的三叉链表表示先序遍历的结果是中序遍历的结果是DBEAC后序遍历的结果是DEBC ABCDEF

21、GII先序遍历 中序遍历 后序遍历BDCEAFHG DECBIIGFAULR先序遍历，即先根再左再右 LDR中序遍历，即先左再根再右 LRD后序遍历,即先左再右再根从前面的三科遍历算法可以令道：如果将printf语句抹去T 从递归的点度看，这三种算法是完全相同的，或者说这三种 遍历算法的访问路径是相同的乂是访问结点鞘时机不同.从虚线的出发点到终点的路径八上，每个结点经过3次.,第1次经过时访问二先存遍历B0第2次经过时访问=巾遍历；第3次经过时访河"后序追历干俊、/（£2.二叉树遇历的时间点率和空间效率时间放率：。（n） 每个结点 ;；访问一次F g J 1 -t：O（n&

22、gt; "栈占用的最大辅劫空间（精确值：树深为k的递归遍历需安+1 个辅助单元！）中序遍历算法的非递蚂描述BPEXckJc *lhibad xil(HiTree T. Suick *S)( if ! 1 > t'el u m 'ILL: while (T- (child )Prhih(S 母T - EchRU:1return： ),/± 2 g止冷及的斗:去 v*)id hardervoid i -clemType& e »> tHGSlack 展t GuL ad Jit I. S); 找到矗左下的好点wliiJril visi

23、ts- data ibif i|t- rchild ii = OuKwLeift&rchild. 5). dw ir I f Slue kJ imply IS )1 Sk厂、中亭岩巧三堂1明好?卜巴走吗T(d/时的形状轮唯一-.、, / *ft * / #并X彳飞 -.、 /前苫 /7Y十 /左种的雌有,4/右子树的根与,J/ /了搬屿时，抽右训"/整世满:的方不柑r岩更呵X播嘉平 和右子料边等分明(1)采用;叉链表空间效率这么低，能否利用这些空闲区存放 有用的信息？(2)二叉链表只能找到结点的左右孩子信息,而不能得到结 点在任一序列中的前驱和后继信息r这种信息只有在西历 过

24、程中才能得到，我们可否对二叉链去进行改造？f增加两个域：IXvd和bwd;两种解决方法I存放前里指不1 孱港爨指针利用空链域(n+1个空链域)我们可以用这IL1个空链域未存放当前站点的直接 前驱和后继等浅索，以加快查找速JL -A二叉线索树rchilcl悬空？力追免悬空1）若结点有左子树，则khUd指向其左孩子； 否则，khiWL指向其直接前驱；2）若结点有右子树.则rchild指向其右孩子； 否则，Eiild指向其直接后继（即线索3。了避免混淆.增加两个标志域.如下图所示曲山以下二叉树对应的残索二叉树该二叉树中序遍历结果为：ax L B, E,所以添加线索应当检如下路径进行：时,表示正常情况

25、; 时，表示线索情况.通过图6-10-4 （空心黄头实线为前驱，虚线黑箭头为后继），就更容易看出,其实 线索二义相，等于是把一模二叉树转变成了一个双向幡表，这样对我们的捕人删除结 点,查找某个结点都带来了方便，所以我们对二叉棚以某种次序遍历使其变为线索二 又树的过程称做是线索化图 6>ltM# .伸羽再忏变R 三智齿写手有常沮if Cprea>rehii E= WXL) E” 5 L rTfhiM - r 1有了线索二丈的后，我们对它进行遍街时发现，其实就等于是操作一个双向链表结构.void I rThr cadi ng (Bi 1 nrN n deJ(if)ifCprcddld

26、=即叮)/前朋校懿菽：:pie->KTai = L; pre->rchild = p; /)Pre = P；"爆拽卬善同g的3IThrcaiTi(p->rdnLd); /1ii®在既麒Ki3后/却骷岐b）/FInThrcadingchild)； /化if(p->lchild = WULL) / 凌魅P->LTm = 1； p->lchild = K"O线盍鬲近微推醐孤和双向链表结构一样，在二又树线索链表上添加一个头错点.如图6-1牛6所示， 并令其国匍域的指针指向二乂网的根结点（图中的）, K rchiU域的指针指向中序 遍行时

27、访问的最后一个结点（图中的）.反之1令二叉周的中序序列中的第一个结点 中，上hiH域指针和最后一个结点的rchild域指均指向头结点（图中的和I这 样定义的好处就是我们既可以从第一个结点起顺后傩进行遍历，也可以从最后一个结 点起搬前驱迸行遍历*我何能把这两耀4阔筒化成叶f给点带投的一叉羯，如图6-12-4所示.牝中A 妻示不及桃、B或示及格.C衷不中等.D襄示良好、E襄示优秀.每个叶干的分支 钱上的数字就是刚才我们提到的五缎分制的成绩所占比例般.用641薛夫堂大叔说，从树中一个结点到另一个结点之间的分支构成两个特点之间的躇 静，路役上的分支数自称懒路径长度，ffi 6-12-4的二式豺m中.根

28、结点到结点D的路及长度就为4,二义树b中根结点到站点D的路径长度为 入 梅的路径长度就是从 捌根到每一结点的路径长度之和已二又附a的树脐役长度就为 1+V2+2+3+3+4+4=20,二叉弱卜的锄路径长度就为 1*»3+3+2+1+2*2=1几如果考虑到带役的绪点.结点的带杈的踣径长度为从填结点到辅福之间的路段张 度与结点上权的秦极，幡的带权踣经长度为例中所者叶子结盒的带极痣径长度之和. 假慢仃仆个枇值wwu- Wn),构造一棵百口个叶子结点的二叉树，吊个明了结点嘴 权Wk.每个叶子的路径长度为1k,我解通轩汜作.则其中带权踣住长度 WL最小的 二叉称做麟关曼物也在不少好中他栋为最优

29、义榜，我个人党得为了纪念瓢出巨 大页*的科学家,既然用他仃的名字命名，就座簟9!坚持用他们的名字称呼,害怕 我优"史籍体现这操掷的品质也应垓只作为别名.ABCDEF01100110100111000BADCADFEED I ;1001010010101001000111100定n个数值 v1, v2,，vn2 .根据这n个数值构造二叉树集合 FF = T1, T2,TnTi的数据域为vi,左右子树为空3 .在F中选取两棵根结点的值最小的树作为左右子树构造一棵新的二叉树，这棵二叉树的根结点中的值为左右子树根结点中的值之和4 .在F中删除这两棵子树，并将构造的新二叉树加入F中5 .重复3

30、和4,直到F中只剩下一个树为止。这棵树即霍夫曼树假设经过统计ABCDEF&需要传输的报文中出现的概率如下ABCDEF27%8%15%15%30%5%霍夫曼树是一种特殊的二叉树霍夫曼树应用于信息编码和数据压缩领域 霍夫曼树是现代压缩算法的基础5、排序排序基本概念现实生活中排序很重要算法已写好代码复用&和我们需要学习前辈们的经验不矛盾，也不代表我们不需要不学习。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。排序数学定义：假设含 n个数据元素的序列为 R1, R2,，Rn其相应的关键字序列为 K1, K2,，Kn这些关键字相互之间可以进行

31、比较，即在它们之间存在着这样一个关系：Kp1< Kp2< < Kpn按此固有关系将上式记录序列重新排列为 Rp1, Rp2,，Rpn的操作称作排序排序的稳定性如果在序列中有两个数据元素ri和rj,它们的关键字ki = k j,且在排序之前，对象明排在 前面。如果在排序之后，对象 明仍在rj前面，则称这个排序方法是稳定的； 否则称这个排序方法是不稳定的。多关键字排序排序时需要比较的关键字多余一个排序结果首先按关键字1进行排序当关键字1相同时按关键字2进行排序/当关键字n-1相同时按关键字n进行排序/对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可！排序中的关键操作比较

32、任意两个数据元素通过比较操作确定先后次序交换数据元素之间需要交换才能得到预期结果内排序和外排序内排序整个排序过程不需要访问外存便能完成外排序待排序的数据元素数量很大，整个序列的排序过程不可能在内存中完成排序的审判/时间性能关键性能差异体现在比较和交换的数量辅助存储空间为完成排序操作需要的额外的存储空间必要时可以“空间换时间”算法的实现复杂性过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能 总结排序是数据元素从无序到有序的过程排序具有稳定性，是选择排序算法的因素之一比较和交换是排序的基本操作多关键字排序与单关键字排序无本质区别排序的时间性能是区分排序算法好坏的主要因素选择法基本

33、思想每一趟（例如第i趟，i = 0,1,n-2）在后面n-i个待排的数据元素中选出关键字 最小的元素，作为有序元素序列的第i个元素。排序过程'首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交 换重复上述操作，共进行 n-1趟排序后，排序结束i-2 一趟二二趟;三趟二四趟二五趟:六趟: 排序结束;例i=l初始:耳7 76 49 65 13273813273813273813273813273849494976659797 76 6576 97 49 65 7697假设排序过

34、程中，待排数据元素序列的状态为:有序序列R0- i-l无序序列Ri+*n第i瓶简单选择排序从中选出 关键字最小的元素有序序列HO.i无序序列Ri+l.n插入排序基本思想：元素i个元素，排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列, 然后从第2个记录开始，逐个进行插入，直至整个序列有序实质：对线性表执行 n-1次插入操作，只是先要找到插入位置V0, V1,，Vi-1已经排好序。这时已经排好序。这时 ，用Vi的关键字与 Vi-1, Vi-2, 的关键字进行比较，找到插入位置即将 Vi插入，原来位置上的对象向后顺移。插入排序关键点：1、拿出一个元素，留出位置、 2

35、符合条件的元素后移例 i=l (49 38 65 97 76 13 27 I户2 38 (38 49) 65 97 76 13 27尸365(384965)977613271-497(38496597)761327j=576(3849657697)1327i=613(133849657697)彳703 >«»»«JJJJJJ排序结果：(13 27 38 49 65 76 97)冒泡排序排序过程将第一个记录的关键字与第二个记录的关饯字进行 比较，著为逆序r1.key>r2.key,则交换：然后比 较第二个记录与第三个记录；依次类推1r宜至第n-

36、1 个记录和第0个记录比较为止弟一越冒泡排序.结果关键字般大的记录被安置在Jft后一个记录上对前n，1个记录进行第二趟官泡排序，结果使关键字 次大的记录被安置在第n-1个记录位置重复上述过程，宜到“在一趟排序过程中没有迸行 过交换记声的蜂作好为止Tnstm E )int aQl 1 J 5，int i.；t;prinvf Cinpul 1。numbers =nw) ; for (i= 1 iVl 1 ;" +)scan£C”%d.&a：i)孑printf < n” > ?for <j= 1 ；j<l= 9 ; j Hfor (i = 1 ?

37、i= j o j *i-1-十)if £«iQAai + J 二)t = aCil(aLi21 = aIi-l- 1 J printf<the sorted numbers 士 for G = 1 T VI：i十 +)printf (%d。白口).算法冉改进1 2 3 6 5 4上述冒泡排序还可做如下改进：即记住最 后一次交换发生位置lastExchangc泡排序.在“自下向上”冒泡车布趟扫描中，记 住最后一次交换发生的位一置：lastExchange, 位置之前的相邻记录均已有序).下一趟排序开 始时，R| L.lastExchange-11 是有序区， Rlast

38、Exchangcj是无序区.这样一趟排序可 能使当前有序区扩充多个记录，从而减少排序 的趟数，有奖征集该程序Q希尔排序排序过程：先取一个正整数 d1<n,把所有相隔di的记录放一组，组内进行直接插入排序; 然后取d2<d1,重复上述分组和排序操作；直至 di=1,即所有记录放进一个组中排序为止OQ(nlogn)希尔排序是不稳定的。例初始t 49 38 65 97 76 13 27 48 55 4取dl=5一趟分组：49 38 65 9 76 13 27 4S 55 4一趟排序：1327 48 55 449 386、9776取 d2=3二趟分组：1327 48 55 449 3865

39、9776二趟排序：13 44838274955659776取 d3=l二趟分组：13 448382749556597761三趟排序：4 132738484955657697快速排序思想：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，基准数据排在这两个子序列的中间；然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。：对rst中记录进行一趟快速排序,附设两个指针i和j,设x-rp.key而始辞令仁s产t首先从j所指位置向前才 的记录，并和rp交换:记录 rp=rs.第一个关键字 从后向刖再犍字位置起向后搜索，找到第一个关 记录，和甲交换；从前向后 可步，直至i=j为止A再分别对两个