§ 堆排序（Floyd &Williams）

Presentation on theme: "§ 堆排序（Floyd &Williams）"— Presentation transcript:

1 § 10.4.2 堆排序（Floyd &Williams）
直接选择的比较次数多是因为后一趟未利用前一趟的比较结构，树形选择可克服此缺点，但它耗费的空间大，故实用的树形选择是堆排序。 思想 将R[1..n]看作是1棵完全二叉树的顺序存储结构，利用完全二叉树的双亲和孩子之关系，在当前无序区里选择最小（大）元扩充至有序区。 二叉堆（快速选择最大/小元） n个keys序列K1, K2, …，Kn称为堆，当且仅当满足如下性质（堆性质，堆序）： （1） 或 （2） 这里， 。即i结点不是叶子

2 § 10.4.2 堆排序 堆性质 将R[1..n]看作是完全二叉树的顺序存储结构时，堆性质实质上是满足如下性质的完全二叉树：
树中任一非叶结点的key均不大/小于其左右孩子（若存在）结点的key。即：从根到任一叶子的路径上的结点序列是一个有序序列，堆中任一子树仍是堆。它适合查找吗？ 70 30 25 56 15 10 堆顶 10 15 25 30 56 70 堆顶 小根堆 大根堆

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 § 堆排序 调整（重建）堆 设调整区间为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 20 25 30 15 56 10 25 20 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; large<=high; large*=2 ) { //R[low]是当前调整结点，若large>high，则R[low]是叶子，结束； //否则，先令large指向R[low]的左孩子 if (large<high && R[large].key<R[large+1].key ) large++; //若R[large]有右兄弟，且右兄弟大，则令large指向右兄弟 if ( temp.key>=R[large].key ) break; //满足堆序 R[low]=R[large]; //交换，小的筛下 low=large; //令low指向新的调整结点 } R[low]=temp; //将被调整结点放到最终的位置

7 § 堆排序 构造初始堆算法 将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)) 特点：就地，不稳定

8 § 10.5 归并排序 归并的基本思想：将K（K≥2）个有序表合并成一个新的有序表。 二路归并：K＝2，类似于理牌
§ 归并排序 归并的基本思想：将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＝
§ 归并排序 排序算法 自底向上：见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 }

10 § 10.5 归并排序 特点 性能分析 时间：最好最坏均是O(nlgn) 空间：辅助O(n)，非就地排序 稳定 易于在链表上实现
§ 归并排序 性能分析 时间：最好最坏均是O(nlgn) 空间：辅助O(n)，非就地排序 特点 稳定 易于在链表上实现 与快排相比：分解易、组合难

11 § 10.6 分配排序 基于比较的排序时间下界: 分配排序正是如此，它通过“分配”和“收集”过程实现排序，时间为O(n)。
§ 分配排序 基于比较的排序时间下界: 由Stirling公式知：lgn!＝nlgn-1.44n+O(lgn) 要突破此界，就不能通过keys的比较。 分配排序正是如此，它通过“分配”和“收集”过程实现排序，时间为O(n)。 § 箱排序 基本思想 分配：扫描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)

12 §10.6.2 基数排序 基本思想 例子 将2位整数看作2个keys，先对个位，后对十位做箱排序。因此，无须100个箱子，只要10个箱子。
例如，若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个箱子。

13 §10.6.2 基数排序 （36,5,10,16,98,95,47,32,36,48） 第1趟箱排序 第2趟箱排序 分配： 0 10
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
设每位取值范围相同： 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; //各箱子用链队列表示，其中的结点数据类型改为与本章的记录类型一致

15 §10.6.2 基数排序 void RadixSort( SeqList R ){
//对R[0..n-1]做基数排序，设keys为非负整数， //且位数不超过KeySize LinkQueue B[Radix]; //10个箱子 int i； for ( i=0; i<Radix; i++ ) //初始化 InitQueue(&B[i]); //清空箱子 for( i=KeySize-1; 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； //按关键字jth分量分配，进入此过程时各箱子为空 j=KeySize - j; //将 j 换算为从个位起算，个位是第1位 for ( i=0; i<n; i++ ) { //扫描R，装箱 k=R[i].key; for( t=1; t<j; t-- ) k=k/10; //去掉key的后j-1位 k=k%10; //取key的第j位数字k EnQueue( &B[k],R[i] ); //将R[i]装入箱子B[k] } void Collect( SeqList R, LinkQueue B[ ] ){ int i=0, j; //依次连接各非空箱子，完成后使各箱子变空 for ( j=0; j<Radix; j++ ) //将jth箱子的内容依FIFO序收集到R中 while ( !QueueEmpty (&B[ j ]) ) //若是链队列，只需首尾链接 R[i++]=DeQueue( &B[ j ]);

17 §10.6.2 基数排序 链式基数排序：文件R不是以向量形式，而是以单链表形式给出。 时间：线性阶 箱子初始化：O(rd)
分配时间：O(n)，不计求第j位数字的时间 收集收集：O(n+rd)，链式为O(rd) d趟总时间：O( d(2n+rd) )，链式为O( d(n+rd) ) T(n)=O(n) if d=O(1) and rd=O(1) ～ O(n) 设key是十进制整数，d是常数吗？ 若n个keys的取值范围是0 ～nk，(常数k>1)，则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的结构及初始状态，对稳定性的要求，存储结构，时间和辅助空间的要求，语言工具（指针）。 比较 n 直接插入 直接选择 冒泡排序 堆排序 快速排序 随 4000 8000 10000 15000 机 20000 增 20000 减 20000 5.67 23.15 35.43 80.23 143.67 0.05 286.92 17.30 29.43 46.02 103.00 185.05 185.78 199.00 15.78 64.03 99.10 223.28 399.47 0.03 584.67 0.13 0.28 0.35 0.58 0.77 0.75 0.80 0.07 0.17 0.22 0.33 0.47 0.23 说明 直接选择无论k和i是否相等，均交换；快排用中间元做划分元。

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