秋季刘鹏远助教韩越卢梦依课件.ppt

1、2017秋季 刘鹏远助教：韩越/卢梦依数据结构ch.7概述插入排序、希尔排序交换排序、冒泡、快速排序选择排序、堆排序归并排序基数排序、计数排序、桶排序排序方法的分析与比较选择排序n简单选择排序n堆排序简单选择排序n 简单选择排序的基本步骤是：在一组记录 ViVn 中选择具有最小关键字值的记录（索引）；若它不是这组记录中的第一个记录,则将它与这组记录中的第一个记录对调;在剩下的记录 Vi+1Vn 中重复执行第、步,直到剩余记录只有一个为止。简单选择排序void selectSort(DataList*L)/伪码伪码 int i,j,min;/min存放最小值位置存放最小值位置 for(i=1;i

2、 L.n;i+)min=i;/选择具有最小关键字值的记录 for(j=i+1;j=L.n;j+)if(L.Vj.key L.Vi.key)min=j;/每次记录每次记录当前具最小关键字值的记录 if(min!=i)/对换到第 i 个位置 swap(L.Vi,L.Vmin);/数据仍然是从数据仍然是从1开始的，从开始的，从0开始则稍有不同开始则稍有不同简单选择排序在第i趟简单选择排序中，关键字值间比较n-i次；元素的移动，最少0次，最多3次。RCN(最好最坏):1+2+.n-1=n(n-1)/2RMN：最好0次（有序），最坏3(n-1)次（待排序记录初始状态是按第一条记录最大，之后的记录从小到大

3、顺序排列）。存储空间额外用1个。简单选择排序是不稳定的（因为相隔一段距离交换数据，实例？）选择排序之锦标赛排序（树形选择排序）改进，如何进行比较，选择一个最值类似现实中分区进行比赛来选冠军的过程（不需要循环赛）P278继续改进-堆排序n设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 0 开始连续编号。若满足 Ki K2i+1&Ki K2i+2 或 Ki K2i+1&Ki K2i+2,则称该关键字集合构成一个堆。n前者称为最小堆（小根堆），后者称为最大堆（大根堆）。堆排序 完全二叉树顺序表示堆 Ki K2i+1&Ki K2i+1&K

4、i K2i+2 Ki K2i+2090987877878454565653131532323531717n利用堆及其运算,可以很容易地实现选择排序的思路。n堆排序分为两个步骤1）根据初始输入数据，利用堆的筛选算法 SiftDown()形成初始堆;2）通过一系列的记录交换和重新调整堆进行排序。n堆排序比较适合在数据动态变化中进行排序的情形n除了优先队列，还常用堆在n个元素中挑选(第)k个最值，ksize-2)/2;/从最后分支结点（子树根）开始最后分支结点（子树根）开始 while(start=0)/从后向前逐步调整堆直从后向前逐步调整堆直到最大堆的根到最大堆的根 SiftDown(H,star

5、t,H-size-1);/index为节点数-1 start-;最大堆的向下筛选算法void SiftDown(MaxHeap*H,int start,int EndOfHeap)int i=start,j=2*i+1;/j 是是 i 的左子女的左子女 HeapElem temp=H-datai;/保存待调整元素保存待调整元素 while(j=EndOfHeap)/EndOfHeap为最后一个节点的index if(j dataj.key dataj+1.key)j+;/两子女中选大者两子女中选大者(j为左孩，分支节点必有右孩，为左孩，分支节点必有右孩，倒数第二个叶倒数第二个叶)if(temp

6、.key=H-dataj.key)break;/比最大的大，不用调 else H-datai=H-dataj;i=j;j=2*j+1;/比两子女大者小，则与大子女交换向下滑动比两子女大者小，则与大子女交换向下滑动 H-datai=temp;/待调整元素就位待调整元素就位 堆排序n堆顶元素最大，删除之后，堆顶元素又是其余的最大.n最大堆堆顶H.data0 保存具有最大关键字值的记录，将H.data0 与H.datan-1对调,把具有最大关键字值的记录交换到最后,再对前面的n-1个记录,使用堆的向下筛选算法SiftDown(H,0,n-2),重新建立最大堆,具有次大关键字的记录又上浮到H.data

7、0位置。（这也是为什么需要第三个参数的原因）堆排序n再对调H0和Hn-2,调用sift_down(H,0,n-3),对前n-2个记录重新筛选调整.n如此反复执行，最后得到全部排序好的记录序列。这个算法即堆排序算法。n注意无需从后开始SiftDown，直接从0开始。492525*211608012345082525*16214902543149 25 21 25*16 0808 25 21 25*16 49交换交换 0 号与号与 5 号记录号记录,5 号记录就位号记录就位初始最大堆初始最大堆2525*082116490123451625*0825214902543125 25*21 08 16

8、4916 25*21 08 25 49交换交换 0 号与号与 4 号记录号记录,4 号记录就位号记录就位从从 0 号到号到 4 号号 重新重新调整为调整为最大最大堆堆25*1608212549012345081625*25214902543125*16 21 08 25 4908 16 21 25*25 49交换交换 0 号与号与 3 号记录号记录,3 号记录就位号记录就位从从 0 号到号到 3 号号 重新重新调整为最大堆调整为最大堆211625*082549012345081625*25214902543121 16 08 25*25 4908 16 21 25*25 49交换交换 0 号与

9、号与 2 号记录号记录,2 号记录就位号记录就位从从 0 号到号到 2 号号 重新重新调整为最大堆调整为最大堆160825*212549012345081625*25214902543116 08 21 25*25 4908 16 21 25*25 49交换交换 0 号与号与 1 号记录号记录,1 号记录就位号记录就位从从 0 号到号到 1 号号 重新重新调整为最大堆调整为最大堆堆排序void HeapSort(DataList*H)/伪码 for(i=(H.n-2)/2;i=0;i-)SiftDown(H,i,H.n-1);/建立初始堆 for(i=H.n-1;i=1;i-)swap(H.d

10、ata0,H.datai);/交换 SiftDown(H,0,i-1);/重建最大堆 算法分析n详见教材P282-283。n建堆时，每层进行调整的节点数为2i-1，最多需要调整(该层节点的深度-1)次，每次最多比较2次。总比较次数小于4n。n排序删除调整时，siftdown是O(log2n)的算法，因此可推算大O约为：2(logn-1+.log4+log3+log2)，结果为O(nlogn)n 需要一个交换元素用的存储空间O(1)n 堆排序是一个不稳定的排序方法n2路归并排序n多路归并排序n递归/非递归归并排序基本思想：对任意两个有序线性表，第二章中，对其归并的时间复杂度为：O（a+b），也是

11、线性的。对任意一个长度为n的序列，可视为一系列两个长度为1的线性序列（或额外一个长度为1的线性序列），逐层进行归并（长度为1的自然有序）归并排序两路归并(2-way merging)n归并Merge，是将两个或两个以上的有序表合并成一个新的有序表。n例如，原始序列L 中有两个有序表 Ll Lm和Lm+1 Lh。把它们归并成一个有序表，存于另一序列L1的L1l L1h 中。这种归并方法称为两路归并(2-way merging)。n为了实现两路归并，需要设置 3 个指针：变量 i 和 j 是表Ll Lm和Lm+1 Lh的当前检测指针。k 是表 L1 的存放指针。两路归并算法n当 i 和 j 都在两

12、个表的表长内变化时，根据对应项的关键字的大小，依次把关键字小的记录排放到新表 k 所指位置中；n当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。08 21 25 25*49 62 72 93 16 37 54 left mid mid+1 rightL08 16 21 25 25*37 49 54 62 72 93 left rightkL1两路归并算法void merge(dataList*L,dataList*L1,int left,int mid,int right)int i=left,j=mid+1,k=left;while(i=mid&j=right)/

13、两两比较 if(L.Vi.key=L.Vj.key)L1.Vk=L.Vi;i+;k+;else L1.Vk=L.Vj;j+;k+;while(i=mid)L1.Vk=L.Vi;i+;k+;while(j n=L-n;for(s=left;s=mid;s+)/正向复制 L1.Vs=L.Vs;for(s=mid+1;s=right;s+)/反向复制 L1.Vright+mid+1-s=L.Vs;while(k=right)/归并过程 if(L1.Vi.key=L1.Vj.key)L.Vk+=L1.Vi+;else L.Vk+=L1.Vj-;归并排序(Merge Sort)归并排序也是典型的分治策略

14、，其递归算法思想可描述如下:MergeSort(List)if(还能够划分)将序列List划分为等长的两个子序列 LeftList和Right List;MergeSort(LeftList);/对子序列递归排序 MergeSort(RightList);/对子序列递归排序 将两个子序列 LeftList和RightList归并为一个 序列List;/自顶向下分解，然后再自底向上合并递归的归并排序算法void doSort(dataList*L,int left,int right)if(left n-1);/对序列归并排序;非递归归并排序212525*936272083716544921 2

15、554len=1len=2len=4len=8len=1625*4962 9308 7216 3721 25 25*4908 62 72 9316 37 5408 21 25 25*49 62 72 9316 37 5408 16 21 25 25*37 49 54 62 72 93归并排序归并排序时间复杂度：O(nlogn)需要n大小的辅助空间，空间复杂度：O(n)递归稳定性：稳定2路归并排序在内排序中较少应用多(k)路归并（排序）-多用于外排序非比较排序（分配排序）n通过转换为树结构，或者通过多次划分（本质上也是形成树结构），排序已经得到了O（nlogn）级别的算法，大大优于简单排序的n2

16、，直觉上，O（nlogn）级的方法已经是最优。非比较排序（分配排序）n要讲下一种排序，是直觉又一次naive了？nNO，直觉没有问题，看教材P291-292页n你应该会想起哈希/散列n不利用关键字间直接比较来排序呢？计数排序与桶排序n考虑个简单情况，一个序列中有n个数字，假设取值范围在1-k间，现对其进行排序。计数排序：建数组下标为1-k之间，元素初始值均为0。遍历一遍序列，遇到与下标相同的数字就将该下标内元素+1。最后利用数组遍历，将数字排序输出。时间复杂度：O（n+k）。需要额外k个空间。适合排序整数，整数范围差不太大的情况(max-min)。计数排序与桶排序n假设取值范围跨度K=MAX-

17、MIN比较大，现对其进行排序。则会浪费太多辅助存储空间。桶排序：将整个跨度K分为M个桶。则可遍历一遍待排序序列中的元素，将元素扔在M个桶中。然后在每个桶中进行快速排序。每个桶依次输出。时间复杂度：O(N+C)，其中C=N*(logN-logM)，最好时M=N，则类似计数排序。空间复杂度：O(M+N)（一般用链表做桶）要求取值范围较均匀，否则会集中到一个桶中，退化为NLOGN基数排序n对多关键字排序问题进行排序n教材P284 请看动画nMSD最低位优先与LSD最高位优先nO（d(n+rd)），存储：O（rd）r为基数取值，d为关键字个数每一队列设置两 个队列指针：int front r指示队头

18、int rear r 指向队尾r即基数radix教材以静态链表作为它们的存储结构。基数排序的“分配”与“收集”过程 第一趟614921485637738101215530790306第一趟分配（按最低位 i=3）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第一趟收集530790921101614485215306637738基数排序的“分配”与“收集”过程 第二趟614921485637738101215530790306第

19、二趟分配（按次低位 i=2）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第二趟收集530790921101614485215306637738基数排序的“分配”与“收集”过程 第三趟614921485637738101215530790306第三趟分配（按最高位 i=1）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 f

20、r2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第三趟收集530790921101614485215306637738表排序与地址排序n排序直接采用顺序表，对于数据记录很大时，导致元素频繁移动耗时，因此可以：n1、（表排序）利用(静态)链表存储而进行的排序n2、（地址排序）另开辟一个位置记录数组，存放数据记录的位置，仅对位置记录数组进行调整。还可以变相实现快速排序与堆排序。P289排序总结（教材P288）期末考试例题选择题：下列程序段的时间复杂度为（）。i=0，s=0；while(sn)s=s+i；i+；A.O(n1/2)B.O(n1/3)C.O(n)D.O(n2)期末考试例题判断

21、题：调用一次深度优先遍历可以访问到图中的所有顶点。期末考试例题画图题：给定“AABBBBCCCDDEAAAAFFBBCCC”，对其进行huffman编码。画出对应的huffman树，给出各个字符的编码。编码时huffman树节点的左分支赋0，右分支赋1。期末考试例题n填空题：以下是堆排序算法（目标非递增有序）/堆调整算法：将i为根的子树调整为堆（i的所有子树都已经满足堆性质）/*参数：a-待排序数组首地址，n-总元素个数，i-当前子树根下标 */void Adjust(int*a,int i,int n).(1).(2).(3)./*初始化堆算法，将a初始化为最小堆*/*参数：a-待排序数组首

22、地址，n-总元素个数 */void InitHeap(int*a,int n).(4).(5).期末考试例题填空题：/*堆排序算法，将数组a（长度为n）非递增排序 */*参数：a-待排序数组首地址，n-总元素个数 */void HeapSort(int*a,int n)InitHeap(a,n);for(int i=0;i n-1;+i)/将堆顶和最后一个元素交换，再调整堆int t=a0;a0=an-i-1;an-i-1=t;_ (6)_ ;期末考试例题填空题：下面是快速排序的递归算法，其中有一些语句缺失，请根据算法的功能补充之。/Partition为划分函数，区间为start,end)，返

23、回值为中间点元素位置。int Partition(int*a,int start,int end)/1.选取序列的“中点”为支点int i,j,pivot;pivot=a(end+start)/2;a(end+start)/2=astart;/2.以pivot为支点，将原序列分为2个子序列i=start,j=end-1;while(i j).几个空.期末考试例题编程题：1.设有一组初始记录关键字序列（K1，K2，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2.判断一棵树是否为二叉排序树。ThANKS！I LOVE U ALL