中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）Ch10 排序（2/2）

§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是否相等，均交换；快排用中间元做划分元