数据结构第八章排序.ppt

数据结构数据结构第第8章章 排排 序序数据结构数据结构第第8章章 排排 序序学习目的要求学习目的要求:1.掌握排序的概念和排序的种类掌握排序的概念和排序的种类2.熟练掌握五类基本排序熟练掌握五类基本排序:插入排序、交换排插入排序、交换排序、选择排序、归并排序和基数排序的算序、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析法思想、算法实现和性能分析数据结构数据结构8.1 排序的基本概念排序的基本概念8.2 插入排序插入排序8.3 选择排序选择排序8.4 交换排序交换排序8.5 归并排序归并排序8.6 基数排序基数排序8.7 几种排序方法的比较几种排序方法的比较第第8章章 排排 序序数据结构数据结构8.1 排序的基本概念排序的基本概念•将一组杂乱无序的数据元素将一组杂乱无序的数据元素（（记录）按一定的规记录）按一定的规律顺次排列起来叫做律顺次排列起来叫做排序排序(sort)•对对一一批批记记录录的的排排序序，，应应该该指指定定是是根根据据记记录录中中哪哪个个域域的的数数据据进进行行排排列列这这个个作作为为排排序序依依据据的的数数据据域域我我们们称之为称之为关键字关键字(key)。

•排序方法：排序方法：–大多数的排序方法，数据是存储在内存中，并大多数的排序方法，数据是存储在内存中，并在内存中加以处理的，这种排序方法叫在内存中加以处理的，这种排序方法叫内部排内部排序序–如果在排序过程中，数据的主要部分存放在外如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的进行内、外存数据交换，逐步排列记录之间的顺序，则称之为顺序，则称之为外部排序外部排序数据结构数据结构内内部部排排序序方法方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序直接插入排序直接插入排序折半插入排序折半插入排序……简单选择排序简单选择排序堆排序堆排序冒泡排序冒泡排序快速排序快速排序数据结构数据结构8.2 插入排序插入排序插入排序（插入排序（Insertion Sort）的基本思想）的基本思想:每次将一个待排序的记录，按其关键字的大小插入到前面每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上，直到全部记录插入完已经排好序的有序序列中的适当位置上，直到全部记录插入完成为止。

成为止根据具体插入方法的不同，插入排序可分为以下几种根据具体插入方法的不同，插入排序可分为以下几种:直接插入排序直接插入排序----希尔排序希尔排序折半插入排序折半插入排序---- 2ˉ路插入排序路插入排序数据结构数据结构8.2.1 直接插入排序直接插入排序直接插入排序（直接插入排序（Straight Insertion Sort）是一种最）是一种最简单的排序方法，它的基本操作是依次将记录序列中的每简单的排序方法，它的基本操作是依次将记录序列中的每一个记录插入到有序序列中，使有序序列的长度不断地扩一个记录插入到有序序列中，使有序序列的长度不断地扩大8.2 插入排序插入排序其具体的排序过程可以描述如下其具体的排序过程可以描述如下:首先将待排序记录序列中的第一个记录作为一个有序首先将待排序记录序列中的第一个记录作为一个有序序列，将待排序记录序列中的第二个记录插入到上述有序序列，将待排序记录序列中的第二个记录插入到上述有序序列中形成由两个记录组成的有序序列，再将待排序记录序列中形成由两个记录组成的有序序列，再将待排序记录序列中的第三个记录插入到这个有序序列中，形成由三个序列中的第三个记录插入到这个有序序列中，形成由三个记录组成的有序序列，如此进行下去，直到最后一个记录记录组成的有序序列，如此进行下去，直到最后一个记录也插入完成。

也插入完成数据结构数据结构简简单单插插入入排排序序例如例如: 对如下序列按照关键字由小到大排序对如下序列按照关键字由小到大排序: ( 42 20 17 13 28 14 23 15 )[ ] 20 17 13 28 14 23 15(1) 42(2) [20 42] 17 13 28 14 23 15 (3) [172042 ] 13 28 14 23 15 (4) [13 17 2042 ] 28 14 23 15 (5) [13 17 202842 ] 14 23 15 (6) [13 14 17202842] 23 15(7) [13 14 17 20 23 2842] (8) [13 14 15 1720 23 28 20]15数据结构数据结构main(){ int i,j; int r[9]={0,42,20,17,13,28,14 ,23,15 }; /*r[0]存放每次待插入的记录存放每次待插入的记录*/ for(i=2;i<=8;++i) /*第一个数是有序的第一个数是有序的,为初始有序序列为初始有序序列,i从从2开始开始*/ if(r[i]

当待排序记录较少时，排序速度较快，反之，当待排当待排序记录较少时，排序速度较快，反之，当待排序的记录数量较大时，大量的比较和移动操作将使直接插序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低入排序算法的效率降低但直接插入排序算法是一种稳定算法（如果排序后具但直接插入排序算法是一种稳定算法（如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的为稳定的，否则称为不稳定的数据结构数据结构8.2.2 折半插入排序折半插入排序折半插入排序是对直接插入排序的改进算法，它是利折半插入排序是对直接插入排序的改进算法，它是利用用折半查找折半查找来实现插入位置的定位，因为折半查找的效率来实现插入位置的定位，因为折半查找的效率比较高，因此可以减少排序过程中的比较次数适用于待比较高，因此可以减少排序过程中的比较次数适用于待排序的记录数量较大的情况排序的记录数量较大的情况8.2 插入排序插入排序一趟折半插入排序的步骤为一趟折半插入排序的步骤为: （（1）初始化）初始化 将待插入的记录存入将待插入的记录存入r［［0］中］中:r［［0］］←r［［i］］; 给指定查找区间上下界指针赋值给指定查找区间上下界指针赋值:low←1，，high ←i-1; （（2）折半查找插入位置）折半查找插入位置; （（3）将插入位置后面的记录依次后移一个位置）将插入位置后面的记录依次后移一个位置; （（4）将暂存在）将暂存在r［［0］中的待插入记录放入找到的位置］中的待插入记录放入找到的位置上。

上数据结构数据结构8.2 插入排序插入排序main(){ int i,j,low,high,m; /*low,high,m表示查找的上下界和中间位置表示查找的上下界和中间位置*/ int r[9]={0, 42,20,17,13,28,14 ,23,15 }; for(i=2;i<=8;++i) /*r[1]是有序的是有序的,从从r[2]开始排序开始排序*/ { r[0]=r[i]; /*将将r[i]暂时存到暂时存到r[0]*/ low=1; high=i-1; /*置有序序列区间的初值置有序序列区间的初值*/ while(low<=high) /*在在r[low]到到r[high]中折半查找插入位置中折半查找插入位置*/ { m=(low+high)/2; /*折半折半,取中间位置送取中间位置送m*/ if(r[0]=high+1;--j) r[j+1]=r[j]; /*插入位置以后的记录后移插入位置以后的记录后移*/ r[high+1]=r[0]; /*插入记录插入记录*/ } for(i=1;i<=8;i++) printf("%d ",r[i]); /*输出排序后的有序序列输出排序后的有序序列*/}折半插入排序仅仅减少了关键字间的比较次数，而记折半插入排序仅仅减少了关键字间的比较次数，而记录的移动次数不变。

因此折半插入排序的时间复杂度仍为录的移动次数不变因此折半插入排序的时间复杂度仍为O（（n2）它也是一种稳定的算法）它也是一种稳定的算法数据结构数据结构8.3 选择排序选择排序选择排序（选择排序（Selection Sort）的基本思想是）的基本思想是:每一趟从待排序的序列中选出每一趟从待排序的序列中选出关键字最小关键字最小的记录，顺序的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕放在已排好序的子序列的最后，直到全部记录排序完毕常用的选择排序方法有简单选择排序和堆排序常用的选择排序方法有简单选择排序和堆排序数据结构数据结构简单选择排序的基本思想是简单选择排序的基本思想是:首先从首先从1~n个元素中选出关键字个元素中选出关键字最小最小的记录交换的记录交换到到第一个第一个位置上（第位置上（第1趟）然后再从第趟）然后再从第2 个到第个到第n个个元素中选出次小的记录交换到元素中选出次小的记录交换到第二个第二个位置上（第位置上（第2趟）趟），依次类推，经过，依次类推，经过n-1趟排序后即可得到有序序列趟排序后即可得到有序序列8.3.1 简单选择排序简单选择排序8.3 选择排序选择排序数据结构数据结构例如，一组待排序的记录的关键字如下，要求按照关键例如，一组待排序的记录的关键字如下，要求按照关键字由小到大进行排序。

字由小到大进行排序 8.3 选择排序选择排序第第i趟排序：从数组下标为趟排序：从数组下标为i~n的元素中找一个最小的，放到的元素中找一个最小的，放到下标为下标为i的数组元素中的数组元素中数据结构数据结构8.3 选择排序选择排序#define LENGTH 8main() { int r[LENGTH+1]={0,45,38,63,85,71,28,45,16}; /*定义数组并赋初值定义数组并赋初值,r[0]作暂存单元作暂存单元*/ int i,j,k; for(i=1;ir[j]) k=j; /*保存当前关键字最小的记录位置保存当前关键字最小的记录位置*/ if(i!=k) /*交换交换r[i]与与r[k]*/ { r[0]=r[i]; r[i]=r[k]; r[k]=r[0]; } } for(i=1;i<=LENGTH;i++) /*输出排序后的序列输出排序后的序列*/ printf("%d ",r[i]);}变变量量i: 存存放放第第i 趟趟的的起起始始数数据据的的下标（第一个数据下标）。

下标（第一个数据下标）变变量量k: 存存放放第第i 趟趟的的待待比比较较的的数数据据中中的的最最小小值值下下标标（（初初值值：：本本趟趟比比较较中中的的第第一一个个数数据据下下标标；；终终值值：：本本趟趟比比较较中中的的最最小小数数据据下标；下标； ）变变量量j: 存存放放第第i 趟趟的的待待比比较较的的数数据据下下标标值值（（初初值值：：本本趟趟比比较较中中的的第第二二个个数数据据下下标标；；终终值值：：本本趟趟比比较较中中的的最最后后一一个个数数据据下下标标；； ）数据结构数据结构简单选择排序算法简单，但是速度较慢，时间复杂度为简单选择排序算法简单，但是速度较慢，时间复杂度为O（（n2），并且是一种不稳定的排序方法并且是一种不稳定的排序方法8.3 选择排序选择排序数据结构数据结构8.3.2 堆排序堆排序堆排序（堆排序（Heap Sort）是利用堆的特性进行排序的过程是利用堆的特性进行排序的过程堆堆: 是是满满足足特特定定条条件件的的顺顺序序存存储储的的完完全全二二叉叉树树，，其其特特定定条条件件是是：：任任何何一一个个非非叶叶子子结结点点的的值值大大于于等等于于（（或或小小于于等等于于））左右孩子结点的值。

左右孩子结点的值8.3 选择排序选择排序数据结构数据结构8.3.2 堆排序堆排序对于这些完全二叉树，如果我们按层次对其结点编号，对于这些完全二叉树，如果我们按层次对其结点编号，然后用一维数组来存放各个结点然后用一维数组来存放各个结点实际上数组中的数据就构成了一个待排序序列这个序实际上数组中的数据就构成了一个待排序序列这个序列满足如下条件：列满足如下条件： Ki≤K2i ,并且并且 Ki≤K2i+1或或 Ki≥K2i ,并且并且 Ki≥K2i+1（（i=1，，2，，…，，n/2 ））一般来说如果对于一般来说如果对于 n个元素构成的序列：｛个元素构成的序列：｛K1，，K2，，…，，Kn｝来说，若它们之间满足上述条件｝来说，若它们之间满足上述条件 ，， 那么该序列被称为那么该序列被称为一个一个“堆堆”{ 96 ,83,27,38,11,9} {12,36,24,85,47,30,53,91}8.3 选择排序选择排序在一个堆里，在一个堆里，k1（完全二叉树的根结点）是堆中最小（完全二叉树的根结点）是堆中最小（大）的数据结构数据结构8.3 选择排序选择排序堆排序的基本思想是堆排序的基本思想是:对一组待排序的记录，首先把它们按堆的定义排成一对一组待排序的记录，首先把它们按堆的定义排成一个堆，将堆顶元素取出个堆，将堆顶元素取出;然后把剩下的记录再排成堆，取出然后把剩下的记录再排成堆，取出堆顶元素堆顶元素;依次下去，直到取出全部元素，从而将全部记录依次下去，直到取出全部元素，从而将全部记录排成一个有序序列。

排成一个有序序列实现堆排序需要解决两个问题实现堆排序需要解决两个问题:（（1）如何将一个无序序列建成一个堆）如何将一个无序序列建成一个堆?（（2）如何在输出堆顶元素之后，调整剩余元素成为一个）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆新的堆? 假定有一个待排序序列假定有一个待排序序列{ 25 56 49 78 11 65 41 36}数据结构数据结构（（1）如何将一个无序序列建成一个堆）如何将一个无序序列建成一个堆?首先把该序列存储到一个一维数组中，然后按照其下标首先把该序列存储到一个一维数组中，然后按照其下标编号得到相应的完全二叉树如图：编号得到相应的完全二叉树如图：8.3 选择排序选择排序假定有一个序列假定有一个序列{ 25 56 49 78 11 65 41 36}2556497811654136(a)无序序列无序序列n=8, int(n/2)=4开始开始然后然后由下而上逐层由下而上逐层进行父子结点进行父子结点的关键字比较并交换，直到使其的关键字比较并交换，直到使其最后满足堆的条件最后满足堆的条件ki<=k2i且且ki<=k2i +1））建堆时是从建堆时是从最后一个非终端结点最后一个非终端结点 n/2 开始的。

开始的数据结构数据结构（1）由无序序列建初始堆的过程由无序序列建初始堆的过程2556497811654136(a)无序序列无序序列n=8, int(n/2)=4开始开始2556493611654178(b): 78被筛选后的状态被筛选后的状态2556413611654978(c): 49被筛选后的状态被筛选后的状态2511413656654978(d): 56被筛选后的状态被筛选后的状态(e): 被筛选之后建成堆被筛选之后建成堆1125413656654978下一步就可以输出堆顶元素，然后将剩余元素进一步调整成新堆下一步就可以输出堆顶元素，然后将剩余元素进一步调整成新堆 数据结构数据结构 (2) 输出堆顶元素并调整建新堆的过程输出堆顶元素并调整建新堆的过程(筛选筛选)6525365649784111(b)65365649784111(c)251125365649784165(a)25493656657841(d)11将堆顶元素与最后一个元素将堆顶元素与最后一个元素交换，然后对前交换，然后对前n-1个元素个元素进一步调整成新堆进一步调整成新堆 数据结构数据结构堆排序适用于堆排序适用于n值较大的序列。

整个堆排序的时间复杂值较大的序列整个堆排序的时间复杂度为度为O（（nlog2n），对于存在相同关键字的记录的情况，），对于存在相同关键字的记录的情况，堆排序是不稳定的堆排序是不稳定的8.3 选择排序选择排序数据结构数据结构8.4 交换排序交换排序交换排序的特点在于交换排序的特点在于交换基本思想是基本思想是:两两两两比较待排序记录的关键字，若发现两个记录的次序比较待排序记录的关键字，若发现两个记录的次序为逆序时，交换其存储位置，直到没有逆序的记录为止常为逆序时，交换其存储位置，直到没有逆序的记录为止常用的交换排序方法有用的交换排序方法有:冒泡排序和快速排序冒泡排序和快速排序8.4.1 冒泡排序冒泡排序冒泡排序是一种简单的排序方法它的基本思想是（冒泡排序是一种简单的排序方法它的基本思想是（小小的浮起，大的沉底）的浮起，大的沉底）对所有相邻记录的关键字值进行比较，对所有相邻记录的关键字值进行比较，如果是逆序（如果是逆序（r［［i］］>r［［i+1］），则交换其位置，经过多趟］），则交换其位置，经过多趟排序，最终使整个序列有序排序，最终使整个序列有序数据结构数据结构8.4 交换排序交换排序其处理过程为其处理过程为:第一趟排序，从第一条记录第一趟排序，从第一条记录r［［1］开始，直到最后一条记］开始，直到最后一条记录录r［［n］，］， 对两两相邻的记录依此比较，若发现为逆序，则立对两两相邻的记录依此比较，若发现为逆序，则立即交换其位置，最后使这即交换其位置，最后使这n条记录中关键字最大的记录条记录中关键字最大的记录“下沉下沉”到到最底部，既被交换到第最底部，既被交换到第n个位置上，它不参与下一趟排序个位置上，它不参与下一趟排序; 第二趟排序，从第一条记录第二趟排序，从第一条记录r［［1］开始，直到第］开始，直到第n-1条记条记录录r［［n-1］，］， 对两两相邻的记录依此比较，若发现为逆序，则对两两相邻的记录依此比较，若发现为逆序，则立即交换其位置，最后使这立即交换其位置，最后使这n-1条记录中关键字最大的记录条记录中关键字最大的记录“下下沉沉”到次底部，既被交换到第到次底部，既被交换到第n-1个位置上，它不参与下一趟排个位置上，它不参与下一趟排序序;如此反复，最多经过（如此反复，最多经过（n-1）趟冒泡排序，就可以使整个序）趟冒泡排序，就可以使整个序列成为有序序列。

列成为有序序列数据结构数据结构第第六六趟趟排排序序后后第第五五趟趟排排序序后后第第四四趟趟排排序序后后第第三三趟趟排排序序后后第第二二趟趟排排序序后后第第一一趟趟排排序序后后初初始始关关键键字字4936416511783665364156364165413641561178363641491156492525251149495611111125252525如此反复，最多如此反复，最多经过（经过（n-1）趟冒）趟冒泡排序，就可以泡排序，就可以使整个序列成为使整个序列成为有序序列有序序列数据结构数据结构8.4 交换排序交换排序冒泡排序的时间复杂度为冒泡排序的时间复杂度为O（（n2），由于它的记录移动），由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多次数较多，故平均时间性能比直接插入排序要差得多冒泡排序是一种稳定的排序方法冒泡排序是一种稳定的排序方法数据结构数据结构8.4.2 快速排序快速排序快速排序（快速排序（Quick Sort）是对冒泡排序的一种改进它）是对冒泡排序的一种改进它的基本思想是的基本思想是:通过一趟排序将待排序记录划分成两部分，使得其中一通过一趟排序将待排序记录划分成两部分，使得其中一部分记录的关键字比另一部分记录的关键字小部分记录的关键字比另一部分记录的关键字小;然后再分别对这两部分记录进行这种排序，直到每个部然后再分别对这两部分记录进行这种排序，直到每个部分为空或只包含一个记录时，整个快速排序结束。

分为空或只包含一个记录时，整个快速排序结束例题：例题： （（ 23 52 6 67 18 ））做做法法：：附附设设两两个个指指针针low和和high ，，初初值值分分别别指指向向第第一一个个记记录录和和最最后后一一个个记记录录，，（（取取第第一一个个记记录录的的值值23为为基基准准值值首首先先从从 high所所指指位位置置起起向向前前搜搜索索，，找找到到第第一一个个小小于于基基准准值值的的记记录录与与基基准准记记录录交交换换，，然然后后从从low 所所指指位位置置起起向向后后搜搜索索，，找找到到第第一一个个大大于于基基准准值值的的记记录录与与基基准准记记录交换，重复这两步直至录交换，重复这两步直至low=high为止8.4 交换排序交换排序数据结构数据结构快速排序过程示意图：快速排序过程示意图：有序序列有序序列 6 18 23 52 67key初始序列初始序列 23 52 6 67 18lowhigh一次交换一次交换 18 52 6 67 23 lowhigh二次交换二次交换 18 23 6 67 52high 三次交换三次交换 [18 6] 23 [67 52]// 完成一趟排序后分别进行快速排序完成一趟排序后分别进行快速排序lowhigh数据结构数据结构8.4 交换排序交换排序快速排序的时间复杂度平均为快速排序的时间复杂度平均为 O（（nlog2n），当），当n较较大时，大时， 这种算法是平均速度最快的排序算法，因此称为快这种算法是平均速度最快的排序算法，因此称为快速排序。

快速排序是一种不稳定的排序方法快速排序是一种不稳定的排序方法数据结构数据结构8.5 归并排序归并排序归并排序（归并排序（Merging Sort）是又一类不同的排序方法是又一类不同的排序方法归并归并”的含义是将两个或两个以上的有序序列合成一个新的的含义是将两个或两个以上的有序序列合成一个新的有序序列有序序列假设初始序列含有假设初始序列含有 n个记录，则可看成是个记录，则可看成是n个有序的子个有序的子序列，每个子序列的长度为序列，每个子序列的长度为1，然后两两归并，得到，然后两两归并，得到 n/2 个长度为个长度为2（最后一个序列长度可能小于（最后一个序列长度可能小于2）的有序子序列）的有序子序列;再两两归并，得到再两两归并，得到 n/2 /2 个长度为个长度为4（最后一个序列长度（最后一个序列长度可能小于可能小于4）的有序序列）的有序序列;如此重复，直至得到一个长度为如此重复，直至得到一个长度为n的有序序列为止，每一次合并过程称为一趟归并排序，这的有序序列为止，每一次合并过程称为一趟归并排序，这种排序方法称为种排序方法称为 2-路归并排序路归并排序数据结构数据结构例如，设待排序的记录序列为例如，设待排序的记录序列为: 42 36 56 78 67 11 27 36 2-路归并排序中的核心操作是将一维数组中前后相路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。

邻的两个有序序列归并为一个有序序列8.5 归并排序归并排序数据结构数据结构2-路归并排序算法的时间复杂度为路归并排序算法的时间复杂度为 O（（nlog2n） 2-路归并排序算法是稳定的路归并排序算法是稳定的8.5 归并排序归并排序数据结构数据结构8.6 基数排序基数排序基数排序（基数排序（Radix Sorting）是和前面所述各）是和前面所述各类排序方法完全不同的一种排序方法前面讨论的类排序方法完全不同的一种排序方法前面讨论的排序主要是通过关键字间的比较和移动记录这两种排序主要是通过关键字间的比较和移动记录这两种操作实现的，而基数排序没有进行这两种操作，它操作实现的，而基数排序没有进行这两种操作，它是借助多关键字排序的思想实现的是借助多关键字排序的思想实现的,其基本操作是按其基本操作是按关键字位关键字位进行进行“分散分散”和和“收集收集”基数排序的基本思想：基数排序的基本思想： 设一组待排序数据的个数为设一组待排序数据的个数为n，，每个数据的每个数据的位数为位数为d，，每位数可能有每位数可能有rd种取值，则这种排序方种取值，则这种排序方法需进行法需进行d趟趟“分散分散”和和“收集收集”，，每趟检查每趟检查n个数的个数的某某一位数一位数，并按此位数值的不同，将其分别放到，并按此位数值的不同，将其分别放到rd个个卡片盒中卡片盒中(分散分散),然后按照然后按照rd个卡片盒的顺序进行收个卡片盒的顺序进行收集集.每位数可能取值的数目每位数可能取值的数目rd称为基数称为基数(Radix)，例如对于，例如对于十进制数的每一位可能有十进制数的每一位可能有0到到9十种取值，故基数为十种取值，故基数为10；而二进制的每一位数只能有；而二进制的每一位数只能有0和和1两种取值，则基数两种取值，则基数为为2。

数据结构数据结构基数排序基数排序(a)(a) 原始数据原始数据原始数据中原始数据中:n=9,d=3,rd=10:n=9,d=3,rd=10数据结构数据结构算法的实现算法的实现: :为每个为每个“盒盒”设置一个链接队列，并将各队列设置一个链接队列，并将各队列的队首和队尾指针分别存于两个一维数组中的队首和队尾指针分别存于两个一维数组中开始时，将原始数据构成一个链接队列，设开始时，将原始数据构成一个链接队列，设各各“盒盒”的队列均为空队列然后将原始数据的队列均为空队列然后将原始数据队列中各结点，按所考虑的关键字某位数的队列中各结点，按所考虑的关键字某位数的值插入到相应值插入到相应“盒盒”的队列中去的队列中去当一趟结束时，再把各当一趟结束时，再把各“盒盒”的队列依次首尾的队列依次首尾相连，链接成一个链接队列，以此作为下一相连，链接成一个链接队列，以此作为下一趟的输入趟的输入如此反复进行，直至做完如此反复进行，直至做完d趟，即排序结束趟，即排序结束数据结构数据结构基数排序的时间复杂度为基数排序的时间复杂度为O（（d（（n+rd））由于））由于d、、rd是常数，当是常数，当n较大时，基数排序的时间复杂度近似为较大时，基数排序的时间复杂度近似为O（（n）。

但）但n较小，较小，d较大时，采用基数排序并不合较大时，采用基数排序并不合 适适;只有当只有当n较大、较大、d较小时，基数排序才最为有效较小时，基数排序才最为有效这种排序方法的缺点是占用的存储空间较多，每个待这种排序方法的缺点是占用的存储空间较多，每个待排序的记录都需要加上指针域排序的记录都需要加上指针域基数排序是稳定的排序算法基数排序是稳定的排序算法8.6 基数排序基数排序数据结构数据结构排序是将一组数据按照一定的规律顺序排列起来排序方排序是将一组数据按照一定的规律顺序排列起来排序方法有内部排序和外部排序，内部排序指待排序记录在内存中进法有内部排序和外部排序，内部排序指待排序记录在内存中进行的排序过程外部排序指在排序过程中还需对外存进行访问行的排序过程外部排序指在排序过程中还需对外存进行访问的排序过程的排序过程内部排序的排序方法有内部排序的排序方法有:插入排序、交换排序、选择排序、插入排序、交换排序、选择排序、归并排序和基数排序每种排序方法的排序过程及其排序思想归并排序和基数排序每种排序方法的排序过程及其排序思想各不相同，根据不同的场合选择不同的排序方法各不相同，根据不同的场合选择不同的排序方法。

排序的稳定性方面排序的稳定性方面:直接插入排序、冒泡排序、归并排序直接插入排序、冒泡排序、归并排序和基数排序是稳定的，希尔排序、简单选择排序、快速排序和和基数排序是稳定的，希尔排序、简单选择排序、快速排序和堆排序是不稳定的堆排序是不稳定的本章小结本章小结数据结构数据结构4. 排序方法的时间复杂度分别为排序方法的时间复杂度分别为:直接插入排序、简单选直接插入排序、简单选择排序和冒泡排序这三种排序方法的时间复杂度均为择排序和冒泡排序这三种排序方法的时间复杂度均为O（（n2），），堆排序和归并排序这两种排序方法的时间复杂度为堆排序和归并排序这两种排序方法的时间复杂度为O（（nlog2n），快速排序方法的平均时间复杂度也为），快速排序方法的平均时间复杂度也为O（（n log2n），但快速排序在最坏情况下的时间复杂度为），但快速排序在最坏情况下的时间复杂度为O（（n2）希尔排序方法的时间复杂度介于希尔排序方法的时间复杂度介于O（（n log2n）与）与O（（n2）之）之间，基数排序方法的时间复杂度为间，基数排序方法的时间复杂度为O（（d（（n+r））排序方法））排序方法的空间复杂度分别为的空间复杂度分别为:归并排序的空间复杂度最差，为归并排序的空间复杂度最差，为O（（n））;快速排序的空间复杂度为快速排序的空间复杂度为O（（ log2n））;基数排序的空间复杂度基数排序的空间复杂度为为O（（2r））;其他排序方法的空间复杂度均为其他排序方法的空间复杂度均为O（（1）。

本章小结本章小结数据结构数据结构考试题型：考试题型：一、选择题（一、选择题（20分）分）二、填空题（二、填空题（10分）分）三、问答题（三、问答题（50分）分）四、算法设计题（四、算法设计题（20分）分） 数据结构数据结构部分资料从网络收集整理而来，供大家参考，感谢您的关注！。