§10.4.2堆排序(Floyd&Williams) S10.4.2堆排序 直接选绎的比较次数多是因为后一越未利用前一蜡的 童堆性质 比较结构，制形选择可克服此缺点，但它耗费的空间大， 将R[1.]看作是完全二叉树的顺序存储结构时，堆性质 故实用的树形选择是堆排序， 实质上是满足如下性质的完全二叉树： 一思想 树中任一非叶结点的ky均不大I小于其左右孩子（若存 将[1.看作是1裸完全二叉树的顺序存储结构，利用 在)结点的ky。即：从振到任一叶子的路径上的结点序列是 完全二叉树的双亲和孩子之关暴，在当前无序区里选择量 二个有序序列，维中任字树仍是堆。它适合童战具】 小（大）元扩充至有序区。 ■二叉堆（快速选择量大小元） 101556253070 705630251510 n个keys序列K1,K,K称为堆，当且仅当满足如 10 堆项 70 堆顶 下性质（维性质，堆序）： w(好 skizkzi 或 (2)1k,≥k2+1 3070 25 15 10 这里，1i≤l2.即结点不是叶子 小操维 大根 510.4.2堆排序 S10.4.2堆排序 ■算法思想 ■算法实现 1初始化将R1n建成大根堆，即初始无序区。 void HeapSort(SeqList R){ 2,韩序 inti; ◆交换：设当前无序区是大根堆R[1】,交换其中的首尾记录， BuildHeap(R方将RI.n毫成初始维 即量大元R)(堆项)交换到无序区儿部（有序区头都），使 有序区在R的具都逐新扩大： for(n;>1:i-)(进行-4随堆排序当前无序区为R1.司 R1.i-1】.keys≤R0.n可.key5前衡为无序区，后南为有序区 R[1们兰R叮：凭序区首尾记录交换，R0做言存单元 显然，i=n,n-1,2,即n一1热排序即可完成。 Heapify(R,1,i-1)方1将R1.-们置新调蓝为绳 ◆澜整：将新无序区R1-1]调整为堆，注意：只有R1)可能违 反堆性质。 ◆ 如何调整堆和构造初始堆？ 510.4.2堆排序 S10.4.2堆排序 调遵（量建）堆 ·调盖维算法 c骨程黑内8到注反维床它幽两子内 void Heapify(SeqList R,int low,int high ) int large;只有Rlow个可能连反堆序 ◆无须调量若RfIowJ.key不小于两孩子的Key5,测Row]不速反堆序 RecType temp=R[low]; ◆必演调睡将R[Ow和它的两球子中较大青交换： for large=2"low;largehigh,则Ro是时子，射来 ◆Rflow]→R[arge 香测，先冷arge指向Row的左孩于 交换后Rrge可能速反堆序，量复上述过程，直至被调整的纳点已满足 if (large=R[larg.key)break:满层撞序 Rlow=R[large]:度换，小的薄下 Iow=arge;喻low指向断的调整结点 Row小=temp;将被调睡结点放到曼簧的位重 10 1510 1510 1
1 1 § 10.4.2 堆排序（Floyd &Williams） 直接选择的比较次数多是因为后一趟未利用前一趟的 比较结构，树形选择可克服此缺点，但它耗费的空间大， 故实用的树形选择是堆排序。 思想 将R[1..n]看作是1棵完全二叉树的顺序存储结构，利用 完全二叉树的双亲和孩子之关系，在当前无序区里选择最 小（大）元扩充至有序区。 二叉堆（快速选择最大/小元） n个keys序列K1, K2, …，Kn称为堆，当且仅当满足如 下性质（堆性质，堆序）： （1） 或（2） 这里， 。即i结点不是叶子 i i i i k k k k 2 2 1 { ≥ ≥ + i i i i k k k k 2 2 1 { ≤ ≤ + 1≤i≤⎣ ⎦ n/2 2 § 10.4.2 堆排序 堆性质 将R[1..n]看作是完全二叉树的顺序存储结构时，堆性质 实质上是满足如下性质的完全二叉树： 树中任一非叶结点的key均不大/小于其左右孩子（若存 在）结点的key。即：从根到任一叶子的路径上的结点序列是 一个有序序列，堆中任一子树仍是堆。它适合查找吗？ 70 56 30 25 15 10 70 10 56 25 30 15 堆顶 10 15 56 25 30 70 10 70 15 25 56 30 堆顶 小根堆 大根堆 3 § 10.4.2 堆排序 算法思想 1、初始化 将R[1..n]建成大根堆，即初始无序区。 2、排序 交换：设当前无序区是大根堆R[1..i]，交换其中的首尾记录， 即最大元R[1]（堆顶）交换到无序区尾部（有序区头部），使 有序区在R的尾部逐渐扩大： R[1..i-1].keys≤R[i..n].keys //前者为无序区，后者为有序区 显然，i＝n,n-1,…,2，即n－1趟排序即可完成。 调整：将新无序区R[1..i-1]调整为堆。注意：只有R[1]可能违 反堆性质。 4 § 10.4.2 堆排序 算法实现 void HeapSort( SeqList R ) { int i; BuildHeap( R ); //将R[1..n]建成初始堆 for ( i=n; i>1; i-- ) { //进行n-1趟堆排序，当前无序区为R[1..i] R[1] R[i]; //无序区首尾记录交换，R[0]做暂存单元 Heapify( R,1,i-1 ); //将R[1..i-1]重新调整为堆 } } 如何调整堆和构造初始堆？ 5 § 10.4.2 堆排序 调整（重建）堆 设调整区间为R[low..high]，因为只有根R[low]违反堆序，它的两子树 （若存在，则根为R[2low]，R[2low+1]）均是堆。 无须调整 若R[low].key不小于两孩子的Keys，则R[low]不违反堆序 必须调整 将R[low]和它的两孩子中较大者交换： 设R[large].key=max{ R[2low].key, R[2low+1].key } 令R[low] R[large] 交换后R[large]可能违反堆序，重复上述过程，直至被调整的结点已满足 堆序，或该结点已是叶子。 20 10 56 25 30 15 56 10 25 20 30 15 56 10 20 25 30 15 6 § 10.4.2 堆排序 调整堆算法 void Heapify( SeqList R, int low, int high ) { int large; //只有R[low]可能违反堆序 RecType temp=R[low]; for ( large=2*low; largehigh，则R[low]是叶子，结束； //否则，先令large指向R[low]的左孩子 if (large=R[large].key ) break; //满足堆序 R[low]=R[large]; //交换，小的筛下 low=large; //令low指向新的调整结点 } R[low]=temp; //将被调整结点放到最终的位置 }
§10.4.2堆排序 §10.5归并排序 ■构造初始堆算法 。归并的落本思想：将K(K≥2)个有序表合并成一个新的有序表。 将R[1.可建成堆，须将其每个结点为根的子树均调整为 。二路归井：K=2,类似于理牌 堆。对叶子(>2)无须调整，只要依次将以序号 void Merge(SeqList R,int low,int m,int high ) 为2121的结点为的子树均为堆即可。 将2个有序麦Rowm和Rm+料high归珠为1个有序凄Row.hig时 此次序调鼓每个结点时，其左右子树均已是堆 it=ow,j户m+1,p=0:机指向输入子表头，p指向抛出子囊 RecType*R1=(RecType')malloc(high-low+1)'sizeof(RecType));/ void BuildHeap(SeqList R){ 计（R1)Eror“存轴分配失敷”) whie(K=m&jK=high)2子套非空时取英头上较小蜜输出到Rpj正 inti; R1[p++]=(R[i].key0;i-） while(ik=m)第1子表非空，将测余记录copy到R1中 Heapify(R,i,nl;将Rn调整为绳 R1[p++]=R[i++]; while(jK=high)第2子乘非空，将测余记最copy到R1中 R1[p++]=R[j++]; ■时间：量坏及平均皆为0(nlgn)(2nlgn+O(n) R=R1;R1copy回R,R即ow.high一Ro.high4ow ■符点：就地，不稳定 §10.5归并排序 S10.5归并排序 童排序算法 ■性能分析 ◆自底向上：见Fig10.13 ◆自上而下：分治法设计 ◆时间：景好最坏均是o(nlgn】 (1)分海：将当前区间一分为二，分录点mid=1o+h加g)/2] ◆空间：辅助O(),非就地排序 保品得发欲Rowm问和md1-nNg时进行归并排 ■特点 (3)赠音：将上述两有序的子衰归并成1个有序表R[low..high时 void MergeSort(SeqList R,int low,int high ) ◆雅定 int mid; ◆易于在链表上实现 i计(low<high X{区间长度1 ◆与快排相比：分解易、组合难 mid=(low+high)V2;分锡 MergeSort代R,low,mid方解子问属1，轴束时Row.mi离序 MergeSort(R,mid+1,high方解于向厘2，结束时Rmid+1.high时有房 Merge(R,low,mid,high方a合 lendif §10.6分配排序 §10.6.2基数排序 ■基于比较的排序时间下界：「gn门 ■基本思想 由Stirling公式知：lgnl=nlgn-1.44n+olgn) 箱排序只适用于k©ys取值范国小的情况，香则浪费时间和空间， 要突破此界，就不能通过k©ys的比较。 例如，若m=0(n),则时间和空均为0()： ◆ 分配排序正是如此，它通过“分配和“收集过程实现排序，时 盖数排序是通过分析k©y的构成，用多楚箱排序实现的。 间为0n)。 ·例子 510.6.1箱排序 设n=10,k∈0.99,1≤i≤10 ■基本思想 输入：(36,5,10,16,98,95,47,32,3648) ◆分配：扫描R0.n-1],将k©y等于k的记录全装入kh精子里 将2位整数看作2个k©y5,先对个位，后对十位做箱排序，因 令收集：披按序号将各非空箱子首尾连接起来 此，无须100个箱子，只要10个箱子， ◆多越：每个关铺字1慧，例脚：扑克牌 ■时间： ◆分配：O(n: ◆数集：设箱子数为m(与key相关)，时间为0(m)或0(m+n ◆总计：O(m+n卢0(n)ifm=O(n 2
2 7 § 10.4.2 堆排序 构造初始堆算法 将R[1..n]建成堆，须将其每个结点为根的子树均调整为 堆。对叶子（ i> ）无须调整，只要依次将以序号 为 , , … ,2,1的结点为根的子树均调整为堆即可。按 此次序调整每个结点时，其左右子树均已是堆 void BuildHeap( SeqList R ) { int i; for ( i=n/2; i>0; i-- ) Heapify( R, i, n); //将R[i..n] 调整为堆 } 时间：最坏及平均皆为O(nlgn) (2nlgn+O(n)) 特点：就地，不稳定 ⎣ ⎦ n / 2 ⎣ ⎦ n / 2 －1 ⎣ ⎦ n/ 2 8 § 10.5 归并排序 归并的基本思想：将K（K≥2）个有序表合并成一个新的有序表。 二路归并：K＝2，类似于理牌 void Merge( SeqList R, int low, int m, int high ) { //将2个有序表R[low..m]和R[m+1..high]归并为1个有序表R[low..high] int i=low, j=m+1, p=0; //i,j指向输入子表头，p指向输出子表 RecType *R1=(RecType *)malloc(high-low+1)*sizeof(RecType));//输出 if （ !R1 ）Error( “存储分配失败” ) while( i1 mid=( low+high )/2; //分解 MergeSort( R, low, mid ); //解子问题1，结束时R[low..mid]有序 MergeSort( R, mid+1, high ); //解子问题2，结束时R[mid+1..high]有序 Merge( R, low, mid, high ); //组合 }//endif } ⎣ ⎦ (low+ high)/ 2 10 § 10.5 归并排序 性能分析 时间：最好最坏均是O(nlgn) 空间：辅助O(n)，非就地排序 特点 稳定 易于在链表上实现 与快排相比：分解易、组合难 11 § 10.6 分配排序 基于比较的排序时间下界: 由Stirling公式知：lgn!＝nlgn-1.44n+O(lgn) 要突破此界，就不能通过keys的比较。 分配排序正是如此，它通过“分配”和“收集”过程实现排序，时 间为O(n)。 §10.6.1 箱排序 基本思想 分配：扫描R[0..n-1],将key等于k的记录全装入kth箱子里 收集：按序号将各非空箱子首尾连接起来 多趟：每个关键字1趟，例如:扑克牌 时间： 分配：O(n)； 收集：设箱子数为m(与key相关)，时间为O(m)或O(m+n) 总计：O(m+n)=O(n) if m=O(n) ⎡ ⎤ lg n! 12 §10.6.2 基数排序 基本思想 箱排序只适用于keys取值范围小的情况，否则浪费时间和空间。 例如，若m＝O(n2), 则时间和空间均为O(n2)。 基数排序是通过分析key的构成，用多趟箱排序实现的。 例子 设n＝10，ki ∈[0..99], 1≤i ≤10 输入:（36,5,10,16,98,95,47,32,36,48） 将2位整数看作2个keys，先对个位，后对十位做箱排序。因 此，无须100个箱子，只要10个箱子
§10.6.2基数排序 §10.6.2基数排序 (36,5.10,16,98.95,47,32,3648) 一般情况 第1鹅箱排序 2箱排序 设年记要R即的k@y均由阶分是KKK-构成 分 多关字文件：d个分量为立的k时 0110 0105 单关键字文件：每个分量是k©y中的1位，只讨论这种情况。 1 10,16 设每位取值范相同： 232 32,36,36 Co≤K≤Cd1(0≤=0;i-){ 对位箱排序，从低位到高位进行d髓箱排序 void Collect(SeqList R,LinkQueue B[]){ Distribute(R,B,i方分 it=0,上体次连接各非空箱子，完成后使各箱子变空 Collect(R,B方收第 for(=O:j1),则key的位数是： 15000 80.23 103.00 223.28 0.58 0.33 d=logon=klog on=(klgn) 机20000 143.67 185.05 399.47 0.77 0.47 因此，基数排序的时间是Olgn)。但是可将其改为n进制表示： 抛20000 0.05 8578 0.03 0.75 623 rd=n,d=lognk=k,T(n)=O(k(n+n))=O(n) 轴助空间：O(n+rd 减20000286.92 199.00 584.67 0.80 0.2 对key的要求： 说明 穗定排序：要求第1整跑定，其余各施必须穗定。 直接选择无论k和是香相等，均交换：快排用中间元触划分元。 3
3 13 §10.6.2 基数排序 第1趟箱排序 分配： 0 10 1 2 32 3 4 5 5,95 6 36,16,36 7 47 8 98,48 9 收集： 10,32,5,95,36,16,36,47,98,48 （36,5,10,16,98,95,47,32,36,48） 第2趟箱排序 分配： 0 05 1 10,16 2 3 32,36,36 4 47,48 5 6 7 8 9 95,98 收集： 05,10,16,32,36,36,47,48,95,98 各趟排序前要求清空箱子，分配和收集须按FIFO进行，箱子用链队列表示。 除第1趟外，其余各趟一定要是稳定的排序，否则结果可能有错。 m不再在数量级上大于O(n)，故上述排序时间是O(n) 14 §10.6.2 基数排序 一般情况 设任一记录R[i]的key均由d个分量 构成 多关键字文件：d个分量皆为独立的key 单关键字文件：每个分量是key中的1位，只讨论这种情况。 设每位取值范围相同： C0≤Kj ≤Crd-1 (0≤j﹤d) 这里，rd称为基数，d为key的位数。 若key为十进制整数，按位分解后rd＝10，C0＝0，C9＝9 排序算法 从低位到高位依次对Kj （j＝d-1,d-2,…,0）进行d趟箱排序，所需的箱 子数为基rd。 #defin KeySize 4 //设d＝4 #define Radix 10 //基rd为10 typedef RecType DataType; //各箱子用链队列表示，其中的结点数 据类型改为与本章的记录类型一致 d 1 i 1 i 0 i K K ...K − 15 §10.6.2 基数排序 void RadixSort( SeqList R ){ //对R[0..n-1]做基数排序，设keys为非负整数， //且位数不超过KeySize LinkQueue B[Radix]; //10个箱子 int i； for ( i=0; i=0; i-- ) { //对位i箱排序，从低位到高位进行d趟箱排序 Distribute( R,B,i ); //分配 Collect( R,B ); //收集 } } 16 §10.6.2 基数排序 void Distribute( SeqList R, LinkQueue B[ ], int j ){ int i，k，t； //按关键字j th分量分配，进入此过程时各箱子为空 j=KeySize - j; //将 j 换算为从个位起算，个位是第1位 for ( i=0; i1)，则key的位数是： d＝log10nk＝klog10n＝O(klgn) 因此，基数排序的时间是O(nlgn)。但是可将其改为n进制表示： rd＝n， d＝lognnk＝k，T(n)＝O( k(n+n) )=O(n) 辅助空间：O(n+rd) 对key的要求： 稳定排序：要求第1趟稳定，其余各趟必须稳定。 18 §10.7 各种排序方法的比较和选择 选择因素：实例规模，记录大小，key的结构及初始状态，对稳定性的 要求，存储结构，时间和辅助空间的要求，语言工具（指针）。 比较 0.07 0.17 0.22 0.33 0.47 0.23 0.28 0.13 0.28 0.35 0.58 0.77 0.75 0.80 15.78 64.03 99.10 223.28 399.47 0.03 584.67 17.30 29.43 46.02 103.00 185.05 185.78 199.00 5.67 23.15 35.43 80.23 143.67 0.05 286.92 随 4000 8000 10000 15000 机 20000 增 20000 减 20000 n 直接插入 直接选择 冒泡排序 堆排序 快速排序 说明 直接选择无论k和i是否相等，均交换；快排用中间元做划分元