数据结构第十章排序

1、1第十章第十章 内部排序内部排序本章目标本章目标n熟练掌握各内部排序方法的基本思想；理解排熟练掌握各内部排序方法的基本思想；理解排序方法序方法“稳定稳定”和和“不稳定不稳定”的含义。的含义。n掌握排序过程和实现算法；掌握排序过程和实现算法；n掌握各种排序方法时间复杂度的分析方法；掌握各种排序方法时间复杂度的分析方法；n了解各种排序方法的特点（比较和选择）。了解各种排序方法的特点（比较和选择）。10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较各种内部排序方法的比较1

2、0.1 概述概述n所谓排序排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。n各科成绩表；奖学金评定综合分；.内部排序内部排序 外部排序外部排序 将欲处理的记录全部存放到内存中排将欲处理的记录全部存放到内存中排序，数据可被随机存取序，数据可被随机存取 插入式排序插入式排序 交换式排序交换式排序 选择式排序选择式排序 待排序的记录太多，不能同时存放内存中，待排序的记录太多，不能同时存放内存中，排序过程需要借助外存（比如：硬盘）来排序过程需要借助外存（比如：硬盘）来完成，记录需要在内存和外存间移动。完成，记录需要在内存和外存间移动。 排序的分类归并排序归并排序 基数排序基数排序

3、 比较标准比较标准稳定性稳定性 不稳定性不稳定性 排序过后能使关键字相等的记排序过后能使关键字相等的记录保持原顺序中的相对位置录保持原顺序中的相对位置 排序过后不能使关键字相等的排序过后不能使关键字相等的记录保持原顺序中的相对位置记录保持原顺序中的相对位置 49325649272732494956时间复杂度时间复杂度空间复杂度空间复杂度稳定性稳定性排序算法的基本操作排序算法的基本操作大多数排序算法都有两个基本的操作两个基本的操作：(1) 比较比较两条记录的关键字(排序码)大小；(2) 移动移动记录本身或改变指向记录的指针。注意： 第(2)种基本操作的实现依赖于待排序记录的存储方式。据此可分为静

4、态排序静态排序和动态排序动态排序。#define MAXSIZE 20/顺序表的最大长度typedef int KeyType;/定义关键字类型为整数类型typedef structKeyType key;/关键字项InfoType otherinfo;/其他数据项 RedType；/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或作哨兵单元int length;/顺序表的当前长度 SqList;/ 顺序表类型顺序表类型10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数

5、排序基数排序10.7 各种内部排序方法的比较各种内部排序方法的比较10.2 插入排序插入排序 2. 折半插入排折半插入排序序3. 2-路插入排序路插入排序4. 表插入排序表插入排序 1. 直接插入排序直接插入排序5. 希尔排序希尔排序基本思想：基本思想：（1 1）排序过程分步完成；）排序过程分步完成；（2 2）每步将一个待排序的记录，按其关键字大小，插入到前每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录（有序序列）的适当位置上；面已经排好序的一组记录（有序序列）的适当位置上；（3 3）通过若干步，便可将所有记录全部插入，从而完成排序。）通过若干步，便可将所有记录全部插入

6、，从而完成排序。通常，将这里的每个步骤称为通常，将这里的每个步骤称为“趟趟”。1. 直接插入排序直接插入排序基本操作基本操作：将：将一个待排序的记录按其关键字的大小插一个待排序的记录按其关键字的大小插入到前面已排好序的有序序列中。入到前面已排好序的有序序列中。有序序列有序序列无序序列无序序列125786309412567830941. 直接插入排序直接插入排序有序序列从只有一个记录开始逐次增大；有序序列从只有一个记录开始逐次增大；当插入第当插入第 个记录个记录时时前面的前面的已经排好序已经排好序这时，用这时，用的的关键字与关键字与的关键字依次进行的关键字依次进行比较，找到插入位置后将比较，找到

7、插入位置后将插入，原来位置上插入，原来位置上及以后的所有记录顺次向后移动；及以后的所有记录顺次向后移动；当有序序列大小最终和原始记录集大小相同时排当有序序列大小最终和原始记录集大小相同时排序完毕。序完毕。1. 直接插入排序直接插入排序64647 789896 62424556464 89896 62424557 76464 6 62424557 764648989 2424556 67 764648989 556 67 7242464648989 5 57 789896 62424初始序列初始序列: :第一趟排序第一趟排序: :第二趟排序第二趟排序: :第三第三趟趟排序排序: :第四趟排序第四

8、趟排序: :第五趟排序第五趟排序: :Temp 6j89j64j7j61. 直接插入排序直接插入排序算法算法: void InsertSort（SqList &L） for(i=2; i=L.length; +i) if LT(L.ri.key, L.ri-1.key) L.r0 = L.ri; for(j=i-1;LT(L.r0.key, L.rj.key); - -j) L.rj+1 = L.rj; L.rj+1 = L.r0; 1. 直接插入排序直接插入排序最坏最坏情况下（逆序）情况下（逆序）： 时间复杂度为时间复杂度为 O(n2)比较次数比较次数：移动次数移动次数：2)1)(2

9、(1- -+ += = = =nn (i+1)n-1i2) 1)(4(2- -+ += =+ + nnin-11= =i）（最好最好情况下（正序）情况下（正序）： 比较次数比较次数：n-1移动次数移动次数：0时间复杂度为时间复杂度为 O(n)性能分析性能分析: :空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。特点：简单、容易实现，适用于待排序记录基本有特点：简单、容易实现，适用于待排序记录基本有序或待排序记录较少的情形。序或待排序记录较少的情形。2. 折半插入排序折半插入排序557 76464 6

10、 62424557 764648989 242489896 6第二次排序第二次排序: :第三次排序第三次排序: :Tfmp 689647low6基本思想基本思想:在查找插入位置时,使用折半查找算法。mhigh2. 折半插入排序折半插入排序算法算法: void BInsertSort (SqList &L) for(i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high+1;-j)L.rj+1=L.rj;L.rhigh+1=L.r0;/for/BInsertSort2. 折半插入排序折半插入排序q稳定稳定q空间代价空间代价：O(

11、1)q时间代价时间代价：n比较次数与待排记录的初始顺序无关，只依赖记录个数 n 插入每个记录需要O(log2i)次比较n 最多移动i+1次，最少2次（临时记录）n 最佳情况下总时间代价为O(nlog2n) ，最差和平均情况下仍为O(n2)3. 2-路插入排序路插入排序n基本思想基本思想：增设同类型数组d,视为循环向量。以d1为中心，原数列中比d1小的往前插，比d1大的往后插n原数列原数列：49 38 65 97 76 13 27 49nd数组数组： 49d1first final38first65 97final76final13first27first9749finalvoid TwoWay

12、Sort(SqList &L) int first=1, final=1, i, j; RedType dMAXSIZE+1; /辅助存储辅助存储 d1.key=L.r1.key; for(i=2;i=d1.key) /插入插入d1后后 for(j=final; dj.keyL.ri.key; j-) dj+1.key=dj.key; dj+1.key=L.ri.key; final+; else /插入插入d1前前 if(first=1) first=MAXSIZE-1; dfirst.key=L.ri.key; else for(j=first; dj.keyL.ri.key&am

13、p;dj.key &jMAXSIZE; j+) dj-1.key=dj.key; dj-1.key=L.ri.key; first-; /for for(i=first, j=1; L.rj.key; i=i%(MAXSIZE-1)+1,j+) L.rj.key=di.key; /将序列复制回去将序列复制回去4. 希尔排序希尔排序 基本思想基本思想：把待排序的数据元素分成若干把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成了入法排序；小组的个数逐次缩小；当完成了所有数据元素都在一个组内的排序后排序

14、过所有数据元素都在一个组内的排序后排序过程结束。程结束。 希尔排序又称作希尔排序又称作缩小增量排序缩小增量排序。 4. 希尔排序希尔排序6565 343425258787 121238385656 464614147777 92922323565665651414252577778787383823235656343414147777121223236565464625258787929238386565777712123434565612121414656534342323777746462525878792923838121214142323252534343838464656566565

15、777787879292结果序列结果序列4. 希尔排序希尔排序void ShellInsert(SqList &L, int dk)/1.前后记录位置的增量是dk,而不是1;/2.r0只是暂存单元,不是哨兵。当j=0时,插入位置已找到。for(i=dk+1;i0&LT(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入 4. 希尔排序希尔排序void ShellSort(SqList &L, int dlta, int t)/按增量序列dlta0.t-1对顺序表L作希尔排序。for(k=0

16、;kai+1aiai+1，则交换两，则交换两个数据元素，否则不交换。个数据元素，否则不交换。 当完成一趟交换以后，最大的元素将会出现在数组的当完成一趟交换以后，最大的元素将会出现在数组的最后一个位置。最后一个位置。 依次重复以上过程，当第依次重复以上过程，当第n-1n-1趟结束时，整个趟结束时，整个n n个数据个数据元素集合中次小的数据元素将被放置在元素集合中次小的数据元素将被放置在a1a1中，中，a0a0中放中放置了最小的数据元素。置了最小的数据元素。起泡排序4938659776132749979797384927137665493849276513493849271349384927133

17、827137676654949382713特点：特点：1.n个数排序共需进行n-1趟比较2.第i趟共需要进行n-i次比较起泡排序的原始算法nvoid bubble_sort(SqList &L)n/将a中整数序列排列成自小至大有序的序列(起泡排序)nfor(i=1,i=L.length-1;+i)n for(j=1;j=L.length-1;+j)nif(LT(L.rj+1.key,L.rj.key)nL.rjL.rj+1；n起泡排序的改进算法（一）void bubble_sort(SqList &L)/将a中整数序列排列成自小至大有序的序列(起泡排序) for(i=1;i=L

18、.length-1;+i) for(j=1;j=L.length-i;+j)if(LT(L.rj+1.key,L.rj.key)L.rjL.rj+11 15 24 6 17 5 1 15 6 17 5 241 15 6 17 5 241 6 15 5 17 24注意第注意第i趟比较了趟比较了n-i次，则可以有效的较少比较次数次，则可以有效的较少比较次数问题：刚才的改进算法是否已经最优问题：刚才的改进算法是否已经最优 ?起泡排序的改进算法（二）1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 分析：分析

19、：因为给定的待排序序列已经是一个正序的序列因为给定的待排序序列已经是一个正序的序列，经过第一趟的比较以后，已经没有交换发生，但，经过第一趟的比较以后，已经没有交换发生，但是算法仍然会继续执行。是算法仍然会继续执行。解决：解决：添加一个算法的结束条件，即当某一趟排序添加一个算法的结束条件，即当某一趟排序过程中只有比较而没有交换的时候，就认定序列已过程中只有比较而没有交换的时候，就认定序列已经有序，可以提前结束循环。经有序，可以提前结束循环。起泡排序的改进算法（二）void bubble_sort(SqList &L)/将a中整数序列排列成自小至大有序的序列(起泡排序)for(i=1,ch

20、ang=TRUE；(i=L.length-1)&chang;+i)chang=FALSE;for(j=1;jL.length-i;+j)if(LT(L.rj+1.key,L.rj.key)L.rjL.rj+1;change=TRUE;最坏情况（反序）：最坏情况（反序）：最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情况：平均

21、情况：时间复杂度为时间复杂度为O(n2)。时间性能分析快速排序快速排序n算法思想：算法思想：n指定枢轴指定枢轴(通常为第一个记录通常为第一个记录) n通过一趟排序将以枢轴为中心，把待排记通过一趟排序将以枢轴为中心，把待排记录分割为独立的两部分，使得左边记录的录分割为独立的两部分，使得左边记录的关键字小于枢轴值，右边记录的关键字大关键字小于枢轴值，右边记录的关键字大于枢轴值于枢轴值a.对左右两部分记录序列重复上述过程，依对左右两部分记录序列重复上述过程，依次类推，直到子序列中只剩下一个记录或次类推，直到子序列中只剩下一个记录或不含记录为止。不含记录为止。快速排序快速排序4938659776132

22、749pivotkey=49lowhigh27low65high13low97highhigh49第一趟结果：第一趟结果： 27 38 13 27 38 13 4949 76 97 65 76 97 65 4949 小于小于49大于等于大于等于4949快速排序算法快速排序算法 int Partition(SqList &L, int low, int high) L.r0=L.rlow;/用子表的第一个记录作枢轴记录pivotkey=L.rlow.key;/枢轴记录关键字while(lowhigh)/从表的两端交替地向中间扫描while(low=pivotkey)-high;L.rlo

23、w=L.rhigh;/将比枢轴记录小的记录移到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/将比枢轴记录大的记录移到高端L.rlow=L.r0;/枢轴记录到位returnlow;/返回枢轴位置 快速排序算法快速排序算法void QSort(SqList &L, int low, int high)/对顺序表L中的/长度大于1 if(lowhigh) pivotloc=Partition(L,low,high);/将L.rlow.high一分为二QSort(L,low,pivotloc-1);/对低子表递归排序，

24、pivotloc是枢轴位置QSort(L,pivotloc+1,high);/对高子表递归排序 void QuickSort(SqList &L)/对顺序表L作快速排序。算法10.8QSort(L,1,L.length);算法分析算法分析n在在n个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为O(n)。若设。若设 t(n) 是对是对 n 个元素的序列进行排序所个元素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的把序列划分为长度相等的两个子序列，此时，总的

25、计算时间为：计算时间为：T(n)cn+2t(n/2)/c是一个常数cn+2(cn/2+2t(n/4)=2cn+4t(n/4)2cn+4(cn/4+2t(n/8)=3cn+8t(n/8)cnlog2n+nt(1)=o(nlog2n)10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较各种内部排序方法的比较直接选择排序直接选择排序n基本思想：基本思想：从待排序的数据元素集合中选从待排序的数据元素集合中选取最小的数据元素并将它与原始数据元素取最小的数据元素并将它与原始数据元

26、素集合中的第一个数据元素交换位置；然后集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中从不包括第一个位置上数据元素的集合中选取最小的数据元素并将它与原始数据元选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数此重复，直到数据元素集合中只剩一个数据元素为止。据元素为止。 直接选择排序直接选择排序149238365497576613727849ki=1jkjjjjkjjk1349直接选择排序直接选择排序149238365497576613727849i=kjjjjjj1349kk2

27、voidSelectSort(SqList&L)for(inti=1;iL.length;i+)k=SelectMinKey(L,i);if(i!=k)L.riL.rk;voidSelectMinKey(SqList&L,constinti)intk=i;for(j=i+1;j=L.length;j+)if(L.rj.keyL.rk.key)k=j;/当前具最小关键码的对象returnk;直接选择排序的算法直接选择排序的算法最坏情况：最坏情况：3(n-1)次次直接选择排序算法的性能分析直接选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次比较次

28、数：比较次数：)() 1(21211nOnninni= =- -= =- - - -= =）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。树形选择排序树形选择排序n排序思想：排序思想：首先取得首先取得 n 个对象的关键码，个对象的关键码，进行两两比较，得到进行两两比较，得到 n/2 个比较的优胜者个比较的优胜者(关键码小者关键码小者)，作为第一步比较的结果保留，作为第一步比较的结果保留下来。然后对这下来。然后对这 n/2 个对象再进行关键个对象再进行关键码的两两比较，码的两两比较，如此重复，直到选出，如此重复，直到选出一个关键码最小的对象为止。一个关键码最小的对象为止。13

29、3813973865493876131327652749139749387613652749381338651327273827386576272797493876136527493827386576271338384938657649算法分析算法分析n除第一次选择具有最小关键码的对象需要进行除第一次选择具有最小关键码的对象需要进行 n-1 次关键码比较外，重构胜者树选择具有次次关键码比较外，重构胜者树选择具有次小、再次小关键码对象所需的关键码比较次数小、再次小关键码对象所需的关键码比较次数均为均为 O(log2n)。总关键码比较次数为。总关键码比较次数为O(nlog2n)。n对象的移动次数不

30、超过关键码的比较次数，故对象的移动次数不超过关键码的比较次数，故锦标赛排序总的时间复杂度为锦标赛排序总的时间复杂度为O(nlog2n)n这种排序方法虽然减少了许多排序时间，但是这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。使用了较多的附加存储。堆排序堆排序n把待排序的数据元素集合构成一个完全二叉把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）树结构，则每次选择出一个最大（或最小）的数据元素的数据元素n设数组设数组a中存放了中存放了n个数据元素，数组下标从个数据元素，数组下标从0开始，如果当数组下标开始，如果当数组下标2i+1n时有：时有：aia2i+

31、1；如果当数组下标；如果当数组下标2i+2n时有时有：aia2i+2，则这样的数据结构称为，则这样的数据结构称为最大最大堆堆。性质性质5（2）如果）如果2i+1n，则序号为，则序号为i结点的左孩子结点的序号为结点的左孩子结点的序号为2i+1；如果；如果2i+1n，则序，则序号为号为i结点无左孩子结点。结点无左孩子结点。堆排序堆排序(续续)n设数组设数组a中存放了中存放了n个数据元素，数组下标从个数据元素，数组下标从0开始，如果当数组下标开始，如果当数组下标2i+1n时有：时有：aia2i+1；如果当数组下标；如果当数组下标2i+2n时有：时有：aia2i+2，则这样的数据结构称为，则这样的数据

32、结构称为最小堆最小堆。9683273811091236248547913053堆排序堆排序基本思想：基本思想：n以初始关键字序列，建立堆；以初始关键字序列，建立堆； n输出堆顶最小元素；输出堆顶最小元素；n调整余下的元素，使其成为一个新堆；调整余下的元素，使其成为一个新堆；n重复重复2, 3步，直到步，直到n个元素输出，得到个元素输出，得到 一个一个有序序列。有序序列。关键问题：关键问题：n如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆? 1.如何调整余下的元素成为一个新堆如何调整余下的元素成为一个新堆? 堆调整过程堆调整过程1338277697654949rc=13筛选过程筛选过程

33、void HeapAdjust (SqList R, int s, int m) /已知Rs.m中记录的关键字除Rs.key之外均满足堆的定义，本函数调整Rs的关键字，使Rs.m成为一个大顶堆rc=Rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选if(jm&Rj.key=Rj.key)break;/rc应插入在位置s上Rs=Rj;s=j;Rs=rc;/插入/HeapAdjust建堆过程建堆过程n无序序列建堆过程无序序列建堆过程方法：从完全二叉树的最后一个非叶结点方法：从完全二叉树的最后一个非叶结点 n/2 开始，反复调用筛选过程，直到第开始，反复调用筛选过程

34、，直到第一个结点，则得到一个堆。一个结点，则得到一个堆。建堆算法建堆算法void HeapSort ( SqList R, int n ) /对记录序列R1.n进行堆排序。for ( i=n/2; i0; -i ) /把R1.n建成大顶堆HeapAdjust(R,i,n);for ( i=n; i1; -i ) R1Ri;/将堆顶记录和当前未经排序子序列/R1.i中最后一个记录相互交换HeapAdjust (R,1,i-1); /将R1.i-1重新调整为大顶堆/HeapSort性能分析性能分析q对深度为对深度为k的堆，的堆，“筛选筛选”所需进行的关键字比所需进行的关键字比较的次数至多为较的次数

35、至多为2(k-1);q对对n个关键字，建成深度为个关键字，建成深度为h(= log2n +1)的堆，的堆，所需进行的关键字比较的次数至多为所需进行的关键字比较的次数至多为4n;q调整调整“堆顶堆顶”n-1次，总共进行的关键字比较的次，总共进行的关键字比较的次数不超过次数不超过2( log2(n-1) + log2(n-2) + +log22)2n( log2n )因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为O(nlogn)，不稳定。，不稳定。10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数排序基数排

36、序10.7 各种内部排序方法的比较各种内部排序方法的比较归并排序归并排序n基本思想：基本思想：将一个具有将一个具有n个待排序记录的序个待排序记录的序列看成是列看成是n个长度为个长度为1的有序序列，然后进的有序序列，然后进行两两归并，得到行两两归并，得到n/2个长度为个长度为2的有序序的有序序列，再进行两两归并，得到列，再进行两两归并，得到n/4个长度为个长度为4的有序序列，的有序序列，直至得到一个长度为，直至得到一个长度为n的有序序列为止。的有序序列为止。归并排序过程归并排序过程 (49) (38) (65) (97) (76) (13) (27)(38 49) (38 49 65 97) (

37、13 27 76) (13 27 38 49 65 76 97)(65 97)(13 76)(27)归并排序算法归并排序算法void Merge(RedType SR, RedType &TR, int i, int m, int n) / 将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并为有序的TRi.n int j, k, l; for(j=m+1,k=i;i=m&j=n;+k) / 将将SR中记录由小到大地并入中记录由小到大地并入TR if LQ(SRi.key,SRj.key) TRk=SRi+; else TRk=SRj+; if(i=m) TRkn=SR

38、im; / 将剩余的将剩余的SRi.m复制到复制到TR if(j=n) TRkn=SRjn; / 将剩余的将剩余的SRj.n复制到复制到TR 归并排序算法(续) void MSort(RedType SR, RedType &TR1, int s, int t) / 将将SRs.t归并排序为归并排序为TR1s.t if(s=t) TR1s=SRs; else m=(s+t)/2; / 将将SRs.t平分为平分为SRs.m和和SRm+1.t MSort(SR,TR2,s,m); / 递归地将递归地将SRs.m归并为有序的归并为有序的TR2s.m MSort(SR,TR2,m+1,t);

39、/ 递归地将递归地将SRm+1.t归并为有序的归并为有序的TR2m+1.t Merge(TR2,TR1,s,m,t); / 将将TR2s.m和和TR2m+1.t归并到归并到TR1s.t void MergeSort(SqList &L) / 对顺序表对顺序表L作归并排序。算法作归并排序。算法10.14 MSort(L.r, L.r, 1, L.length); 10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较各种内部排序方法的比较基数排序基数排序n排序思想

40、：排序思想：基数排序是按组成关键字的各位的基数排序是按组成关键字的各位的值进行值进行分配分配和和收集收集，与前面介绍的排序方法不，与前面介绍的排序方法不同，它无需进行关键字之间的比较。同，它无需进行关键字之间的比较。n设关键字有设关键字有d 位，每位的取值范围为位，每位的取值范围为 r (称为称为基数基数)，则需要进行，则需要进行d 趟分配与收集，需要设趟分配与收集，需要设立立 r 个队列。个队列。n例如，关键字是例如，关键字是4位字符串，需要位字符串，需要26个队列，个队列，4趟分配与收集；关键字趟分配与收集；关键字3位十进制数，需要位十进制数，需要10个队列，个队列，3趟分配与收集趟分配与

41、收集基数排序过程基数排序过程278109063930589184505269008083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 278pp109p063p930p589p184p505p269p008p083930063083184505278008109589269 505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 505008109930269063278589184083f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 0080

42、6308310918426927850558993000806318310918426927850558993010.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.1 概述概述10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较各种内部排序方法的比较各种排序方法的比较各种排序方法的比较对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：时间复杂性；时间复杂性；空间复杂性；空间复杂性；稳定性；稳定性；算法简单性；算法简单性；待排序记录个数待排序记录个数n的大小；的大小；记录本身信息量的大小；记录本身信息量的大小；关键码的分布情况。关键码的分布情况。排序方法排序方法最好时间最好时间 平均时间平均时间 最坏时间最坏时间 辅助空间辅助空间 稳定性稳定性 直接插入排直接插入排序序 O(n) O(n2) O(n2) O(1) 稳定稳定 希尔排序希尔排序 O(n1.3)