假设含n个记录的序列为{R1, R2, …, Rn}.ppt

void merge(RecordNode *r,RecordNode *r1,int low,int m,int high) { int i,j,k; i=low; j=m+1; k=low; while( (i=m) (j=high) ) { if(r[i].key=r[j].key) r1[k++]=r[i++]; else r1[k++]=r[j++]; } while (i=m) r1[k++]=r[i++]; while (j=high) r1[k++]=r[j++]; } void mergePass(RecordNode r[], RecordNode r1[], int n, int length) { int i, j; i=0; while(i+2*length-1n) { merge(r,r1,i,i+length-1,i+2*length-1); i+=2*length; } if(i+length-1n-1) merge(r,r1,i,i+length-1,n-1); else for(j=i; jn; j++) r1[j]=r[j]; } void mergeSort(SortObject * pvector) { RecordNode record[MAXNUM]; int length; length=1; while(lengthpvector-n) { mergePass(pvector-record,record, pvector-n,length); length*=2; mergePass(record,pvector-record, pvector-n,length); length*=2; } } 性能分析: 时间复杂度: O(nlog2n) 空间复杂度: 和待排记录等量的空间. 特点: 为稳定排序法. 一般情况下很少用于内部排序. 是和前面所述的排序法完全不同的一类排序法。前面 排序法的基本操作是比较和移动记录，而基数排序则是一 种借助于多关键字排序思想对单逻辑关键字进行排序的方 法，不需要进行关键字的比较。 什么是多关键字的排序？以扑克牌为例，有花色和点 数两种关键字。 一般情况下假设有n个记录的序列{R1, R2, …, Rn}， 且每个记录Ri中含有d个关键字(Ki0, Ki1, …, Kid-1)，在该 序列对关键字有序是指：对应序列中任意两个逻辑Ri和 Rj（1 = i j = n)都满足下列关系： (Ki0, Ki1, …, Kid-1) (Kj0, Kj1, …, Kjd-1) 其中K0称为最主位关键字，Kd-1称为最次位关键字。为实 现排序，通常有两种方法：第一种方法是先对最主位关键 字K0进行排序，然后分别就每个子序列对关键字K1进行排 7.6基数排序 * （1）内部排序和外部排序？ 排序的确切定义： 假设含n个记录的序列为 {R1, R2, …, Rn} 其相应的关键字序列为 {K1, K2, …, Kn} 需确定1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字 满足如下的非递减（或非递增）关系 第七章 排序7.1基本概念 即使序列称为一个按关键字有序的序列 这样一种操作称为排序。 上述排序中的关键字可以是主关键字，也可以是次关 键字，如果是主关键字，则排序结果是唯一的；若是次关 键字排序结果可能不是唯一的。假设Ki=Kj(1=i,j=n,i?j)， 且在排序前的序列中Ri领先于Rj(即ij)，若在排序后的序列 中Ri仍领先于Rj，则称所用的排序方法是稳定的，否则是不 稳定的。 （2）排序中的基本操作： 比较关键字大小 移动记录 前一种基本操作对大多数的排序方法是必须的，而后一个 操作可以通过改变记录的存储方式来予以避免。 （3）待排序记录的存储方式： 存放在地址连续的一组存储单元中，记录之间的关系由存储位置决定，排序必须移动记录； 存在静态链表中，记录之间的关系由指针指示，排序不用移动记录，指向修改指针； 待排序记录本身存储在一组地址连续的存储单元内，同时附设一个指示记录存储位置的地址向量，排序过程中不移动记录，而移动地址向量中这些记录的地址，在排序结束后，再按照地址向量中的值调整记录的存储位置。 （4）顺序