1、第七章第七章 排序排序71 排序的基本概念72 插入排序73 交换排序74 选择排序75 归并排序*76 基数排序77 内排序方法的比较 71 排序的基本概念1排序对象 由记录序列组成的文件，每一个记录又由若干数据项组成。由于文件是记录的序列，所以从逻辑结构上看它是个线性表 表7.1 学生成绩表2排序排序码 通常把选作排序依据的数据项的值称为排序码。3排序的定义 将一组记录按照某个排序码非递增或非递减的次序重新排列的过程。一条记录一个数据项4排序的稳定性 排序码相同的两个记录经过排序之后，其相对次序保持不变，称该排序方法是稳定的；反之，称该排序方法是不稳定的。5内部排序与外部排序 整个排序过程
2、全部在内存中进行，这种排序称为内部排序。涉及内外存之间数据交换的排序称为外部排序。外部排序的速度比内部排序的速度要慢得多。6.排序两种基本操作：1）比较两个记录排序码的大小；2）将记录从一个位置移动到另一个位置。7.常见排序方法：插入排序、交换排序、选择排序、归并排序、基数排序8排序方法的评价 时间复杂度，空间复杂度、稳定性和简单性等 9记录序列采用顺序存储结构，其C语言描述如下：#define N 20typedef struct int key;/*定义排序码*/DataType other;/*定义其他数据项*/RecType;/*记录的类型*/RecType RN+1;N为待排序记录的
3、个数，R0不存放记录，原因有两个:其一，使数组的下标和记录的序号对应；其二，将R0留作他用，比如做监视哨或者做记录交换的辅助空间。72 插入排序插入排序插入排序（Insertion Sort）的基本思想是：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。插入排序主要包括两种方法：直接插入排序和希尔（Shell）排序。7 72 21 1 直接插入排序直接插入排序 直接插入排序的基本思想基本思想：待排序的n个记录存放在数组R1Rn中，把数组分成一个有序表和一个无序表，开始时有序表中只有一个记录R1，无序表中含有n-1个记录R
4、2Rn。在排序的过程中每一次从无序表中取出第一个记录，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表成为空表，有序表就包含了全部n个记录，排序完毕。将一个记录插入到有序表的过程称为一趟直接插入一趟直接插入排序。排序。举例：排序码初始序列为（举例：排序码初始序列为（7878，3838，3232，9797，7878，3030，2929，1717）R1 R2 R3 R4 R5 R6 R7 R8 78 38 32 97 78 30 29 17 （初始状态）38 78 32 97 78 30 29 17 （插入38后）32 38 78 97 78 30 29 17 （插
5、入32后）32 38 78 97 78 30 29 17 （插入97后）32 38 78 78 97 30 29 17 （插入78后）30 32 38 78 78 97 29 17 （插入30后）29 30 32 38 78 78 97 17 （插入29后）17 29 30 32 38 78 78 97 （插入17后）直接插入排序过程图示直接插入排序算法的C函数如下：void insertSort(RecType R)/*对数组R中的记录进行直接插入排序*/int i,j;for(i=2;i=N;i+)/*待插入记录为R2，RN*/R0=Ri;/*将待插入的记录Ri放入R0中*/j=i-1;w
6、hile(R0.keyRj.key)/*查找记录Ri应该插入的位置*/Rj+1=Rj-;/*将排序码大于Ri.key的记录后移*/Rj+1=R0;/*插入Ri*/直接插入排序算法的性能分析时间效率 最好情况下为O(n)最坏和平均时间复杂度都为O(n2)空间效率 O(1)稳定的排序方法7 72 22 2 希尔排序希尔排序 希尔排序的基本思想基本思想是：将待排序记录序列分成几个组，在每一组内分别进行直接插入排序，使得整个记录序列部分有序；重复此过程，直到所有记录都在同一组中，最后对所有的记录进行一次直接插入排序即可。如何分如何分组 将数组R1Rn的记录分为d个组，使下标距离为d的记录在同一组，即R
7、1，R1+d，R1+2d，.为第一组，R2,R2+d,R2+2d,.为第二组，以此类推，Rd,R2d，R3d,.为最后一组（第d组），这里的d叫做步步长（或增量增量值）。这种分组在每一组内做直接插入排序的时候，记录移动一次，能跨跃较大的距离，从而加快了排序的速度。希尔排序要对记录序列进行多次分组，每一次分组的步长d都在递减，即d1d2d3dt，直到最后一次选取步长dt=1，所有的记录都在一组中，进行最后一次直接插入排序，我们将每一次分组排序的过程称为一趟希一趟希尔排序排序。举例：设排序码初始序列:(36，25，48，65，12，25，43，57，76，32)R1 R2 R3 R4 R5 R6
8、R7 R8 R9 R10 36 25 48 65 12 25 43 57 76 32 （初始状态）36 25 （d1=5）25 43 48 57 65 76 12 32 25 25 48 65 12 36 43 57 76 32 （一趟希尔排序结果）25 65 43 32 （d2=3）25 12 57 48 36 7625 12 36 32 25 48 43 57 76 65 （二趟希尔排序结果）25 12 36 32 25 48 43 57 76 65 （d3=1）12 25 25 32 36 43 48 57 65 76 （三趟希尔排序结果）希尔排序过程图示一趟希尔排序算法的C函数：voi
9、d shellInsert(RecType R,int d)/*按步长d进行分组，每一组分别做直接插入排序*/int i,j;for(i=d+1;i0&Rj.keyR0.key)Rj+d=Rj;j=j-d;/*记录后移，查找插入位置*/Rj+d=R0;/*插入记录*/整个希尔排序算法的C函数：void shellSort(RecType R，int d,int t)/*d0dt-1为每一趟分组的步长*/int k;for(k=0;kt;k+)shellInsert(R,dk);希尔排序算法的性能分析当n较大时，希尔排序的平均时间复杂度在O(nlog 2n)和O(n2)之间，大约为O(n1.5)
10、算法的空间复杂度是O(1)。希尔排序是不稳定的。73 交换排序 交换排序的基本思想基本思想是：两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。本节主要介绍两种交换排序：起泡排序和快速排序。7 73 31 1 起泡排序起泡排序 起泡排序的基本思想基本思想是：首先将记录R1的排序码与记录R2的排序码做比较（从上向下），若R1的排序码大于R2的排序码，则交换两个记录的位置，使排序码大的记录（重者）往下“沉”（移到下标大的位置），使排序码小的记录（轻者）往上“浮”（移到下标小的位置）；然后比较R2和R3的排序码，同样轻者上浮，重者下沉；依此类推，直到比较Rn
11、1和Rn的排序码，若不符合顺序就交换位置，称此过程为一趟起泡排序一趟起泡排序，结果是R1Rn中排序码最大的记录沉“底”，即放入Rn中。接下来，在R1Rn-1中进行第二趟起泡排序，又会将一个排序码最大的记录沉“底”，放到Rn-1中。这样重复进行n-1趟排序后，对于n个记录的起泡排序就结束了，数组R1Rn成为有序表。举例：设有举例：设有8 8个记录的排序码初始序列为个记录的排序码初始序列为（3636，2525，4848，1212，2525，6565，4343，5757）R1 36 25 25 25 25 25 25 25R2 25 36 36 36 36 36 36 36R3 48 48 48
12、12 12 12 12 12R4 12 12 12 48 25 25 25 25R5 25 25 25 25 48 48 48 48R6 65 65 65 65 65 65 43 43R7 43 43 43 43 43 43 65 57R8 57 57 57 57 57 57 57 65一趟排序的过程图示R1 R 2 R 3 R4 R5 R6 R7 R 836 25 48 12 25 65 43 57 （初始状态）25 36 12 25 48 43 57 65 （1趟排序结果）25 12 25 36 43 48 57 65 （2趟排序结果）12 25 25 36 43 48 57 65 （3趟
13、排序结果）12 25 25 36 43 48 57 65 （4趟排序结果）12 25 25 36 43 48 57 65 （5趟排序结果）12 25 25 36 43 48 57 65 （6趟排序结果）12 25 25 36 43 48 57 65 （7趟排序结果）起泡排序的全过程图示起泡排序算法的C函数如下：void bubbleSort(RecType R)RecType x;int i,j,flag;for(i=1;iN;i+)/*i排序的趟数，n个记录最多进行n-1趟排序*/flag=1;/*flag表示每趟排序是否交换，比较之前置为1 ，表示无交换*/for(j=1;jRj+1.ke
14、y)x=Rj;Rj=Rj+1;Rj+1=x;flag=0;if(flag)break;/*若没有交换，表明已有序，结束循环*/起泡排序的性能分析时间效率：起泡排序的最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，可以证明它的平均时间复杂度也为O(n2)。空间效率：在整个算法中，需要一个用于交换记录的辅助空间，所以起泡排序的空间复杂度为O(1)。稳定性：起泡排序是稳定的。7 73 32 2 快速排序快速排序快速排序快速排序(Quick Sort)也被称为划分排序或分区排序，它是目前所有的内部排序方法中速度最快的一种，快速排序是对起泡排序的一种改进。快速排序的基本思想基本思想是：在R1Rn中
15、任意选取一个记录作为“基准记录”，将整个数组划分为两个子区间：R1Ri-1和Ri+1Rn，前一个区间中记录的排序码都小于或等于基准记录的排序码，后一区间中记录的排序码都大于或等于基准记录的排序码，基准记录落在排序的最终位置Ri上，我们称该过程为一次划分（或一趟快速排序）。若R1Ri-1和Ri+1Rn非空，分别对每一个子区间再重复这样的划分，直到所有子区间为空或只剩下一个记录，使整个数组达到有序。举例：排序码初始序列为（49，14，38，74，96，65，8，49，55，27），对其进行快速排序。一次划分的详细操作过程为：（1）选取R1为基准记录，将其复制到R0中；（2）设置两个搜索“指针”并
16、赋初值为：low=1；high=10；（3）若lowhigh，从high位置向前搜索排序码小于R0.key的记录，如果找到，将Rhigh移动到Rlow位置，然后从low位置向后搜索排序码大于R0.key的记录，如果找到，将Rlow移动到Rhigh位置，重复上述操作，直到两个“指针”相遇，即low=high，找到了基准记录的最终排序位置low，由于这个位置的原值已经被移走，可以将R0赋值给Rlow，一次划分完毕。R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 49 14 38 74 96 65 8 49 55 27 14 38 74 96 65 8 49 55 27 l
17、ow=1 high=10从high向前搜索小于R0.key的记录，找到R10，将R10移到Rlow 27 14 38 74 96 65 8 49 55 low=1 high=10 从low向后搜索大于R0.key的记录，找到R4，将R4移到Rhigh 27 14 38 96 65 8 49 55 74 low=4 high=10 从high向前搜索小于R0.key的记录，找到R7，将R7移到Rlow 27 14 38 8 96 65 49 55 74 low=4 high=7 从low向后搜索大于R0.key的记录，找到R5，将R5移到Rhigh 27 14 38 8 65 96 49 55
18、74 low=5 high=7 从high向前搜索小于R0.key的记录，两指针相遇low=high 27 14 38 8 65 96 49 55 74 low high 一次划分结束，填入基准记录：Rlow=R0，此时数组分成前后两个子区间 27 14 38 8 49 65 96 49 55 74 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 14 38 74 96 65 8 49 55 27 初始状态 27 14 38 8 49 65 96 49 55 74 第一层划分结果 8 14 27 38 49 55 49 65 96 74第二层划分结果 8 14 27 38
19、49 49 55 65 74 96 第三层划分结果 快速排序全过程图示一次划分的C函数如下：int partition(RecType R,int low,int high)/*一趟快速排序*/int k;R0=Rlow;/*以子表的第一个记录作为基准记录*/k=Rlow.key;/*取基准记录排序码*/while(lowhigh)/*从表的两端交替地向中间扫描*/while(low=k)high-;if(lowhigh)/*比基准记录小的交换到前端*/Rlow=Rhigh;while(lowhigh)&(Rlow.key=k)low+;if(lowhigh)/*比基准记录大的交换到后端*/R
20、high=Rlow;Rlow=R0;/*基准记录到位*/return low;/*返回基准记录所在位置*/快速排序递归算法的C函数如下void QSort(RecType R,int low,int high)/*对数组R的子区间lowhigh做快速排序*/int part;if(lowhigh)part=partition(R,low,high);/*将表一分为二*/QSort(R,low,part-1);/*对前面的子区间快速排序*/QSort(R,part+1,high);/*对后面的子区间快速排序*/快速排序对应的二叉树起泡排序的性能分析时间效率：最好的情况下，时间复杂度为O(nlog
21、2n）；在最坏情况下，O(n2)；平均时间复杂度仍为O(nlog2n)。空间效率：最好空间复杂度为O(log2n)；最坏空间复杂度为O(n)；平均空间复杂度也为O(log2n)。快速排序是一个不稳定的排序方法。74 选择排序 选择排序排序（Selection Sort）的基本思想是：每一次从待排序记录序列中选取一个排序码最小（或最大）的记录，放在待排序记录序列的最前面（或最后面），重复此过程，直到所有的记录按排序码排好序。本节介绍直接选择排序和堆排序两种方法。7 74 41 1 直接选择排序直接选择排序直接直接选择排序排序（Straight Select Sort）的基本思想是：假定待排序的n
22、个记录存储在数组 R1Rn中，经过比较选出排序码最小的记录，将其同R1交换，也就是将排序码最小的记录放到待排序区间的最前面，完成第一趟直接选择排序（即i=1）。第i（1in-1）趟直接选择排序的结果是将RiRn中排序码最小的记录放到待排序子区间的最前面，即与Ri交换位置。经过n-1趟直接选择排序，R1Rn成为有序表，整个排序过程结束。举例：设有举例：设有8 8个待排序记录的排序码为（个待排序记录的排序码为（2525，3636，4848，6565，2525，1212，4343，5757）。）。R1 R2 R3 R4 R5 R 6 R7 R 825 36 48 65 25 12 43 57 （初始
23、状态）12 36 48 65 25 25 43 57（第1趟排序的结果）12 25 48 65 36 25 43 57 (第2趟排序的结果）12 25 25 65 36 48 43 57 (第3趟排序的结果）12 25 25 36 65 48 43 57 (第4趟排序的结果）12 25 25 36 43 48 65 57 (第5趟排序的结果）12 25 25 36 43 48 65 57 (第6趟排序的结果）12 25 25 36 43 48 57 65 (第7趟排序的结果）直接选择排序过程图示直接选择排序算法的C函数：void selectSort(RecType R)/*用直接选择排序对数
24、组R中的记录进行排序*/RecType x;int i,j,k;for(i=1;iN;i+)/*共进行n-1趟排序*/k=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;直接选择排序的性能分析时间效率：直接选择排序主要时间消耗在比较操作上，其平均时间复杂度为O(n2)。空间效率：在整个算法中，只需要一个用于交换记录的辅助空间，所以直接选择排序的空间复杂度为O(1)。稳定性直接选择
25、排序是不稳定的。7 74 42 2 堆排序堆排序一、堆的定义：设n个元素的序列为（K1，K2，Kn），当且仅当满足下述关系之一时，称之为堆堆。（1）KiK2i且 KiK2i+1，1i n/2（2）KiK2i且 KiK2i+1，1i n/2 满足第（1）个条件的称作小根堆小根堆，满足第（2）个条件的称作大根堆大根堆。例：（12，36，24，85，47，30，53，91），它满足堆定义的第一个条件，因此是小根堆。（91，47，85，24，36，53，30，16），它满足堆定义的第二个条件，因此是大根堆。二、堆与二叉树 如果把存储堆的一维数组看作是完全二叉树的顺序存储结构，就可以把堆转换为完全二叉树
26、来表示。12362485473053919147852436533012三、堆排序的基本思想：利用大（或小）根堆的性质不断地选择排序码最大（或小）的记录来实现排序的，利用大根堆来实现升序排列。（1）首先将R1Rn这n个记录按排序码建成大根堆。（2）然后R1与Rn交换位置，即把排序码最大的记录放到待排序区间的最后；接着，再把R1Rn-1中的n-1个记录建成大根堆，仍然将堆顶R1与Rn-1交换位置。如此反复n-1次，每次选一个排序码最大的记录与本次排序区间的最后一个记录交换位置，最终得到一个有序序列。堆排序需解决两个问题：（1）如何将n个待排序记录按排序码建成堆？（2）交换堆顶记录后，对剩余的n-
27、1个记录重新建堆的过程和前面的建堆过程是否相同？（a）初始大根堆 （b）91与12对换之后 （c）12与85对换之后 （d）12与53对换之后 交换堆顶元素之后 调整堆的过程图示举例：对(49，38，65，97，76，13，27，49)堆排序。（a）8个结点的初始状态（b）筛选97之后的状态（c）筛选65之后的状态（d）筛选38之后的状态（e）筛选49之后的状态 建堆过程图示“筛选法”算法的C函数如下：void heapSift(RecType R,int i,int n)/*Ri为根结点，调整RiRn为大根堆*/RecType rc;int j;rc=Ri;j=2*i;while(j=n)/
28、沿排序码较大的孩子结点向下筛选*/if(jn&Rj.keyRj.key)break；Ri=Rj;/*记录移动到Ri*/i=j;j=j*2;/*调整进入下一层*/Ri=rc;/*找到了根结点最后应插入的位置*/堆排序算法heapSort()的C函数：void heapSort(RecType R,int n)/*对n个记录进行堆排序*/int i;RecType x;for(i=n/2;i=1;i-)/*将RiRn建成堆*/heapSift(R，i，n)；for(i=n;i1;i-)/*进行n-1趟排序*/x=Ri;/*堆顶与最后一个记录交换位置*/Ri=R1;R1=x;heapSift(R，
29、1，i-1);/*将R1Ri-1重新调整为堆*/堆排序的性能分析如下：时间效率：堆排序的时间主要消耗在筛选算法中，一共调用了n/2+n-1（约3n/2）次的筛选算法，在每次筛选算法中，排序码之间的比较次数都不会超过完全二叉树的高度，即log2n+1，所以整个堆排序过程的最坏时间复杂度为O(nlog2n)，也是其平均时间复杂度。空间效率：在整个堆排序过程中，需要1个与记录大小相同的辅助空间用于交换记录，故其空间复杂度为O(1)。堆排序是一种不稳定的排序方法。75 归并排序归并排序并排序（Merge Sort）是利用“归并”技术实现的排序方法。所谓归并并就是将两个或多个有序表合并成一个有序表的过程
30、如果是将两个有序表合并成一个有序表称为二路二路归并并；同理，将三个有序表合并成一个有序表称为三路归并，以此类推可以有n路归并等。本节主要讲二路归并技术实现的归并排序。二路归并方法：设数组R由两个有序子表RuRv和Rv+1Rt组成（uv,v+1t），将这两个有序子表合并之后存于数组A中，得到一个新的有序表AuAt。设i=u，j=v+1，k=u，即i，j，k分别指向三个有序表的起始下标，归并过程为：比较Ri.key和Rj.key的大小，如果Ri.keyRj.key，则将第一个有序子表的记录Ri复制到Ak中，并令i和k分别加1，指向下一个位置，否则将第二个有序子表的记录Rj复制到Ak中，并令j和k
31、分别加1，如此循环下去，直到其中一个有序子表已到表尾，然后将另一个有序子表中剩余的记录复制到数组AkAt中，至此二路归并结束。二路归并排序：首先把存储在数组R中的每个记录看成是长度为1的有序表，则n个记录构成n个有序表，接下来依次进行二路归并，归并成n/2个长度为2的有序表，当n是奇数时，还会剩余一个长度为1的有序表，通常把这个过程称为一趟归并排序。每完成一趟归并排序，都会使有序表的长度变为上一趟的2倍，但最后一个有序表的长度有可能小一些。举例：(45,53,18,36,73,45,93,15,30,48)45 53 18 36 73 45 93 15 30 48 (初始状态）45 53 18
32、 36 45 73 15 93 30 48 (1趟归并)18 36 45 53 15 45 73 93 30 48 (2趟归并)15 18 36 45 45 53 73 93 30 48 (3趟归并)15 18 30 36 45 45 48 53 73 93 (4趟归并)归并排序过程图示一趟归并排序算法需要多次调用二路归并。设数组R中每个有序表的长度为len，（最后一个表长度可能小于len）,对其进行一趟归并排序，结果存于数组A中。实际处理过程中，可能有以下三种情况：（1）数组R中有偶数个长度都是len的有序表的，这时只要连续调用二路归并merge(R，A，p，p+len-1，p+len*2-
33、1），即可完成一趟归并，这里p为有序表的起始下标；（2）数组R中前面有偶数个长度为len的有序表，两两合并完成以后，还剩余两个不等长的有序表,则对最后两个不等长的有序表还要调用一次二路归并merge(R，A，p，p+len-1，n)，即可完成一趟归并；（3）数组R中前面所有长度为len的有序表两两合并以后，只剩一个有序表，把它直接复制到数组A中即可。二路归并算法的C函数描述如下：void merge(RecType R,RecType A,int u,int v,int t)/*将两个有序表RuRv和Rv+1Rt归并到有序表AuAt*/int i,j,k;for(i=u,j=v+1,k=u；i
34、v&j=t；k+)if(Ri.key=Rj.key)Ak=Ri；i+；else Ak=Rj；j+；while(i=v)/*处理第一个有序表中剩余的记录*/Ak=Ri；i+;k+；while(j=t)/*处理第二个有序表中剩余的记录*/Ak=Rj；j+;k+；一趟归并排序算法的C函数：void mergePass(RecType R，RecType A，int n，int len)/*把数组R中每一个长度为len的有序子表归并到数组A中*/int p,i;for(p=1;p+2*len-1=n;p=p+2*len)/*归并长度为len等长有序表*/merge(R，A，p，p+len-1，p+l
35、en*2-1);if (p+len-1n)/*归并剩余的两个不等长的有序表*/merge(R，A，p，p+len-1，n);else for(i=p;i=n;i+)/*把剩余的一个有序表复制到数组A中*/Ai=Ri;归并排序的过程就是反复地调用一趟归并排序算法，其算法的C函数如下：void mergeSort(RecType R，int n)/*对数组R进行归并排序*/RecType AN+1；/*A是辅助数组*/int len,i;len=1;while(lenn)mergePass(R,A,n,len);len=2*len;mergePass(A,R,n,len);len=2*len;分析
36、归并排序的性能：时间效率：归并排序的时间复杂度应为每一趟归并排序的时间复杂度和归并趟数的乘积。对n个记录进行归并排序，归并趟数约为log2n。归并排序的时间效率主要取决于记录的移动次数。而一趟归并排序中记录的移动次数等于记录个数n，故归并排序的平均时间复杂度为O(nlog2n)。空间效率：归并排序需要一个与表等长的辅助数组空间，所以空间复杂度为O（n）。归并排序是稳定的。*76 基数排序 基数排序基数排序（Radix Sort）是与前面各类排序方法完全不同的一种排序方法，它是基于排序码的结构分解，然后通过“分配”和“收集”方法实现的排序。举例：52张扑克牌上有花色和面值（点数）。扑克牌的顺序是
37、A2JQKA2KA2KA2K。对扑克牌进行排序可以采用下面两种方法：方法1：首先按花色分成4堆，每一堆都具有相同花色，然后分别在每一堆内按面值从小到大排序，最后按花色顺序收集起来，使52张扑克牌有序；方法2：首先按不同的面值分成13堆（这个过程叫做“分配分配”），然后按照从小到大顺序将13堆收集起来（这个过程叫做“收集收集”）；接下来，再按不同的花色分成4堆，最后按花色顺序将这4堆牌收集起来，又可以得到按照次序排列的扑克牌。如何将排序码分解成多个不同位权的元素 若排序码K是个十进制整数，其值在0999范围内，则可以把每一位上的十进制数字看成一个元素，即K由3个元素（k1,k2,k3）组成，其
38、中k1的位权是102（百位数），k2的位权是101（十位数），k3的位权是100（个位数）。按照以上方法分解K，不同位权的kj都有相同的取值范围（0kj9，1j3），我们把kj取值的个数称为基数，通常用r表示。当排序码为十进制数时，基数r是10；当排序码为字符串时，基数r是26。基数排序的基本思想基本思想是：若有n个待排序记录，设第i个记录的排序码为Ki（1in），把Ki看成是一个d元组：Ki=（ki1，ki2，.，kid），其中kij c1，c2，.，cr（1jd），c1，c2，.cr 是kij 的所有可能取值，r为基数。排序时先按kid 的值进行分配，即将n个记录分到r个堆中（有时形象地称
39、为装箱），再按顺序收集；然后按kid-1的值再进行分配和收集，直至按ki1分配和收集完毕为止，这样重复做d趟分配和收集，排序结束。设待排序记录的排序码为288,371,260,531,287,235,56,299,18,23，这里 r=10,d=3，需要进行3趟分配和收集完成排序 第一趟 分配(装箱)箱号0123456789内容260371531232355628728818299第一趟收集的结果（260，371，531，23，235，56，287，288，18，299）第二趟 分配(装箱)箱号0123456789内容1823531 23556260371287288299第二趟收集的结果（1
40、8，23，531，235，56，260，371，287，288，299）第三趟 分配(装箱)箱号0123456789内容182356235260287288289371531第三趟收集的结果（260，371，531，23，235，56，287，288，18，299）基于静态链表的基数排序的存储结构#define N 10#define d 3#define r 10typedef structint key d;/*排序码由d个分量组成，这里排序码是十进制数*/DataType other;/*记录的其他数据域*/int next;/*静态链域*/RecType;RecType RN;/*数组
41、R存放n个待排序记录*/typedef struct/*定义队列*/int f,e;/*队列的队头和队尾指针*/Queue;Queue Qr;/*队列Q表示箱子*/基于静态链表的基数排序的性能分析：时间效率：基数排序的平均时间复杂度为O(n)。空间效率：在基数排序中，需要一个辅助空间数组Q，但Q的大小与n无关，所以空间复杂度为O(1)。稳定性：基数排序是稳定的。77 内排序方法的比较排序方法排序方法时间复杂度时间复杂度空间复杂度空间复杂度稳定性稳定性直接插入排序O(n2)O(1)稳定直接选择排序O(n2)O(1)不稳定起泡排序O(n2)O(1)稳定希尔排序O(n1.5)O(1)不稳定堆排序O(nlog2n)O(1)不稳定快速排序O(nlog2n)O(log2n)不稳定归并排序O(nlog2n)O(n)稳定基数排序O(n)O(1)稳定
