数据结构项目八课件.ppt

1、数据结构数据结构项目八共分为五个任务项目八共分为五个任务项目八项目八 排序排序任务一任务一 排序的相关概念排序的相关概念 任务二任务二 插入排序插入排序 任务三任务三 交换排序交换排序 任务四任务四 选择排序选择排序 任务五任务五 归并排序和基数排序归并排序和基数排序 任务一任务一 排序的相关概念排序的相关概念 1排序排序 2数据元素的存储结构数据元素的存储结构3算法的稳定性算法的稳定性 4算法的评价算法的评价 1排序排序 排序排序是指将一个数据元素的任意序列按关键字的递增或递减次序重新是指将一个数据元素的任意序列按关键字的递增或递减次序重新排列起来，使其成为一个按关键字有序排列的序列。排列起

2、来，使其成为一个按关键字有序排列的序列。内部排序内部排序是指将待排数据元素完全放置在内存中进行排序的方法。是指将待排数据元素完全放置在内存中进行排序的方法。外部排序外部排序是指因待排数据元素数量太大，排序过程中不仅需要使用内是指因待排数据元素数量太大，排序过程中不仅需要使用内存，还要借助外部存储器来完成的排序方法。存，还要借助外部存储器来完成的排序方法。2数据元素的存储结构数据元素的存储结构数据元素可有数据元素可有3种存储结构：种存储结构：顺序结构顺序结构、链式结构链式结构和和地址向量结构地址向量结构。排序过程中一定要排序过程中一定要移动数据元素移动数据元素排序过程中不用移动数据元排序过程中不

3、用移动数据元素，而只需要修改指针素，而只需要修改指针 指将数据元素顺序存储的同时，另设一个指示各个数据元素指将数据元素顺序存储的同时，另设一个指示各个数据元素位置的地址向量，这样在排序过程中不用移动数据元素，而位置的地址向量，这样在排序过程中不用移动数据元素，而只需修改地址向量中数据元素的只需修改地址向量中数据元素的“地址地址”即可即可 顺序结构的数据类型定义如下：顺序结构的数据类型定义如下：#define MAXSIZE 100/顺序表的最大长度顺序表的最大长度typedef struct KeyType key;/关键字项关键字项OtherType otheritem;/另外的数据项另外的

4、数据项RecordType;typedef structRecordType rMAXSIZE+1;/定义数据元素数组，定义数据元素数组，r0为哨兵单元为哨兵单元int length;/顺序表长度顺序表长度SeqList;3算法的稳定性算法的稳定性 如果待排序的数据元素序列中有两个数据元素的关键字的值相同，经如果待排序的数据元素序列中有两个数据元素的关键字的值相同，经过排序后，两个数据元素的过排序后，两个数据元素的相对次序保持不变相对次序保持不变，则称所用的排序方法，则称所用的排序方法是是稳定稳定的；反之，则称所用的排序方法是的；反之，则称所用的排序方法是不稳定不稳定的。的。关键字序列（关键字

5、序列（35，2，15，6，81，6*）结果序列为（结果序列为（2，6，6*，15，35，81）表示为）表示为稳定稳定的排序方法的排序方法 结果序列为（结果序列为（2，6*，6，15，35，81）表示为）表示为不稳定不稳定的排序方法的排序方法 4算法的评价算法的评价 可以从两个方面来评价某种排序算法的优劣：可以从两个方面来评价某种排序算法的优劣：通过排序过程中所需的内存辅助空间的多少来衡量。通过排序过程中所需的内存辅助空间的多少来衡量。通过排序过程中关键字的比较次数和数据元素的移动次数来反映。通过排序过程中关键字的比较次数和数据元素的移动次数来反映。空间复杂度空间复杂度：时间复杂度时间复杂度：任

6、务二任务二 插入排序插入排序 一、直接插入排序一、直接插入排序 二、折半插入排序二、折半插入排序 三、希尔排序三、希尔排序 1基本思想基本思想 2算法实现算法实现 一、直接插入排序一、直接插入排序 3算法分析算法分析 1基本思想基本思想 将待排数据元素插入到已排好序的有序表中，从而得到一个新的有序表。将待排数据元素插入到已排好序的有序表中，从而得到一个新的有序表。对于一个具有对于一个具有n个数据元素的序列，进行直接插入排序具体过程：个数据元素的序列，进行直接插入排序具体过程：将第将第1个数据元素看作一个已排好序的有序表。个数据元素看作一个已排好序的有序表。将第将第i（2in）个数据元素的关键字

7、）个数据元素的关键字Ki依次与其前面数据元素的关依次与其前面数据元素的关键字键字Ki1、Ki2、K1进行比较，将所有关键字大于进行比较，将所有关键字大于Ki的数据元素依的数据元素依次向后移动一个位置，直到某个数据元素的关键字次向后移动一个位置，直到某个数据元素的关键字Kj小于或者等于小于或者等于Ki时，时，将第将第i个数据元素插入到关键字为个数据元素插入到关键字为Kj的数据元素后面，即完成第的数据元素后面，即完成第i个数据个数据元素的插入。元素的插入。经过经过n1次插入操作后，所有数据元素构成一个按关键字值大小排次插入操作后，所有数据元素构成一个按关键字值大小排列的有序序列。列的有序序列。数据

8、元素序列数据元素序列35，66，2，15，6，81，6*，9进行直接插入排序的过程：进行直接插入排序的过程：2算法实现算法实现 void InsertSort(SeqList*L)/对顺序表对顺序表L作直接插入排序作直接插入排序int i,j;for(i=2;i Length;i+)/从第二个数据元素开始排序从第二个数据元素开始排序if(L-ri.key ri-1.key)/如果第如果第i个数据元素的关键字小于其前面数据元素的关键字，则将其个数据元素的关键字小于其前面数据元素的关键字，则将其插入到有序表中插入到有序表中L-r0=L-ri;/将待插入数据元素存入将待插入数据元素存入r0作为监视哨

9、作为监视哨/搜索插入位置，将有序表中大于待排关键字的数据元素后移搜索插入位置，将有序表中大于待排关键字的数据元素后移for(j=i-1;L-r0.key rj.key;j-)L-rj+1=L-rj;L-rj+1=L-r0;/将待排数据元素插入到第将待排数据元素插入到第j个数据元素之后个数据元素之后3算法分析算法分析（1）空间复杂度）空间复杂度 排序过程中仅使用了一个辅助单元排序过程中仅使用了一个辅助单元r0，算法的空间复杂度为，算法的空间复杂度为O(1)。（2）时间复杂度）时间复杂度 直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)。（3）稳定性）稳定性 直接插入排序是一种直接插

10、入排序是一种稳定稳定的排序算法。的排序算法。二、折半插入排序二、折半插入排序 1算法实现算法实现 2算法分析算法分析 1算法实现算法实现 通过对有序表进行折半查找来确定插入位置，以减少关键字比较的次通过对有序表进行折半查找来确定插入位置，以减少关键字比较的次数。算法描述如下：数。算法描述如下：void BinSort(SeqList*L)/对顺序表对顺序表L作折半插入排序作折半插入排序int i,j;int low,high,mid;for(i=2;i length;i+)/从第从第2个元素开始排序个元素开始排序L-r0=L-ri;/将待插入数据元素存入将待插入数据元素存入r0作为监视哨作为监

11、视哨low=1;high=i-1;/设置初始查找区间设置初始查找区间while(low r0.key rmid.key)high=mid 1;/在前半部分查找在前半部分查找else low=mid+1;/在后半部分查找在后半部分查找for(j=i-1;j=low;j-)/将插入位置以后的数据元素后移将插入位置以后的数据元素后移L-rj+1=L-rj;L-rlow=L-r0;/插入数据元素插入数据元素 2算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 排序过程中仅使用了一个辅助单元排序过程中仅使用了一个辅助单元r0，算法的空间复杂度为，算法的空间复杂

12、度为O(1)。折半插入排序的时间复杂度为折半插入排序的时间复杂度为O(n2)。折半插入排序是一种折半插入排序是一种稳定稳定的排序算法。的排序算法。三、希尔排序三、希尔排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 将待排序数据元素划分成若干个子序列，其中每个子序列由相隔某个将待排序数据元素划分成若干个子序列，其中每个子序列由相隔某个“增量增量”的数据元素组成，然后对这些子序列分别进行直接插入排序，的数据元素组成，然后对这些子序列分别进行直接插入排序，通过缩小通过缩小“增量增量”对子序列进行调整。当整个序列基本有序时，对全对子序列进行调整。当整个序列基本有序

13、时，对全部数据元素进行一次直接插入排序。部数据元素进行一次直接插入排序。具体过程：具体过程：按选定增量按选定增量d1（d1n），将所有距离为），将所有距离为d1的数据元素划分为一个的数据元素划分为一个子序列，对各个子序列进行直接插入排序。子序列，对各个子序列进行直接插入排序。选定增量选定增量d2（d2d1），对所有数据元素重新进行划分并对各子序），对所有数据元素重新进行划分并对各子序列直接插入排序。列直接插入排序。重复以上操作，直到增量重复以上操作，直到增量di1，即将所有数据元素放在一个子序列中，即将所有数据元素放在一个子序列中进行一次直接插入排序，最后得到所有数据元素按关键字有序排列的序进

14、行一次直接插入排序，最后得到所有数据元素按关键字有序排列的序列。列。2算法实现算法实现 void ShellInsert(SeqList*L,int di)/对顺序表对顺序表L作一趟希尔排序，作一趟希尔排序，di为增量为增量int i,j;for(i=di+1;i Length;i+)if(L-ri.key ri-di.key)/将第将第i个数据元素插入有序子序列个数据元素插入有序子序列L-r0=L-ri;/将第将第i个数据元素存入个数据元素存入r0作为监视哨作为监视哨/查找插入位置，将子序列内插入位置后的数据元素后移查找插入位置，将子序列内插入位置后的数据元素后移for(j=i-di;j 0

15、&L-r0.key rj.key;j=j-di)L-rj+di=L-rj;L-rj+di=L-r0;/插入数据元素插入数据元素void ShellSort(SeqList*L,int d,int t)/按增量序列按增量序列d对顺序表对顺序表L作作t趟希尔排序趟希尔排序int k;for(k=0;k t;k+)ShellInsert(L,dk);/一趟增量为一趟增量为dk的希尔排序的希尔排序3算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 排序过程中仅使用了一个辅助单元，算法的空间复杂度为排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。希

16、尔排序是一种希尔排序是一种不稳定不稳定的排序算法。的排序算法。在在数据量较少数据量较少时，利用时，利用直接插入排序的效率较高直接插入排序的效率较高；当待排序的数据元；当待排序的数据元素素数目较大数目较大时，时，希尔排序方法希尔排序方法一般要比直接插入排序方法一般要比直接插入排序方法快快。任务三任务三 交换排序交换排序 一、冒泡排序一、冒泡排序 二、交换排序二、交换排序一、冒泡排序一、冒泡排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 从头扫描待排序的数据元素序列，依次比较相邻两个数据元素的关键字从头扫描待排序的数据元素序列，依次比较相邻两个数据元素的关键字

17、大小，如果逆序，则交换它们的位置，逐步将待排序列变成有序序列。大小，如果逆序，则交换它们的位置，逐步将待排序列变成有序序列。具体过程：具体过程：对待排序数据元素序列进行第一趟扫描，依次比较相邻两个数据元对待排序数据元素序列进行第一趟扫描，依次比较相邻两个数据元素的关键字大小，如果前面数据元素的关键字大于后面数据元素的关素的关键字大小，如果前面数据元素的关键字大于后面数据元素的关键字，就将它们交换，这样具有较大关键字的数据元素将不断后移，键字，就将它们交换，这样具有较大关键字的数据元素将不断后移，最后，具有最大关键字的数据元素移动到最后一个位置上；最后，具有最大关键字的数据元素移动到最后一个位置

18、上；第二趟扫描仅需对前第二趟扫描仅需对前n1个数据元素进行，重复以上操作，使具有个数据元素进行，重复以上操作，使具有次大关键字的数据元素移动到第次大关键字的数据元素移动到第n1个位置；个位置；依此类推，直到某一趟扫描过程中没有发生数据元素的交换，则可依此类推，直到某一趟扫描过程中没有发生数据元素的交换，则可结束冒泡排序。结束冒泡排序。对数据元素序列（对数据元素序列（35，66，2，15，6，81，6*，9）进行冒泡排序：）进行冒泡排序：2算法实现算法实现 void BubbleSort(SeqList*L)/对顺序表对顺序表L作冒泡排序作冒泡排序int i,j,change;change=TR

19、UE;/设置交换标志，初始值为设置交换标志，初始值为TRUEfor(i=1;i Length&change;i+)/进行冒泡排序，无交换时结束进行冒泡排序，无交换时结束change=FALSE;/设置交换标志为设置交换标志为FALSEfor(j=1;j Length-i;j+)/对未排好序的数据元素排序对未排好序的数据元素排序if(L-rj.key L-rj+1.key)/比较相邻两个数据元素的大小比较相邻两个数据元素的大小L-r0=L-rj;/要交换的数据元素暂时存入要交换的数据元素暂时存入r0中中L-rj=L-rj+1;L-rj+1=L-r0;change=TRUE;/设置交换标志为设置交

20、换标志为TRUE3算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 冒泡排序过程中仅使用了一个辅助单元，算法的空间复杂度为冒泡排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。冒泡排序的时间复杂度为冒泡排序的时间复杂度为O(n2)。冒泡排序是一种冒泡排序是一种稳定稳定的排序算法。的排序算法。二、快速排序二、快速排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 从待排数据元素序列中选取一个数据元素为基准，通过一趟扫描将待排序从待排数据元素序列中选取一个数据元素为基准，通过一趟扫描将待排序列分成两部分。其中一

21、部分数据元素的关键字都小于或等于基准数据元素列分成两部分。其中一部分数据元素的关键字都小于或等于基准数据元素的关键字，而另一部分数据元素的关键字都大于或等于基准数据元素的关的关键字，而另一部分数据元素的关键字都大于或等于基准数据元素的关键字。对各部分不断划分，直到整个序列按关键字有序排列为止。键字。对各部分不断划分，直到整个序列按关键字有序排列为止。具体过程如下：具体过程如下：选取待排序列中的第一个数据元素为基准，将其复制到选取待排序列中的第一个数据元素为基准，将其复制到r0中，并令该位置为中，并令该位置为空；设置两个指针空；设置两个指针low和和high，分别指向第一个数据元素和最后一个数据

22、元素，即，分别指向第一个数据元素和最后一个数据元素，即初始状态时初始状态时rlow为空。为空。从后向前扫描，若从后向前扫描，若rhigh的关键字大于或等于基准关键字，则的关键字大于或等于基准关键字，则high向前移动向前移动一个位置，直到一个位置，直到rhigh的关键字小于基准关键字时，将的关键字小于基准关键字时，将rhigh与与rlow交换。交换。从前向后扫描，若从前向后扫描，若rlow的关键字小于或等于基准关键字，则的关键字小于或等于基准关键字，则low向后移动一个向后移动一个位置，直到位置，直到rlow的关键字大于基准关键字时，将的关键字大于基准关键字时，将rlow与与rhigh交换。交

23、换。重复步骤重复步骤和和，直至，直至lowhigh时，令时，令rlowr0，以，以rlow为基准将待为基准将待排序列划分为前后两部分，第一次划分完成。排序列划分为前后两部分，第一次划分完成。按照以上方法，对各部分不断划分，直到各部分只有一个数据元素时，整个序按照以上方法，对各部分不断划分，直到各部分只有一个数据元素时，整个序列排序完成。列排序完成。对数据元素序列（对数据元素序列（35，66，2，15，6，81，6*，9）进行一趟快速排序）进行一趟快速排序的过程的过程：2算法实现算法实现 int Partition(SeqList*L,int low,int high)/以第一个数据元素为基准进

24、行一趟快排，返回排序后基准数据元素的位置以第一个数据元素为基准进行一趟快排，返回排序后基准数据元素的位置L-r0=L-rlow;/以序列中第一个数据元素为基准以序列中第一个数据元素为基准while(low high)/从序列两端交替向中间扫描从序列两端交替向中间扫描while(low rhigh.key=L-r0.key)/从后向前扫描从后向前扫描high-;/high指针前移指针前移L-rlow=L-rhigh;/将小于基准关键字的数据元素移到将小于基准关键字的数据元素移到low所指位置所指位置while(low rlow.key r0.key)/从前向后扫描从前向后扫描low+;/low指

25、针后移指针后移L-rhigh=L-rlow;/将大于基准关键字的数据元素移到将大于基准关键字的数据元素移到high所指位置所指位置L-rlow=L-r0;/将基准数据元素移到将基准数据元素移到low所指位置所指位置return low;/返回排序后基准数据元素的位置返回排序后基准数据元素的位置void QuickSort(SeqList*L,int low,int high)/对顺序表对顺序表L作快速排序作快速排序int p;if(low high)/表长度大于表长度大于1p=Partition(L,low,high);/对对L进行一趟快速排序，返回基准数据元素的位置进行一趟快速排序，返回基准

26、数据元素的位置QuickSort(L,low,p-1);/对表的前半部分进行快速排序对表的前半部分进行快速排序QuickSort(L,p+1,high);/对表的后半部分进行快速排序对表的后半部分进行快速排序3算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 快速排序是一种快速排序是一种不稳定不稳定的排序算法。的排序算法。最好情况下为最好情况下为O(log2n)，最坏情况下为，最坏情况下为O(n)。最好情况下为最好情况下为O(log2n)，最坏情况下为，最坏情况下为O(n2)，平均时间复杂度为，平均时间复杂度为O(nlog2n)。任务四任务四 选择排

27、序选择排序 一、直接选择排序一、直接选择排序 二、树形选择排序二、树形选择排序三、堆排序三、堆排序 一、直接选择排序一、直接选择排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 通过关键字的比较，每次从待排序列中选出关键字最小的数据元素，将通过关键字的比较，每次从待排序列中选出关键字最小的数据元素，将其与待排序列的第一个数据元素交换，直到全部数据元素都有序排列。其与待排序列的第一个数据元素交换，直到全部数据元素都有序排列。对于一个具有对于一个具有n个数据元素的序列，进行直接选择排序的具体过程是：个数据元素的序列，进行直接选择排序的具体过程是：进行第一趟排序时

28、，用进行第一趟排序时，用r1与其余与其余n1个数据元素比较，选出关键个数据元素比较，选出关键字最小的数据元素与字最小的数据元素与r1交换。交换。进行第二趟排序时，用进行第二趟排序时，用r2与其余与其余n2个数据元素比较，选出关键个数据元素比较，选出关键字最小的数据元素与字最小的数据元素与r2交换。交换。依此类推，进行第依此类推，进行第i趟排序时，用趟排序时，用ri与其余与其余ni个数据元素比较，个数据元素比较，选出关键字最小的数据元素与选出关键字最小的数据元素与ri交换。共需进行交换。共需进行i1趟选择，直到所趟选择，直到所有数据元素有序排列为止。有数据元素有序排列为止。对数据元素序列（对数据

29、元素序列（35，66，2，15，6，81，6*，9）进行直接选择排）进行直接选择排序的过程序的过程：2算法实现算法实现 void SelectSort(SeqList*L)/对顺序表对顺序表L作直接选择排序作直接选择排序int i,j,t;for(i=1;i Length;i+)进行第进行第i趟排序时，选出待排序列中关键字最小的数据元素与趟排序时，选出待排序列中关键字最小的数据元素与ri交换交换t=i;/设置设置t的初值的初值 for(j=i+1;j Length;j+)if(L-rj.key rt.key)/找到待排序列中关键字最小的数据元素找到待排序列中关键字最小的数据元素 t=j;/记录

30、关键字最小的数据元素的下标记录关键字最小的数据元素的下标 if(t!=i)/关键字最小的数据元素与第关键字最小的数据元素与第i个数据元素交换个数据元素交换L-.r0=L-rt;L-rt=L-ri;L-.ri=L-r0;3算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 直接选择排序是一种直接选择排序是一种不稳定不稳定的排序算法。的排序算法。排序过程中仅使用了一个辅助单元，算法的空间复杂度为排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。直接选择排序的平均时间复杂度为直接选择排序的平均时间复杂度为O(n2)。二、树形选择排序二、树形选择排序

31、 2算法分析算法分析 1基本思想基本思想 1基本思想基本思想 对待排序列的所有数据元素进行两两比较，选出每两个中的较小者，然对待排序列的所有数据元素进行两两比较，选出每两个中的较小者，然后采取同样方法对这些较小者再进行两两比较，如此反复，直至选出关后采取同样方法对这些较小者再进行两两比较，如此反复，直至选出关键字最小的数据元素并输出；将该数据元素置为键字最小的数据元素并输出；将该数据元素置为，以便进行下一趟选，以便进行下一趟选择排序，择排序，当所有数据元素全部输出，则排序完成。当所有数据元素全部输出，则排序完成。对数据元素序列（对数据元素序列（35，66，2，15，6，81，6*，9）进行树形

32、选择排序）进行树形选择排序的过程如下：的过程如下：2算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 算法的空间复杂度为算法的空间复杂度为O(n)。时间复杂度为时间复杂度为O(nlog2n)。树形选择排序是一种树形选择排序是一种稳定稳定的排序方法。的排序方法。三、堆排序三、堆排序 1堆的定义堆的定义 2基本思想基本思想 3算法实现算法实现 4算法分析算法分析 1堆的定义堆的定义 n个关键字序列个关键字序列kl，k2，kn，当且仅当该序列满足如下性质时称为，当且仅当该序列满足如下性质时称为堆堆。树中任一非叶子结点的关键字均不大于或不小于其左右孩子结点的

33、关键树中任一非叶子结点的关键字均不大于或不小于其左右孩子结点的关键字。其中，前者称为字。其中，前者称为小顶堆小顶堆，后者称为，后者称为大顶堆大顶堆。堆实质上是满足如下性质的完全二叉树：堆实质上是满足如下性质的完全二叉树：2基本思想基本思想 将待排序列初始化为大顶堆（或小顶堆），然后将堆顶数据元素与最后将待排序列初始化为大顶堆（或小顶堆），然后将堆顶数据元素与最后一个叶子结点交换，输出该叶子结点表示的数据元素；然后将剩余的数一个叶子结点交换，输出该叶子结点表示的数据元素；然后将剩余的数据元素重新调整为大顶堆（或小顶堆），重复以上操作，直到所有数据据元素重新调整为大顶堆（或小顶堆），重复以上操作，

34、直到所有数据元素有序输出。元素有序输出。对数据元素序列（对数据元素序列（35，66，2，15，6，81，6*，9）进行堆排序的过）进行堆排序的过程如下所示。程如下所示。3算法实现算法实现 void HeapAdjust(SeqList*L,int s,int m)/将顺序表将顺序表L中的中的rsm调整为一个大顶堆调整为一个大顶堆int j;L-r0=L-rs;/保存根结点保存根结点for(j=2*s;j=m;j*=2)/沿关键字较大的孩子结点向下筛选沿关键字较大的孩子结点向下筛选if(j rj.key rj+1.key)j+;/令令j为关键字较大的元素的下标为关键字较大的元素的下标if(L-r

35、0.key=L-rj.key)break;/若若r0最大，将最大，将r0插入在位置插入在位置s上上elseL-.rs=L-rj;/将关键字最大的结点插入在位置将关键字最大的结点插入在位置ss=j;/沿关键字最大的结点进行下一层筛选沿关键字最大的结点进行下一层筛选L-rs=L-r0;/插入最后一个结点插入最后一个结点void HeapSort(SeqList*L)/对顺序表对顺序表L进行堆排序进行堆排序int i,j;for(i=L-length/2;i 0;i-)/将将rsm调整为一个大顶堆调整为一个大顶堆HeapAdjust(L,i,L-length);for(i=L-length;i 1;

36、i-)L-r0=L-r1;/将堆顶元素与最后一个元素交换将堆顶元素与最后一个元素交换L-r1=L-ri;L-ri=L-r0;HeapAdjust(L,1,i-1);/将将L.r1i-1重新调整为大顶堆重新调整为大顶堆4算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 堆排序的时间复杂度为堆排序的时间复杂度为O(nlog2n)。堆排序是一种堆排序是一种不稳定不稳定的排序方法。的排序方法。堆排序仅使用了一个辅助单元，算法的空间复杂度为堆排序仅使用了一个辅助单元，算法的空间复杂度为O(1)。任务五任务五 归并排序和基数排序归并排序和基数排序 一、归并排序一

37、、归并排序 二、基数排序二、基数排序 一、归并排序一、归并排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 对于一个具有对于一个具有n个数据元素的序列，将其中的每个数据元素看成长度个数据元素的序列，将其中的每个数据元素看成长度为为1的有序子表，然后对其进行两两归并，即第的有序子表，然后对其进行两两归并，即第1个子表与第个子表与第2个子表个子表归并，第归并，第3个子表与第个子表与第4个子表归并，依此类推，这样得到个子表归并，依此类推，这样得到n/2个长度为个长度为2的有序表（若的有序表（若n为奇数，则最后一个有序表的长度为为奇数，则最后一个有序表的长度为1）；

38、在此基础）；在此基础上再进行两两归并，得到上再进行两两归并，得到n/4个长度为个长度为4的有序表（最后一个有序表的的有序表（最后一个有序表的长度可能小于长度可能小于4），依此类推，直至得到一个长度为），依此类推，直至得到一个长度为n的有序表为止。的有序表为止。对数据元素序列（对数据元素序列（35，66，2，15，6，81，6*，9）进行归并排序的）进行归并排序的过程如下图所示。过程如下图所示。2算法实现算法实现 void Merge(RecordType r1,RecordType r2,int low,int mid,int high)/r1lowmid和和r1mid+1high分别按关键字

39、有序排列，将它分别按关键字有序排列，将它们合并为有序序列存放们合并为有序序列存放/在在r2lowhigh中中int i,j,k;i=low;j=mid+1;k=low;/i、j分别为指向分别为指向r1lowmid和和r1mid+1high的指针，将的指针，将r1中中的数据元素由小到大并入的数据元素由小到大并入r2中中while(i=mid)&(j=high)/值小的送入值小的送入r2if(r1i.key r1j.key)r2k=r1i;/r1lowmid中的元素送入中的元素送入r2i+;/指针指针i后移后移elser2k=r1j;/r1mid+1high中的元素送入中的元素送入r2j+;/指针

40、指针j后移后移k+;while(i=mid)/若若r1lowmid中有元素剩余，直接将剩余元素复制到中有元素剩余，直接将剩余元素复制到r2中中r2k=r1i;k+;i+;while(j r,L-r,1,L-length);3算法分析算法分析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 归并排序的时间复杂度为归并排序的时间复杂度为O(nlog2n)。归并排序是一种归并排序是一种稳定稳定的排序方法。的排序方法。排序过程中需要一个与待排序列等长的辅助单元存放数据元素，因此，排序过程中需要一个与待排序列等长的辅助单元存放数据元素，因此，算法的空间复杂度为算法的空间复杂度

41、为O(n)。二、基数排序二、基数排序 2基本思想基本思想 3算法实现算法实现 4算法分析算法分析 1基本概念基本概念 1基本概念基本概念 基数排序是一种基于基数排序是一种基于多关键字排序多关键字排序思想进行排序的排序方法。思想进行排序的排序方法。例如，表例如，表8-28-2给出的某班学生成绩单中包含了数学成绩和英语成绩（用给出的某班学生成绩单中包含了数学成绩和英语成绩（用A A、B B、C C、D D、E 5E 5个等级来表示），对该成绩单先按数学成绩的等级由高到个等级来表示），对该成绩单先按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的等级由高到低排序。低排序，数学成绩相同的学

42、生再按英语成绩的等级由高到低排序。高位优先法高位优先法（Most Significant Digit first，简称，简称MSD）：先按数学成绩的）：先按数学成绩的等级由高到低将学生记录分成等级由高到低将学生记录分成A、B、C、D、E 5组，再分别对每组记录按组，再分别对每组记录按英语成绩的等级由高到低进行排序。英语成绩的等级由高到低进行排序。低位优先法低位优先法（Least Significant Digit first，简称，简称LSD）：先按英语成）：先按英语成绩的等级由高到低将学生记录分成绩的等级由高到低将学生记录分成A、B、C、D、E 5组，再将其按从组，再将其按从左到右、从上到下

43、的顺序排列，得到关键字序列，如左图所示；然后左到右、从上到下的顺序排列，得到关键字序列，如左图所示；然后按数学成绩的等级由高到低重新分成按数学成绩的等级由高到低重新分成A、B、C、D、E 5组，再将其按组，再将其按从左到右、从上到下的顺序排列，得到关键字序列，如右图所示；从左到右、从上到下的顺序排列，得到关键字序列，如右图所示；2基本思想基本思想 根据基数的值设立相应个数的队列，排序时先按最低位子关键字的值根据基数的值设立相应个数的队列，排序时先按最低位子关键字的值进行排序，即按子关键字的不同值将各数据元素分配到相应的队列中，进行排序，即按子关键字的不同值将各数据元素分配到相应的队列中，然后按

44、照一定顺序将数据元素收集起来，此时得到的序列已按最低位然后按照一定顺序将数据元素收集起来，此时得到的序列已按最低位子关键字有序排列。在此基础上按次低位子关键字的值进一步排序，子关键字有序排列。在此基础上按次低位子关键字的值进一步排序，依此类推，直至按关键字的最高位排序后，整个序列排序完成。依此类推，直至按关键字的最高位排序后，整个序列排序完成。例如，对数据元素序列例如，对数据元素序列3535，6666，2 2，1515，6 6，8181，6 6*，99进行基数排进行基数排序的过程如下图所示。序的过程如下图所示。3算法实现算法实现 数据类型定义如下：数据类型定义如下：#define KEY_SI

45、ZE 10/关键字项数最大值关键字项数最大值#define RADIX 10/关键字基数关键字基数#define LIST_SIZE 20/静态链表的最大容量静态链表的最大容量typedef structKeyType keyKEY_SIZE;/子关键字数组子关键字数组OtherTyp otheritem;/其他数据项其他数据项int next;/静态链表的指针域静态链表的指针域RecordType;typedef struct/定义静态链表类型定义静态链表类型RecordType rLIST_SIZE+1;/r0为头结点为头结点int keynum;/当前关键字个数当前关键字个数int le

46、ngth;/静态链表的当前长度静态链表的当前长度SLinkList;typedef int headtailRADIX;/指针数组类型指针数组类型 算法描述如下：算法描述如下：void Distribute(SeqList*L,int i,headtail head,headtail tail)/静态链表静态链表L已按已按keyi+1之后的关键字进行过之后的关键字进行过“低位优先低位优先”排序，排序，对对L按第按第i个关键字个关键字keyi进行第进行第i趟分配趟分配int i,j;int p;for(j=0;j .r0.next;p!=0;p=L-rp.next)j=Order(L-rp.ke

47、yi);/求第求第i个关键字对应的队列号个关键字对应的队列号if(headj=0)/如果第如果第j个队列为空，头指针指向个队列为空，头指针指向pheadj=p;else L-rtailj.next=p;/如果第如果第j个队列不空，将个队列不空，将p插入到第插入到第j个队列队尾个队列队尾tailj=p;/队尾指针指向队尾指针指向pvoid Collect(Seqlist*L,int i,headtail head,headtail tail)/按第按第i个关键字个关键字keyi进行第进行第i趟收集，即将所有非空队列首尾相接链接趟收集，即将所有非空队列首尾相接链接为一个链表为一个链表int j;i

48、nt t;for(j=0;headj=0;j+);/寻找第一个非空队列寻找第一个非空队列L-r0.next=headj;/r0.next指向第一个非空队列中第一个结点指向第一个非空队列中第一个结点t=tailj;/t指向第一个非空队列中最后一个结点指向第一个非空队列中最后一个结点while(j RADIX)/将所有非空队列链接为一个链表将所有非空队列链接为一个链表for(j+;j rt.next=headj;/将当前非空的头链接在前一个非空队列的尾上将当前非空的头链接在前一个非空队列的尾上t=tailj;/t指向当前非空队列中最后一个结点指向当前非空队列中最后一个结点L-rt.next=0;/

49、t指向最后一个非空队列中的最后一个结点指向最后一个非空队列中的最后一个结点void RadixSort(SeqList*L)/对静态链表对静态链表L进行基数排序进行基数排序for(i=0;i length;i+)/对静态链表进行初始化对静态链表进行初始化L-ri.next=i+1;L-rL-length.next=0;for(i=L-keynum 1;i=0;i-)/按低位优先依次对各关键字进行分配和收集按低位优先依次对各关键字进行分配和收集Distribute(L,i,head,tail);/第第i趟分配趟分配Collect(L,i,head,tail);/第第i趟收集趟收集4算法分析算法分

50、析（1）空间复杂度）空间复杂度（2）时间复杂度）时间复杂度（3）稳定性）稳定性 在基数排序算法中，一趟分配的时间复杂度为在基数排序算法中，一趟分配的时间复杂度为O(n)，一趟收集的时间，一趟收集的时间复杂度为复杂度为O(RADIX)，整个排序过程共进行，整个排序过程共进行d趟分配和收集。因此，基趟分配和收集。因此，基数排序的时间复杂度为数排序的时间复杂度为O(nd)。基数排序是一种基数排序是一种稳定稳定的排序方法。的排序方法。链式基数排序需要链式基数排序需要2*RADIX个指向队列的指针，以及用于静态链表的个指向队列的指针，以及用于静态链表的n个指针。因此，基数排序所需的辅助存储空间为个指针。