数据结构分解PPT学习教案

1、会计学1数据结构分解数据结构分解2插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3）2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希尔排序希尔排序小改进小改进大改进大改进第1页/共50页3 以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的）为例，分别写出执行以下算法的各趟各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？排序结束时，关键字序列的状态，并说明这些排序

2、方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？ 直接插入排序直接插入排序 希尔排序（取希尔排序（取dk=5,3,1）答：答：显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后：第2页/共50页4 256256，301301 ，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301，7517

3、51 ，129129，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751 ，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，937937 ，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937 ，742742，694694，076076，438438 129129，256256，301301，742742，751751

4、，863863，937937 ，694694，076076，438438 129129，256256，301301，694694，742742，751751，863863，937937 ，076076，438438 076076，129129，256256，301301，694694，742742，751751，863863，937937 ，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863，937937 第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟第3页/共5

5、0页5256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，

6、076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076

7、，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，43

8、8438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第4页/共50页6void ShellSort(SqList &L，int dlta ，int t) /按增量序列按增量序列dlta0t-1对顺序表对顺序表L作作Shell排序排序 for(k=0；kt；+k) ShellSort(L，dltak)； / ShellSort空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元( (与算法有关）与算法有关）算法的

9、稳定性：算法的稳定性：因为因为4949* *排序后却到了排序后却到了4949的前面的前面参见教材参见教材P272P272由经验公式得到由经验公式得到dkdk值依次装在值依次装在dltadltat t 中中/增量为增量为dltak的一趟插入排序的一趟插入排序第5页/共50页7理解难点：理解难点：整理动作是二合一的，整理动作是二合一的， r0 仍是每个仍是每个dk子集的哨兵，用于子集的彻子集的哨兵，用于子集的彻底排序！底排序！ for(i=dk+1；i=L.length； + i) if(ri.key 0&(r0.key0&(r0.keyrj.key); j-=dk) rj+dk=

10、rj；rj+dk=r0； 5 7 45 7 4 i=1 i+dk=6 i+2dk=11 i=1 i+dk=6 i+2dk=11 如果不用如果不用forfor循环，比较的结果是循环，比较的结果是 5 5，4 4，7 7 只有执行只有执行forfor循环后，比较结果才会是循环后，比较结果才会是 4 4，5 5，7 7for(i=dk+1；i=L.length； + i) if(ri.key ri-dk.key) r0=ri；大者后移大者后移空间效率与算法设计有关空间效率与算法设计有关第7页/共50页9交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序第8页

11、/共50页10基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素同时部分理顺其他元素；一旦下趟没有交换发生，还可以；一旦下趟没有交换发生，还可以提前结束排序提前结束排序。前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。），请写出冒泡排序的具体实现过程。21，25，49， 2

12、5*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初态初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第9页/共50页11最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n- -1 次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n-

13、i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。此时的比较总次数次对象交换。此时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(第10页/共50页12第11页/共50页13第12页/共50页14( )，设以首元素为枢轴中心设以首元素为枢轴中心21， 25， 49， 25*，16， 08初态：初态：第第1趟趟：第第2趟趟：第第3趟趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)第13页/共50页15pivotkey

14、=21pivotkey=21( 08 ，16 ） 21 （ 25* ， 49， 25 ）ri0123456初态初态21254925*1608第第1趟趟highhighlowlow2125*32108251649设计技巧：设计技巧：交替交替/振荡式逼近振荡式逼近第14页/共50页16原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076

15、076，438438，129129，937937，863863，742742，694694，301301，438438意即模拟算法实现步骤意即模拟算法实现步骤076076301301129129751751，129129，438438，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，( (存每层存每层lowlow，highhigh和和pivot)pivot)第15页/共50页17讨论讨论1 1：如何编程实现？：如何编程实

16、现？分析：分析：每一趟子表的形成是采用从两头向中间交替式逼近法；每一趟子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，主程序可采用递归算法。由于每趟中对各子表的操作都相似，主程序可采用递归算法。见教材见教材P275int int (SqList &L,int(SqList &L,int low low,int,int high high) ) /一趟快排一趟快排/交换子表交换子表 rlowrlowhighhigh的记录，使支点（枢轴）记录到位，并的记录，使支点（枢轴）记录到位，并返回其位置返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均

17、不小于它。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。 r0=r0=rlowrlow; ; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作）第16页/共50页18pivotkey=pivotkey=rlow.keyrlow.key; ; /取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high) /从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(whil

18、e(lowhighlow=pivotkeyrhigh.key=pivotkey ) ) rlow=rhigh; rlow=rhigh; /比支点小的记录交换到低端；比支点小的记录交换到低端；while(while(lowhighlowhigh & & rlow.key=pivotkeyrlow.key=pivotkey) ) rhigh=rlow; rhigh=rlow; /比支点大的记录交换到高端；比支点大的记录交换到高端；rlow=r0; rlow=r0; /支点记录到位；支点记录到位；return return lowlow; ; /返回支点记录所在位置。返回支点记录所在

19、位置。 /第17页/共50页19从高端从高端扫描扫描寻找小于寻找小于pivot的元的元素素从低端从低端扫描扫描寻找大于寻找大于pivot的元的元素素r0=rlow; pivot=rlow.key;low highlow =pivot- high;rlow = rhigh;low high &rlow.key=pivot- low;rhigh = rlow;rlow = r0;return low;第18页/共50页20if ( low 1/对顺序表对顺序表L中的子序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进行递归快排

20、，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1是局部变量是局部变量 1, L.length 第19页/共50页21设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位置；第第4 4趟比较（趟比较（8 8个子表）

21、，可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置； 只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。教材教材P276P276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为O(nlogO(nlog2 2n)n)；但最坏情况下但最坏情况下( (例如天然有序例如天然有序) )仍为仍为O(nO(n2 2),),改进措施见改

22、进措施见P277P277。第20页/共50页22选择排序有多种具体实现算法：选择排序有多种具体实现算法： 1) 简单选择排序简单选择排序 2) 锦标赛排序锦标赛排序 3) 堆排序堆排序第21页/共50页23第22页/共50页24原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49时间效率：时间效率： 虽移动次数较少，但比较次数仍多。虽移动次数较少，但比较

23、次数仍多。 空间效率：空间效率：没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)算法的稳定性：算法的稳定性：因为排序时，因为排序时，2525* *到了到了2525的前面。的前面。最小值最小值 0808 与与r1r1交换位置交换位置第23页/共50页25Void SelectSort(SqList &L ) for (i=1; i0; - - i ) HeapAdjust(r, i, length ); HeapSortHeapAdjust是针对结点是针对结点 i 的堆调整函数，的堆调整函数，其含义是：其含义是：从结点从结点i i开始到开始到堆尾堆尾为止，自上向下比

24、较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。参见教材参见教材P281-282第37页/共50页39while(child=m) /检查是否到达当前堆尾，未到尾则整理检查是否到达当前堆尾，未到尾则整理 if ( childm & rchild.key=rchild.key ) breack; /根大则不必调整，函数结束根大则不必调整，函数结束 else rcurrent=rchild; /否则子女中的大者上移否则子女中的大者上移 current= child; child=2* c

25、hild; /将根下降到子女位置将根下降到子女位置 / while rcurrent=temp; /直到自下而上都满足堆定义，再安置直到自下而上都满足堆定义，再安置入口入口结点结点 / HeapAdjustHeapAdjust(r, i, m )current=i; temp=ri; child=2*i; /temp暂存暂存ri值，值，child是其左孩子是其左孩子 从结点从结点i i开始到开始到当前堆尾当前堆尾m m为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。第38页/

26、共50页40H.rim中除中除ri外，其他都具有堆特征。外，其他都具有堆特征。现调整现调整ri的值的值 ，使，使H.rim为堆。为堆。第39页/共50页41第40页/共50页42123456136542第41页/共50页43123456136542第42页/共50页44123456136542第43页/共50页45123456136542第44页/共50页46123456136542第45页/共50页47void HeapSort (HeapType &H ) /对顺序表对顺序表H进行堆排序进行堆排序 for ( i = H.length / 2; i 0; - - i ) HeapAdjust(H,i, H.length ); /for,建立初始建立初始堆堆 for ( i = H.length; i 1; - -i) H.r1 H.ri