基数排序的时间是Onlgn课件.ppt

1、1 10.4.2 堆排序（堆排序（Floyd&Williams）直接选择的比较次数多是因为后一趟未利用前一趟的直接选择的比较次数多是因为后一趟未利用前一趟的比较结构，树形选择可克服此缺点，但它耗费的空间大，比较结构，树形选择可克服此缺点，但它耗费的空间大，故实用的树形选择是堆排序。故实用的树形选择是堆排序。n 思想思想 将将R1.n看作是看作是1棵完全二叉树的顺序存储结构，利用棵完全二叉树的顺序存储结构，利用完全二叉树的双亲和孩子之关系，在当前无序区里选择最完全二叉树的双亲和孩子之关系，在当前无序区里选择最小（大）元扩充至有序区。小（大）元扩充至有序区。n 二叉堆（快速选择最大二叉堆（快速选择

2、最大/小元）小元）n个个keys序列序列K1,K2,，Kn称为堆，当且仅当满足如称为堆，当且仅当满足如下性质（下性质（堆性质堆性质，堆序堆序）：）：（1）或或 （2）这里，这里，。即。即i结点不是叶子结点不是叶子iiiikkkk212iiiikkkk2122/1ni2 10.4.2 堆排序堆排序n 堆性质堆性质 将将R1.n看作是完全二叉树的顺序存储结构时，堆性质看作是完全二叉树的顺序存储结构时，堆性质实质上是满足如下性质的完全二叉树：实质上是满足如下性质的完全二叉树：树中任一非叶结点的树中任一非叶结点的key均不大均不大/小于其左右孩子（若存小于其左右孩子（若存在）结点的在）结点的key。即

3、：。即：从根到任一叶子的路径上的结点序列是从根到任一叶子的路径上的结点序列是一个有序序列，堆中任一子树仍是堆。一个有序序列，堆中任一子树仍是堆。它适合查找吗？它适合查找吗？101525305670701056253015堆顶堆顶703025561510107015255630堆顶堆顶小根堆小根堆大根堆大根堆3 10.4.2 堆排序堆排序n 算法思想算法思想 1、初始化、初始化 将将R1.n建成建成大根堆大根堆，即初始无序区。，即初始无序区。2、排序、排序v交换：交换：设当前无序区是大根堆设当前无序区是大根堆R1.i，交换其中的首尾记录，交换其中的首尾记录，即最大元即最大元R1（堆顶）交换到无序

4、区尾部（有序区头部），（堆顶）交换到无序区尾部（有序区头部），使有序区在使有序区在R的尾部逐渐扩大：的尾部逐渐扩大：R1.i-1.keysRi.n.keys/前者为无序区，后者为有序区前者为无序区，后者为有序区 显然，显然，in,n-1,2，即，即n1趟排序即可完成。趟排序即可完成。v调整：调整：将新无序区将新无序区R1.i-1调整为堆。注意：只有调整为堆。注意：只有R1可能违可能违反堆性质。反堆性质。4 10.4.2 堆排序堆排序n 算法实现算法实现void HeapSort(SeqList R)int i;BuildHeap(R);/将将R1.n建成初始堆建成初始堆 for(i=n;i1;

5、i-)/进行进行n-1趟堆排序，当前无序区为趟堆排序，当前无序区为R1.i R1 Ri;/无序区首尾记录交换，无序区首尾记录交换，R0做暂存单元做暂存单元 Heapify(R,1,i-1);/将将R1.i-1重新调整为堆重新调整为堆 n 如何调整堆和构造初始堆？如何调整堆和构造初始堆？5 10.4.2 堆排序堆排序n 调整（重建）堆调整（重建）堆 设调整区间为设调整区间为Rlow.high，因为只有根，因为只有根Rlow违反堆序，它的两子树违反堆序，它的两子树（若存在，则根为（若存在，则根为R2low，R2low+1）均是堆。）均是堆。v 无须调整无须调整 若若Rlow.key不小于两孩子的不

6、小于两孩子的Keys，则，则Rlow不违反堆序不违反堆序v 必须调整必须调整 将将Rlow和它的两孩子中较大者交换：和它的两孩子中较大者交换：设设Rlarge.key=max R2low.key,R2low+1.key 令令Rlow Rlarge 交换后交换后Rlarge可能违反堆序，重复上述过程，直至被调整的结点已满足可能违反堆序，重复上述过程，直至被调整的结点已满足堆序，或该结点已是叶子。堆序，或该结点已是叶子。2010562530155610252030155610202530156 10.4.2 堆排序堆排序n 调整堆算法调整堆算法void Heapify(SeqList R,int

7、low,int high)int large;/只有只有Rlow可能违反堆序可能违反堆序 RecType temp=Rlow;for(large=2*low;largehigh，则，则Rlow是叶子，结束；是叶子，结束；/否则，先令否则，先令large指向指向Rlow的左孩子的左孩子 if(largehigh&Rlarge.key=Rlarge.key)break;/满足堆序满足堆序 Rlow=Rlarge;/交换，小的筛下交换，小的筛下 low=large;/令令low指向新的调整结点指向新的调整结点 Rlow=temp;/将被调整结点放到最终的位置将被调整结点放到最终的位置7 10.4.2

8、 堆排序堆排序n 构造初始堆算法构造初始堆算法 将将R1.n建成堆，须将其每个结点为根的子树均调整为堆。建成堆，须将其每个结点为根的子树均调整为堆。对 叶 子（对 叶 子（i ）无 须 调 整，只 要 依 次 将 以 序 号）无 须 调 整，只 要 依 次 将 以 序 号为为 ,2,1的结点为根的子树均调整为堆即可。的结点为根的子树均调整为堆即可。按此次序调整每个结点时，其左右子树均已是堆按此次序调整每个结点时，其左右子树均已是堆 void BuildHeap(SeqList R)int i;for(i=n/2;i0;i-)Heapify(R,i,n);/将将Ri.n 调整为堆调整为堆 n 时

9、间：时间：最坏及平均皆为最坏及平均皆为O(nlgn)(2nlgn+O(n)n 特点：特点：就地，不稳定就地，不稳定2/n12/n2/n8 10.5 归并排序归并排序n 归并的基本思想：归并的基本思想：将将K（K2）个有序表合并成一个新的有序表。）个有序表合并成一个新的有序表。n 二路归并：二路归并：K2，类似于理牌，类似于理牌void Merge(SeqList R,int low,int m,int high)/将将2个有序表个有序表Rlow.m和和Rm+1.high归并为归并为1个有序表个有序表Rlow.high int i=low,j=m+1,p=0;/i,j指向输入子表头，指向输入子表

10、头，p指向输出子表指向输出子表 RecType*R1=(RecType*)malloc(high-low+1)*sizeof(RecType);/输出输出 if（!R1）Error(“存储分配失败存储分配失败”)while(i=m&j=high)/2子表非空时，取其头上较小者输出到子表非空时，取其头上较小者输出到R1p上上 R1p+=(Ri.key=Rj.key)?R i+:R j+;while(i=m)/第第1子表非空，将剩余记录子表非空，将剩余记录copy到到R1中中 R1p+=R i+;while(j=high)/第第2子表非空，将剩余记录子表非空，将剩余记录copy到到R1中中 R1p

11、+=R j+;R=R1;/将将R1copy回回R，Rlow.high R10.high-low9 10.5 归并排序归并排序n 排序算法排序算法v 自底向上自底向上：见：见Fig10.13v 自上而下自上而下：分治法设计：分治法设计 (1)分解分解：将当前区间一分为二，分裂点：将当前区间一分为二，分裂点mid (2)求解求解：递归地对：递归地对2个子表个子表Rlow.mid和和Rmid+1.high进行归并排序，进行归并排序，出口是当前区间长度为出口是当前区间长度为1。(3)组合组合：将上述两有序的子表归并成：将上述两有序的子表归并成1个有序表个有序表Rlow.highvoid MergeSo

12、rt(SeqList R,int low,int high)int mid;if(low1 mid=(low+high)/2;/分解分解 MergeSort(R,low,mid);/解子问题解子问题1，结束时，结束时Rlow.mid有序有序 MergeSort(R,mid+1,high);/解子问题解子问题2，结束时，结束时Rmid+1.high有序有序 Merge(R,low,mid,high);/组合组合 /endif2/)(highlow10 10.5 归并排序归并排序n 性能分析性能分析v时间时间：最好最坏均是：最好最坏均是O(nlgn)v空间空间：辅助：辅助O(n)，非就地排序，非就

13、地排序n 特点特点v稳定稳定v易于在链表上实现易于在链表上实现v与快排相比与快排相比：分解易、组合难：分解易、组合难11 10.6 分配排序分配排序n 基于比较的排序时间下界基于比较的排序时间下界:由由Stirling公式知：公式知：lgn!nlgn-1.44n+O(lgn)要突破此界，就不能通过要突破此界，就不能通过keys的比较。的比较。n 分配排序正是如此，它通过分配排序正是如此，它通过“分配分配”和和“收集收集”过程实现排序，过程实现排序，时间为时间为O(n)。10.6.1 箱排序箱排序n 基本思想基本思想v分配分配：扫描：扫描R0.n-1,将将key等于等于k的记录全装入的记录全装入

14、kth箱子里箱子里v收集收集：按序号将各非空箱子首尾连接起来：按序号将各非空箱子首尾连接起来v多趟多趟：每个关键字：每个关键字1趟，例如趟，例如:扑克牌扑克牌n 时间时间：v分配分配：O(n)；v收集收集：设箱子数为：设箱子数为m(与与key相关相关)，时间为，时间为O(m)或或O(m+n)v总计总计：O(m+n)=O(n)if m=O(n)!lg n1210.6.2 基数排序基数排序n 基本思想基本思想箱排序只适用于箱排序只适用于keys取值范围小的情况，否则浪费时间和空间。取值范围小的情况，否则浪费时间和空间。例如，若例如，若mO(n2),则时间和空间均为则时间和空间均为O(n2)。基数排

15、序是通过分析基数排序是通过分析key的构成，用多趟箱排序实现的。的构成，用多趟箱排序实现的。n 例子例子设设n10，ki0.99,1i 10输入输入:（36,5,10,16,98,95,47,32,36,48）将将2位整数看作位整数看作2个个keys，先对个位，后对十位做箱排序。因此，先对个位，后对十位做箱排序。因此，无须无须100个箱子，只要个箱子，只要10个箱子。个箱子。1310.6.2 基数排序基数排序第第1趟箱排序趟箱排序分配：分配：0 101 2 32345 5,956 36,16,367 478 98,489收集：收集：10,32,5,95,36,16,36,47,98,48（36

16、,5,10,16,98,95,47,32,36,48）第第2趟箱排序趟箱排序分配：分配：0 051 10,162 3 32,36,364 47,485 6 7 8 9 95,98收集：收集：05,10,16,32,36,36,47,48,95,98n 各趟排序前要求清空箱子，分配和收集须按各趟排序前要求清空箱子，分配和收集须按FIFO进行，箱子用链队列表示。进行，箱子用链队列表示。n 除第除第1趟外，趟外，其余各趟一定要是稳定的排序其余各趟一定要是稳定的排序，否则结果可能有错。，否则结果可能有错。n m不再在数量级上大于不再在数量级上大于O(n)，故上述排序时间是，故上述排序时间是O(n)14

17、10.6.2 基数排序基数排序n 一般情况一般情况设任一记录设任一记录Ri的的key均由均由d个个分量分量 构成构成v多关键字文件：多关键字文件：d个分量皆为独立的个分量皆为独立的keyv单关键字文件：每个分量是单关键字文件：每个分量是key中的中的1位，只讨论这种情况。位，只讨论这种情况。设每位取值范围相同：设每位取值范围相同：C0KjCrd-1(0jd)这里，这里，rd称为基数，称为基数，d为为key的位数。的位数。若若key为十进制整数，按位分解后为十进制整数，按位分解后rd10，C00，C99n 排序算法排序算法 从低位到高位依次对从低位到高位依次对Kj（jd-1,d-2,0）进行）进

18、行d趟箱排序，所需的箱趟箱排序，所需的箱子数为基子数为基rd。#defin KeySize 4/设设d4#define Radix 10/基基rd为为10 typedef RecType DataType;/各箱子用链队列表示，其中的结点数各箱子用链队列表示，其中的结点数据类型改为与本章的记录类型一致据类型改为与本章的记录类型一致1di1i0i.KKK1510.6.2 基数排序基数排序void RadixSort(SeqList R)/对对R0.n-1做基数排序，设做基数排序，设keys为非负整数，为非负整数，/且位数不超过且位数不超过KeySize LinkQueue BRadix;/10个

19、箱子个箱子 int i；for(i=0;i=0;i-)/对位对位i箱排序，从低位到高位进行箱排序，从低位到高位进行d趟箱排序趟箱排序 Distribute(R,B,i);/分配分配 Collect(R,B);/收集收集 1610.6.2 基数排序基数排序void Distribute(SeqList R,LinkQueue B,int j)int i，k，t；/按关键字按关键字jth分量分配，进入此过程时各箱子为空分量分配，进入此过程时各箱子为空 j=KeySize-j;/将将 j 换算为从个位起算，个位是第换算为从个位起算，个位是第1位位 for(i=0;in;i+)/扫描扫描R，装箱，装箱

20、 k=Ri.key;for(t=1;tj;t-)k=k/10;/去掉去掉key的后的后j-1位位 k=k%10;/取取key的第的第j位数字位数字k EnQueue(&Bk,Ri);/将将Ri装入箱子装入箱子Bk void Collect(SeqList R,LinkQueue B )int i=0,j;/依次连接各非空箱子，完成后使各箱子变空依次连接各非空箱子，完成后使各箱子变空 for(j=0;j1)，则，则key的位数是：的位数是：dlog10nkklog10nO(klgn)因此，基数排序的时间是因此，基数排序的时间是O(nlgn)。但是可将其改为。但是可将其改为n进制表示：进制表示：r

21、dn，dlognnkk，T(n)O(k(n+n)=O(n)n 辅助空间：辅助空间：O(n+rd)n 对对key的要求：的要求：n 稳定排序：要求第稳定排序：要求第1趟稳定，其余各趟必须稳定。趟稳定，其余各趟必须稳定。1810.7 各种排序方法的比较和选择各种排序方法的比较和选择n 选择因素：选择因素：实例规模，记录大小，实例规模，记录大小，key的结构及初始状态，对稳定性的的结构及初始状态，对稳定性的要求，存储结构，时间和辅助空间的要求，语言工具（指针）。要求，存储结构，时间和辅助空间的要求，语言工具（指针）。n 比较比较n直接插入直接插入直接选择直接选择冒泡排序冒泡排序堆排序堆排序快速排序快

22、速排序随随 4000 8000 10000 15000机机 20000增增 20000减减 200005.6723.1535.4380.23143.670.05286.9217.3029.4346.02103.00185.05185.78199.0015.7864.0399.10223.28399.470.03584.670.130.280.350.580.770.750.800.070.170.220.330.470.230.28n 说明说明 直接选择无论直接选择无论k和和i是否相等，均交换；快排用中间元做划分元。是否相等，均交换；快排用中间元做划分元。1910.7 各种排序方法的比较和选择

23、各种排序方法的比较和选择排序方法排序方法最好时间最好时间平均时间平均时间最坏时间最坏时间辅助空间辅助空间稳定性稳定性直接插入直接插入直接选择直接选择 冒泡冒泡 希尔希尔快速快速堆堆归并归并基数基数O(n)O(n2)O(n)O(nlgn)O(nlgn)O(nlgn)O(d*n+d*rd)O(n2)O(n2)O(n2)O(n1.25)O(nlgn)O(nlgn)O(nlgn)O(d*n+d*rd)O(n2)O(n2)O(n2)O(n2)O(nlgn)O(nlgn)O(d*n+d*rd)O(1)O(1)O(1)O(1)O(lgn)O(1)O(n)O(n+rd)稳定稳定不稳定不稳定稳定稳定不稳定不稳定不稳定不稳定不稳定不稳定稳定稳定稳定稳定