存放结果的表 template <elass Type> void datalist<Type>: count sort()4 ∥ netList是待排序表, resultlist是结果表 intc= new datalist <Type>; ∥c是存放计数排序结果的临时表 for(i=0;i< Currentsize;i计+) ector. count=0;∥初始化,计数值都为0 for(j=i+1:j<CurrentSie; j++) if( Vector[).key vector[key )vector[].count++ else Vector).count++ for(i=0: i< Current Sie; i++) ∥在c->ecor[]中各就各位 c->Vector[ Vector]. count]=Vector[: for(i=0;i< Currentsize;i+) Vector[=c-> Vector;/结果复制回当前表对象中 delete c: 9-22试证明对一个有n个对象的序列进行基于比较的排序,最少需要执行 nlog,l次关键码 比较 【解答】 9-23如果某个文件经内排序得到80个初始归并段,试问 1)若使用多路归并执行3趟完成排序,那么应取的归并路数至少应为多少? (2)如果操作系统要求一个程序同时可用的输入输出文件的总数不超过15个,则按多 路归并至少需要几趟可以完成排序?如果限定这个趟数,可取的最低路数是多少? 【解答】 (1)设归并路数为k,初始归并段个数m=80,根据归并趟数计算公式S=「ogm1= 「log80]=3得:k3≥80。由此解得k≥3,即应取的归并路数至少为3。 (2)设多路归并的归并路数为k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区 对应1个文件,有k+1=15,因此k=14,可做14路归并。由S=「logm1=「og801=2 即至少需2趟归并可完成排序。 若限定这个趟数,由S=「Iog801=2,有80≤k2,可取的最低路数为9。即要在2趟内 完成排序,进行9路排序即可 9-24假设文件有4500个记录,在磁盘上每个页块可放75个记录。计算机中用于排序的内 存区可容纳450个记录。试问: (1)可以建立多少个初始归并段?每个初始归并段有多少个记录?存放于多少个页块 (2)应采用几路归并?请写出归并过程及每趟需要读写磁盘的页块数。 【解答】 (1)文件有4500个记录,计算机中用于排序的内存区可容纳450个记录,可建立的初 始归并段有4500/450=10个。每个初始归并段中有450个记录,存于450/75=6个页块 2)内存区可容纳6个页块,可建立6个缓冲区,其中5个缓冲区用于输入,1个缓冲template <class Type> void datalist<Type> :: count_sort ( ) { //initList是待排序表，resultList是结果表 int i, j; int *c = new datalist <Type>; // c是存放计数排序结果的临时表 for ( i = 0; i < CurrentSize; i++ ) Vector[i].count = 0; //初始化，计数值都为0 for ( i = 0; i < CurrentSize-1; i++ ) for ( j = i+1; j < CurrentSize; j++ ) if ( Vector[j].key < Vector[i].key ) Vector[i].count++; else Vector[j].count++; //统计 for ( i = 0; i < CurrentSize; i++ ) //在c->Vector[ ]中各就各位 c->Vector[ Vector[i].count ] = Vector[i]; for ( i = 0; i < CurrentSize; i++ ) Vector[i] = c->Vector[i]; //结果复制回当前表对象中 delete c; } 9-22 试证明对一个有 n 个对象的序列进行基于比较的排序，最少需要执行 nlog2n 次关键码 比较。 【解答】 9-23 如果某个文件经内排序得到 80 个初始归并段，试问 (1) 若使用多路归并执行 3 趟完成排序，那么应取的归并路数至少应为多少？ (2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多 路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？ 【解答】 (1) 设归并路数为 k，初始归并段个数 m = 80，根据归并趟数计算公式 S = logkm = logk80 = 3 得：k 3≥80。由此解得 k≥3，即应取的归并路数至少为 3。 (2) 设多路归并的归并路数为 k，需要 k 个输入缓冲区和 1 个输出缓冲区。1 个缓冲区 对应 1 个文件，有 k +1 = 15，因此 k = 14，可做 14 路归并。由 S = logkm = log1480 = 2。 即至少需 2 趟归并可完成排序。 若限定这个趟数，由 S = logk80 = 2，有 80≤k 2，可取的最低路数为 9。即要在 2 趟内 完成排序，进行 9 路排序即可。 9-24 假设文件有 4500 个记录，在磁盘上每个页块可放 75 个记录。计算机中用于排序的内 存区可容纳 450 个记录。试问： (1) 可以建立多少个初始归并段？每个初始归并段有多少个记录？存放于多少个页块 中？ (2) 应采用几路归并？请写出归并过程及每趟需要读写磁盘的页块数。 【解答】 (1) 文件有 4500 个记录，计算机中用于排序的内存区可容纳 450 个记录，可建立的初 始归并段有 4500∕450 = 10 个。每个初始归并段中有 450 个记录，存于 450∕75 = 6 个页块 中。 (2) 内存区可容纳 6 个页块，可建立 6 个缓冲区，其中 5 个缓冲区用于输入，1 个缓冲 存放结果的表