§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].key<=R[].key R[i++]:R[j++]; for(i=nl2;i>0;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 22 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( i<=m && j<=high ) //2子表非空时，取其头上较小者输出到R1[p]上 R1[p++]=( R[i].key<=R[j].key ) ? R[ i++]: R[ j++] ; while ( i<=m ) //第1子表非空，将剩余记录copy到R1中 R1[p++]=R[ i++ ]; while ( j<=high ) //第2子表非空，将剩余记录copy到R1中 R1[p++]=R[ j++ ]; R=R1; //将R1copy回R，R[low..high] R1[0..high-low] } 9 § 10.5 归并排序 „ 排序算法 ™ 自底向上：见Fig10.13 ™ 自上而下：分治法设计 (1)分解：将当前区间一分为二，分裂点mid＝ (2)求解：递归地对2个子表R[low..mid]和R[mid+1..high]进行归并排 序，出口是当前区间长度为1。 (3)组合：将上述两有序的子表归并成1个有序表R[low..high] void MergeSort( SeqList R, int low, int high ) { int mid; if ( low<high ){ //区间长度>1 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个箱子