[工学]第九章.ppt

另一方法是首先根据关键字的最低位(个位)有效数字进行排序，然后根据次低位(十位)有效数字进行排序，依次类推，直到根据最高位有效数字进行排序，产生一个有序序列，这种方法称最低位优先法(Least Significant Digit)，简称LSD法。 现用LSD法进行基数排序。假设有n个记录，其关键字在0～999之间，每一位上有效数字值在0～9之间共10种可能性，则认为基数是10，在进行“分配”操作时涉及10个队列，即队列的个数与基数相同。此处关键字最多位数是3，那么就需进行3趟“分配”和“收集”操作。 算法思路： (1) 第一趟“分配”，根据关键字的个位有效数字，把所有记录分配到相应的10个队列中去。用f[0]，e[0]表示0号队列的头、尾指针，f[9]，e[9]表示9号队列的头、尾指针。例如，关键字为184的记录就分配到4号队列中去。 (2) 第一趟“收集”把所有非空队列(10个队列中可能有空队)按队列号由小到大的顺序头、尾相接，收集成一个新的序列。此序列若观察其关键字的个位，则它是有序的；若观察其关键字的高位，则它尚处于无序状态。 (3) 以后各趟，分别根据关键字的十位、百位有效数字重复类同第(1)、(2)步的“分配”与“收集”操作，最终得到一个按关键字由小到大的序列。 例9.8 有一组关键字{278,109,063,930,589,184,505,269,008,083}，将它们按由小到大的顺序排序。 操作的具体过程见图9.13。 图9.13(a)是待排序的关键字序列的初始状态。 图9.13(b)是按每个关键字的个位有效数字将它们分配到相应的队列中去。例如，关键字008，278都分配到了8号队列中去，e[8]指向队尾，f[8]指向队头。 图9.13(c)是将6个非空队列(0号，3号，4号，5号，8号，9号)头尾相接收集在一起之后得到的一个新的序列。 图9.13(d)是按每个关键字十位上的有效数字重新将它们分配到相应的队列中去，例如，关键字589、184、083都分配到了8号队列中去。然后再次收集，形成如图9.13(e)所示的新的序列。 图9.13(f)则是按百位上的有效数字分配之后的各队列状态。图9.13(g)则是再次收集后的结果，这也是基数排序所得到的最终的有序序列。 在本章前几节的讨论中，待排序的记录是用向量r做存储结构。基数排序又是“分配”队列，又要“收集”起来，故适用于链表形式存储。本节不采用动态链表而仍用向量r存储(即一维数组)，让每个存放记录的数组元素增加一个指针域。此域为整型，用来存放该记录的下一个相邻记录所在数组元素的下标。这种结构称为静态链表结构。所谓队列的头、尾指针也是整型，它们记下可做某号队列头或队尾元素的记录在数组r中的下标值。记录结构为： struct node {int key; /*关键字域*/ int oth; /*其他信息域*/ int point; /*指针域*/ } 图9.13 基数排序示例 初始状态；(b) 第一趟分配后；(c) 第一趟收集后；(d) 第二趟分配后； (e) 第二趟收集后；(f) 第三趟分配之后；(g) 第三趟收集之后 (2) 递归算法： 算法9.7 void quicksort2(node r[?],int l,int h) { if(lh){ i=hoare(r,l,h); /*划分两个区*/ quicksort2(r,l,i-1); /*对左分区快速排序*/ quicksort2(r,i+1,h); /*对右分区快速排序*/ } } /*quicksort2*/ 在主程序调用非递归算法时比较简单易懂。若要调用递归算法，因函数的形参不同，需做预处理。主程序的主要操作如下： 调用递归函数 调用非递归函数 {creat(r,n); {creat(r,n); l=1;h=n; quicksort1(r,n); quicksort2(r,l,h); 输出r; 输出r; } } 3) 快速排序算法空间时间及稳定性分析 快速排序的非递归算法引用了辅助栈，它的深度为lbn。假设每一次分区处理所得的两个子区长度相近，那么可入栈的子区长度分别为