第7章排序.ppt

7.1 查找与表验证 7.2 排序的定义 7.3 插入排序 7.3.1 直接插入排序 算法的若干变形：1）折半插入排序2）链表插入排序 交换排序 7.4 快速排序 7.7选择排序 7.7.2 堆排序 7.6归并排序 7.8基数排序 7.11外部排序 7.11.1外部排序过程 7.11.2多路平衡归并 7.11.3置换一选择排序 7.12各种排序方法的比较 本章小结 基数排序是和前面所述各类排序方法完全不同的一种排序方法。基数排序(Radix Sort)是一种借助于多关键字排序的思想对单逻辑关键字进行排序的方法，即先将关键字分解成若干部分，然后通过对各部分关键字的分别排序，最终完成对全部记录的排序。 基数排序首先把每个关键字看作为一个d元组： Ki=( Ki 0, Ki 1,…, Ki d-1) 其中，C0≤Ki j≤Cr-1（1≤i≤n，0≤j≤d-1），r称为基数。设置r个桶，排序时先按Ki d-1从大到小将记录分配到r个桶中，然后依次收集这些记录，称之为一趟基数排序。再按Ki d-2从大到小将记录分配到r个桶中，如此反复，直到对Ki0分配和收集，得到的便是排好序的序列。基数r的选择和关键字的分解法因关键字的类型而异。关键字为十进制整数时，r=10，C0=0，Cr-1=9，关键字的每一位取值为0≤Ki j≤9，d为关键字的最大位数。关键字为二进制数时，r=2，C0=0，Cr-1=1，关键字的每一位取值为0或1，d为关键字的最大位数。关键字为字母串时，r=26，C0=’A’，Cr-1=’Z’，关键字的每一位取值为’A’≤Ki j≤’Z’，d为关键字中字母的最大长度。 基数排序时，为了实现记录的分配和收集，可以设置r个队列，排序前均为空队列，分配时将记录分别插入到各自的队列中去，收集时将这些队列中的记录排列在一起。使用数组F[ ]和E[ ]分别保存各个队列的头、尾指针。设置数组R存放待排序记录序列，并令表头结点head指向第一个记录，R数组元素的类型描述为： typedef struct dataType { char key[d]; //记录中的关键字 struct dataType *next; //指向下一个记录的下标 elemtype otherelement; //记录中的其他数据 }srecord; 算法描述为： void RadixSort(srecord *head,srecord*F[],srecord*E[],int d,int r) {//head是指向待排序记录链表的头指针，r为基数，d为每个关键字的最大位数 int i,j,k; srecord *p,*q; for(i=0;id;i++) //循环d次，对各位进行分配和收集 { for(j=0;jr;j++) //清空保存各个队列头、尾指针的数组 { F[j]=NULL; E[j]=NULL; } p=head; While(p!=NULL) //进行待排序记录的分配 {k=(p-key[d-1-i])-‘0’}; //取出关键字的(d-1-i)位的值，用于判断将当前记录链到哪个队列 if(F[k]==NULL) //将记录添到第k个队列尾部 F[k]=p; else E[k]-next=p; E[k]=p; //修改尾指针 p=p-next; } head=NULL; //head作为收集新记录链表的头指针 q=NULL; //q作为新记录链表的尾指针 for(j=0;jr;j++) //收集按关键字(d-1-i)位分配的记录 { if(F[j]!=NULL) { if(head!=NULL) q-next=F[j]; //将第j个“桶”链接到head链表中 else head=F[j]; q=E[j]; } } q-next=NULL; } } 上述算法中，由while循环完成记录的分配，每个记录应存放到哪个队列中与关键字(d-1-i)位的取值有关，关键字(d-1-i)位的值通过语句p-key[(d-1-i)]-‘0’获得。由内层第二个for循环完成对已分配记录的收集。 【例7-9】