严蔚敏版数据结构(C语言版)PPT-第十章 课件原版

1、1数数 据据 结结 构构10.1 概述概述10.2 插入类排序插入类排序10.4 选择类排序选择类排序第第10章章 内部排序内部排序10.3 交换类排序交换类排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的总和比较各种排序方法的总和比较2数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序排序排序是计算机内经常进行的一种操作，其目的是将是计算机内经常进行的一种操作，其目的是将一组一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序的记录序列。列。例如：将下列关键字序列例如：将下列关键字序列52, 49, 80, 36, 14,

2、58, 61, 23, 97, 7552, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为调整为14, 23, 36, 49, 52, 58, 61, 75, 80, 9714, 23, 36, 49, 52, 58, 61, 75, 80, 973数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序排序的排序的定义定义：假设含假设含n个记录个记录的序列为的序列为 a0, a1, ， an-1 其相应的其相应的关键字关键字序列为序列为 K0, K1, ，Kn-1 这些关键字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着

3、这样一个关系它们之间存在着这样一个关系 ： Kp0Kp1Kpn-1按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 ap0, ap1, ，apn-1 的操作称作的操作称作排序排序。4数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序排序排序内部排序内部排序外部排序外部排序整个排序过程整个排序过程不需要访问外存不需要访问外存便能完成。便能完成。若参加排序的记录数量很大，整个序列的排若参加排序的记录数量很大，整个序列的排序过程序过程不可能在内存中不可能在内存中完成。完成。稳定排序稳定排序不稳定排序不稳定排序排序排序相同关键字的领先关系在排序过程中未发生变

4、化。相同关键字的领先关系在排序过程中未发生变化。相同关键字的领先关系在排序过程中发生变化。相同关键字的领先关系在排序过程中发生变化。5数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序内部排序的过程：内部排序的过程：是一个逐步扩大记录的有序序列长度的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区内部排序的方法内部排序的方法6数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序基于不同的基于不同的“扩大扩大” 有序序列长度的方法，有序序列长度

5、的方法，内部排序方法大致可分下列几种类型：内部排序方法大致可分下列几种类型：插入类插入类交换类交换类选择类选择类 归并类归并类其它方法其它方法7数数 据据 结结 构构10.1 概述概述第第10章章 内部排序内部排序待排记录的数据类型定义如下待排记录的数据类型定义如下:#define MAXSIZE 1000typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList; 8数数 据据 结

6、结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序将将无序无序子序列中的一个或几个记录子序列中的一个或几个记录“插入插入”到到有有序序序列中，从而序列中，从而增加增加记录的记录的有序有序子序列的子序列的长度长度。有序序列有序序列a1.i-1a1.i-1ai 无序序列无序序列 ai.n-1ai.n-1一趟直接插入排序的基本思想：一趟直接插入排序的基本思想：有序序列有序序列a1.ia1.i无序序列无序序列 ai+1.n-1ai+1.n-19数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进

7、行：3将将ai 插入插入(复制复制)到到aj+1的位置上。的位置上。2将将aj+1.i中的所有记录均后移一个位置；中的所有记录均后移一个位置；1在在a1.i-1中查找中查找ai的插入位置，的插入位置， a1.j.key ai.key aj+1.i.key；10数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）表插入排序（基于链

8、表存储）表插入排序（基于链表存储）11数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序利用利用顺序顺序查找实现在查找实现在r1.i-1中中查找查找ri的插入位置的插入位置4862 357755 143598第第1 趟趟4862r06235235486237777455556277514 1435 4855627763535485562 7779898从从ri-1起向前进行顺序查找，监视哨设置在起向前进行顺序查找，监视哨设置在r0；r0 = ri; 循环结束表明循环结束表明ri的插入位置为的插入位置为 j +1r0jrifor (j=i-

9、1; r0.keyrj.key; -j); j=i-1插入位置插入位置12数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序对于在查找过程中找到的那些关键字不小于对于在查找过程中找到的那些关键字不小于ri.key的记录，并在查找的同时实现记录向后移动；的记录，并在查找的同时实现记录向后移动；for (j=i-1; r0.keyrj.key; -j); rj+1 = rj；上述循环结束后可以上述循环结束后可以直接直接进行进行“插入插入” rj+1 = r0；r0jrij=i-1插入位置插入位置直接插入排序直接插入排序13令令 i = 2，3，, n, 实现整个序列

10、的排序。实现整个序列的排序。for ( i=2; i=n; +i ) if (ri.keyri-1.key) 在在 r1.i-1中查找中查找ri的插入位置的插入位置; 插入插入ri ; 数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序14数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序void InsertionSort ( SqList &L ) for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.

11、ri; for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0; 15内部排序的时间分析：内部排序的时间分析：实现内部排序的基本操作有两个：实现内部排序的基本操作有两个：（2）“移动移动”记录。记录。（1）“比较比较”序列中两个关键字的大小；序列中两个关键字的大小；数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序16对对于于直直接接插插入入排排序序最好的情况最好的情况（关键字在记录序列中（关键字在记录序列中顺顺序有序）：序有序）：“比较比较”的次数：的次数：最

12、坏的情况最坏的情况（关键字在记录序列中（关键字在记录序列中逆序逆序有序）：有序）：“比较比较”的次数：的次数：112nni0 02) 1)(4() 1(2nnini“移动移动”的次数：的次数：“移动移动”的次数：的次数：2) 1)(4() 1(2nnini数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序直接插入排序直接插入排序17数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序折半插入排序折半插入排序因为因为 r1.i-1 是一个按关键字有序的是一个按关键字有序的有序有序序列，则序列，则可以利用可以利用折半查找折半查找实现实现

13、“在在r1.i-1中查找中查找ri的插的插入位置入位置”，如此实现的插入排序为，如此实现的插入排序为折半插入排序折半插入排序。14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如例如: :插入插入位置位置L.r18数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序折半插入排序折半插入排序void BiInsertionSort ( SqList &L ) 在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=low; -j ) L.rj+1 = L.rj; L.rlo

14、w = L.r0; 19数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序折半插入排序折半插入排序low = 1; high = i-1;while (low=high) m= (low+high)/2; if (L.r0.key L.rm.key) high = m-1; else low = m+1; 在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；20数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序希尔排序希尔排序基本思想：基本思想：对待排记录序列先作对待排记录序列先作“宏观宏观”调整，再作调整，再作“微观微

15、观”调调整。整。所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排的插入排序。序。（又称缩小增量排序）（又称缩小增量排序）21将记录序列分成若干子序列，分将记录序列分成若干子序列，分别对每个子序列进行插入排序。别对每个子序列进行插入排序。其中，其中，d d 称为增量，它的值在排序过程中从称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为大到小逐渐缩小，直至最后一趟排序减为1 1。例如：将例如：将 n n 个记录分成个记录分成 d d 个子序列：个子序列： R1 R1，R1+dR1+d，R1+2dR1+2d，R1+kd R1+kd R2 R2，R2+dR2+

16、d，R2+2dR2+2d，R2+kd R2+kd Rd Rd，R2dR2d，R3dR3d，RkdRkd，R(k+1)d R(k+1)d 数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序希尔排序希尔排序 （又称缩小增量排序）（又称缩小增量排序）具体做法为：具体做法为：22数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序希尔排序希尔排序 （又称缩小增量排序）（又称缩小增量排序）4655134294170570d1=4465513429417057017550513d2=2461705429455137005134694d3=105

17、171342465594701317709423数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序希尔排序希尔排序 （又称缩小增量排序）（又称缩小增量排序）void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; L.rj+dk = L.r0; 24数数 据据 结结 构构10.2 插入类排序插入类排序第第10章章 内部排序内部排序希尔排序希尔排序 （又称缩小增量排序

18、）（又称缩小增量排序）void ShellSort (SqList &L, int dlta, int t) for (k=0; kt; +t) ShellInsert(L, dltak); 25数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序基本思想：基本思想：通过通过交换逆序元素交换逆序元素进行排序的方法。进行排序的方法。冒泡排序冒泡排序（相邻比逆法）（相邻比逆法）快速排序快速排序通过通过“交换交换”无无序序列中的记录从而得到其中关键字序序列中的记录从而得到其中关键字最小最小或或最大最大的记录，并将它的记录，并将它加入到有序子序列加入到有序子序列中

19、，中，以此方法以此方法增加记录的有序子序列的长度增加记录的有序子序列的长度。26数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序冒泡排序冒泡排序（相邻比逆法）（相邻比逆法）思想：在扫描的过程中思想：在扫描的过程中顺次比较相邻顺次比较相邻的两个的两个 元素的大小，若元素的大小，若逆序逆序就交换位置。就交换位置。48623577551435982240第第1趟趟35625577147735 77229840989次次483562551435772240第第2趟趟7735485514356222408次次第第n-1趟趟 排序结束排序结束n-i次次第第i 趟趟27数数

20、 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序冒泡排序冒泡排序（相邻比逆法）（相邻比逆法）void BubbleSort(RecordType r ,int length) n=length; for(i=1; i=n-1; i+) for(j=1;jrj+1.key) x=aj;rj=rj+1;rj+1=x; 28数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序冒泡排序冒泡排序 时间分析时间分析: :情况情况序列序列起泡次数起泡次数 比较次数比较次数最最好好有有序序1n-1最最坏坏逆逆序序n-1n(n-1)/229数数 据据

21、结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序快速排序快速排序改进冒泡排序中一次交换只能消除一个逆序改进冒泡排序中一次交换只能消除一个逆序的缺点，即实现的缺点，即实现一次交换消除多个逆序一次交换消除多个逆序。思想：思想：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字，凡其关键字小于枢轴小于枢轴的记录均的记录均移动至该记录之前移动至该记录之前，凡其关键字，凡其关键字大于枢轴大于枢轴的记录均的记录均移动至该记录之后移动至该记录之后。即对无序的记录序列进行即对无序的记录序列进行“一次划分一次划分”，之后分别对分割所得之后分别对分割所得两个子序

22、列两个子序列“递归递归”进行进行快速排序快速排序。30数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序快速排序快速排序一次划分（一趟快速排序）一次划分（一趟快速排序）4862357755143598r048lowhighhigh35low62high14low low77highhigh4831数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序快速排序快速排序int QKpass (RecordType r , int low, int high) r0 = rlow; while (lowhigh) while(low= r0

23、.key) - high; rlow = rhigh;while (lowhigh & rlow.key= r0.key) + low; rhigh = rlow;rlow = r0; return low;一趟快速排序算法一趟快速排序算法32void QKSort(RecordType r ,int low,int high) r0=rlow; if(lowhigh) pos=QKpass(r,low,high); QKSort(r,low,pos-1); QkSort(r,pos+1,high);数数 据据 结结 构构10.3 交换类排序交换类排序第第10章章 内部排序内部排序快速

24、排序快速排序算法算法33数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序从记录的从记录的无无序子序列中序子序列中“选择选择”关键字关键字最小最小或或最大最大的记录，并将它的记录，并将它加入到有序子序列加入到有序子序列中，中，以此方法以此方法增加记录的有序子序列的长度增加记录的有序子序列的长度。简单选择排序简单选择排序堆排序堆排序树型选择树型选择排序排序34数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序简单选择排序简单选择排序4862357755143598i第第 1 趟趟kjjkjjj kjj14482i kj3562335

25、624487755566277777898void SelectSort(RecordType r ,int n) n=length; for(i=1;i=n-1;i+) k=i; for(j=i+1;j=n; +j) if(rj.keyrk.key) k=j; if(k!=i) x=ri;ri=rk;rk=x; 35数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序树型选择排序树型选择排序是一种按是一种按锦标赛锦标赛的思想进行排序的方法。的思想进行排序的方法。493827659776491338651327381313761327272749493838494

26、9494965494976656597977676979736数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序对树型排序的进一步改进。对树型排序的进一步改进。堆是满足下列性质的数列堆是满足下列性质的数列r1, r2, ，rn：或或堆的定义堆的定义:12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如: :是小顶堆是小顶堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆(小顶堆小顶堆)(大顶堆大顶堆)122iiiirrrr122iiiirrrr37rir2i r2

27、i+1 若将该数列视作完全二叉树，则若将该数列视作完全二叉树，则 r2i 是是 ri 的左孩子；的左孩子；r2i+1 是是 ri 的右孩子。的右孩子。例如例如: :数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 4912362765403498817355491414是小顶堆是小顶堆不不38堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序列进行排序。对记录序列进行排序。例如：例如：建大顶堆建大顶堆 98, 81, 49, 73, 36, 27, 40, 55, 64

28、, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交换交换 98 98 和和 1212重新调整为大顶堆重新调整为大顶堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 经过筛选经过筛选数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序391、如何由一个无序序列、如何由一个无序序列“建初堆建初堆”？堆排序的两个问题堆排序的两个问题: 2、输出堆顶后，如何、输出堆顶后，如何“筛选筛选”？数数 据据 结结 构构1

29、0.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序所谓所谓“筛选筛选”指的是，对一棵指的是，对一棵左左/右子树均为堆的完右子树均为堆的完全全二叉树二叉树，“调整调整”根结点使整个二叉树也成为一个堆根结点使整个二叉树也成为一个堆。40数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序4898357755143562489877624841数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序例如：例如： 48, 62, 35, 77, 55, 14, 35, 98486235775514359

30、8显然不是一个堆显然不是一个堆调整调整如何建初堆？如何建初堆？424862357755143598数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序987798776298776248439877356255143548数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序984898776248773577625535626214554814555535483548481435143535353535141444时间复杂度分析时间复杂度分析1. 1. 对深度为对深度为k k的堆，的堆，“筛选筛选”所需进行的关

31、键所需进行的关键字字 比较的次数至多为比较的次数至多为2(k-1)2(k-1)；3. 3. 调整调整“堆顶堆顶”n-1n-1次，总共进行的关键字比较的次次，总共进行的关键字比较的次数数 不超过不超过 2(2( loglog2 2(n-1)(n-1) + + loglog2 2(n-2)(n-2) + + + +loglog2 22 2)2)2n n( ( loglog2 2n n ) ) 因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为O(O(n nloglogn n) )。2. 2. 对对n n个关键字，建成深度为个关键字，建成深度为h h(=(= loglog2 2n n +1)+1)

32、的堆，的堆， 所需进行的关键字比较的次数至多所需进行的关键字比较的次数至多4 4n n；数数 据据 结结 构构10.4 选择类排序选择类排序第第10章章 内部排序内部排序堆排序堆排序45数数 据据 结结 构构10.5 归并类排序归并类排序第第10章章 内部排序内部排序通过通过“归并归并”两个或两个以上两个或两个以上的记录的记录有有序序子序列，逐步增加记录有序序列的长度。子序列，逐步增加记录有序序列的长度。在在内内部排序中，通常采用的是部排序中，通常采用的是2-路路归并排序。归并排序。即：即：将两个位置相邻的记录有序子序列将两个位置相邻的记录有序子序列归并为一个记录的有序序列。归并为一个记录的有

33、序序列。有有 序序 序序 列列 rrl l.n n 有序子序列有序子序列 rrl l.m m 有序子序列有序子序列 rrm+1m+1.n n 46数数 据据 结结 构构10.5 归并类排序归并类排序第第10章章 内部排序内部排序例如：例如：19，13，05，27，01，26，31，1613，1905，2701，2616 ，3105，13，19，2701，16，26，3101，05，13，16，19，26，27，31很少进行内排序，主要用于外排序。很少进行内排序，主要用于外排序。47数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部排序主要利用主要利用分配分配和和收集收集

34、两种基本操作。两种基本操作。典型的就是典型的就是基数类排序基数类排序。多关键字的排序多关键字的排序链式基数排序链式基数排序48数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部排序多关键字的排序多关键字的排序最低位优先最低位优先LSD法法最高位优先最高位优先MSD法先对先对K0进行排序，并按进行排序，并按 K0 的不同值将记录序列分的不同值将记录序列分成若干子序列之后，分别对成若干子序列之后，分别对 K1 进行排序，进行排序，.， 依次类推，直至最后对最次位关键字排序完成为止。依次类推，直至最后对最次位关键字排序完成为止。先对先对 Kd-1 进行排序进行排序，然后对然后

35、对 Kd-2 进行排序，依进行排序，依次类推，次类推，直至对最主位关键字直至对最主位关键字 K0 排序完成为止排序完成为止。排序过程中不需要根据排序过程中不需要根据 “前一个前一个” 关键字的排序结果，关键字的排序结果，将记录序列分割成若干个将记录序列分割成若干个(“前一个前一个”关键字不同的关键字不同的)子子序列。序列。49例如例如: :学生记录含三个关键字学生记录含三个关键字: :系别、班号和系别、班号和班内的序列号，其中以系别为最主位关键字。班内的序列号，其中以系别为最主位关键字。 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3

36、,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下: :数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部排序多关键字的排序多关键字的排序50数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部排序链式基数排序链式基数排序假如多关键字的记录序列中，每个关键字的取值范假如多关键字的记录序列中，每个关键字的取值范围相同，则按围相同，则按LSD法进行排序时，可以采用法进行排

37、序时，可以采用“分配分配-收收集集”的方法，其的方法，其好处是不需要进行关键字间的比较好处是不需要进行关键字间的比较。对于对于数字型或字符型的单关键字数字型或字符型的单关键字，可以看成是，可以看成是由多个由多个数位或多个字符构成的多关键字数位或多个字符构成的多关键字，此时可以采用这种，此时可以采用这种“分配分配-收集收集”的办法进行排序，称作的办法进行排序，称作基数排序法基数排序法。51例如：对下列这组关键字例如：对下列这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其首先按其 “个位数个位数” 取值分别为取值分别为 0, 1, , 9

38、 “分配分配” 成成 10 组，之后按从组，之后按从 0 至至 9 的顺序将的顺序将 它们它们 “收集收集” 在一起；在一起；然后按其然后按其 “十位数十位数” 取值分别为取值分别为 0, 1, , 9 “分配分配” 成成 10 组组，之后再按从，之后再按从 0 至至 9 的顺序将它们的顺序将它们“收集收集”在一起；在一起；最后按其最后按其“百位数百位数”重复一遍上述操作。重复一遍上述操作。数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部排序链式基数排序链式基数排序52在计算机上实现基数排序时，为减少所需辅助存储空在计算机上实现基数排序时，为减少所需辅助存储空间，应采

39、用间，应采用链表链表作存储结构，即作存储结构，即链式基数排序链式基数排序。具体作法为：具体作法为： 待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；“分配分配” ” 时，按当前时，按当前“关键字位关键字位”所取值，将记所取值，将记 录分配到不同的录分配到不同的 “ “链队列链队列” ” 中，每个队列中记中，每个队列中记 录的录的 “ “关键字位关键字位” ” 相同；相同；“收集收集”时，按当前关键字位取值从小到大将时，按当前关键字位取值从小到大将 各队列首尾相链成一个链表各队列首尾相链成一个链表; ;对每个关键字位均重复对每个关键字位均重复 2) 2) 和和 3) 3) 两步。两步。数数 据据 结结 构构10.6 基数排序基数排序第第10章章 内部排序内部