数据结构(C语言) 排序课件

Data StructureData Structure数据结构(C语言) 排序Page 12022-6-20q 学习目标学习目标v理解排序的定义和各种排序方法的特点，并能加以灵活应用。理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序排序方法有不同的分类方法，基于方法有不同的分类方法，基于“关键字间的比较关键字间的比较”进行排序的方法进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。排序、归并排序和计数排序等五类。v掌握各种排序方法的时间复杂度的分析方法。掌握各种排序方法的时间复杂度的分析方法。能从能从“关键字间的比关键字间的比较次数较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：时间复杂度划分，内部排序可分为三类：O O (n(n2 2) ) 的简单排序方法，的简单排序方法，O O (nlogn) (nlogn) 的高效排序方法和的高效排序方法和O O (dn)(dn)的基数排序方法。的基数排序方法。v理解排序方法理解排序方法 稳定稳定 或或 不稳定不稳定 的含义，弄清楚在什么情况下要求的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。应用的排序方法必须是稳定的。Data StructureData Structure数据结构(C语言) 排序Page 22022-6-20q 重点和难点重点和难点v重点重点：希尔排序、快速排序、堆排序和归并排序等高效方法：希尔排序、快速排序、堆排序和归并排序等高效方法v难点难点：希尔排序、快速排序、堆排序和归并排序等高效方法：希尔排序、快速排序、堆排序和归并排序等高效方法q 知识点知识点v排序、直接插入排序、折半插入排序、表插入排序、希尔排序、排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、起泡排序、快速排序、简单选择排序、堆排序、2-2-路归并排序、路归并排序、基数排序、排序方法的综合比较。基数排序、排序方法的综合比较。Data StructureData Structure数据结构(C语言) 排序Page 32022-6-20q 排序排序v假设含有假设含有n n个记录的序列为：个记录的序列为：RR1 1，R R2 2，R Rn n ， 它们的关键字相应为它们的关键字相应为KK1 1，K K2 2，K Kn n ， 对记录序列进行对记录序列进行排序排序就是要确定序号就是要确定序号1 1，2 2，n n的一种排列的一种排列 P P1 1，P P2 2，P Pn n，使其相应的关键字满足如下的使其相应的关键字满足如下的非递减（或非递增）非递减（或非递增）的关系：的关系： K Kp1p1=K=Kp2p2=K=Kpnpn 使序列成为一个按关键字有序的序列使序列成为一个按关键字有序的序列 RRp p1 1，R Rp p2 2，R Rp pn n v目的目的利用高效的查找方法，以提高查找效率。利用高效的查找方法，以提高查找效率。Data StructureData Structure数据结构(C语言) 排序Page 42022-6-20q 排序分类排序分类v按待排序记录所在位置按待排序记录所在位置内部排序内部排序：待排序记录存放在内存。：待排序记录存放在内存。外部排序外部排序：排序过程中需对外存进行访问的排序。：排序过程中需对外存进行访问的排序。v按排序依据原则按排序依据原则插入排序插入排序：直接插入排序、折半插入排序、希尔排序。：直接插入排序、折半插入排序、希尔排序。交换排序交换排序：冒泡排序、快速排序。：冒泡排序、快速排序。选择排序选择排序：简单选择排序、堆排序。：简单选择排序、堆排序。归并排序归并排序：2-2-路归并排序。路归并排序。基数排序基数排序Data StructureData Structure数据结构(C语言) 排序Page 52022-6-20q 稳定稳定v若待排序文件中有若待排序文件中有关键字相等的记录，排序后，其前后相对次序关键字相等的记录，排序后，其前后相对次序与排序前未发生变化与排序前未发生变化，这种排序称为，这种排序称为“稳定稳定”排序；否则是排序；否则是“不不稳定稳定”排序。排序。v稳定排序与不稳定排序稳定排序与不稳定排序只是表示所用的排序方法，只是表示所用的排序方法，并不说明哪种并不说明哪种方法好与差。方法好与差。q 排序基本操作排序基本操作v比较比较两个关键字大小；两个关键字大小；v将记录从一个位置将记录从一个位置移动移动到另一个位置；到另一个位置；q 就全面性能而言，就全面性能而言，很难提出一种被认为最好的方法很难提出一种被认为最好的方法，每种，每种方法均有优点和适用环境。方法均有优点和适用环境。Data StructureData Structure数据结构(C语言) 排序Page 62022-6-20q 本章讨论中，待排记录如下结构。本章讨论中，待排记录如下结构。#define MAXSIZE 20; #define MAXSIZE 20; / / 假设的顺序表最大长度假设的顺序表最大长度type int KeyType; type int KeyType; / / 定义关键字类型为整数类型定义关键字类型为整数类型typedef struct typedef struct KeyType key; KeyType key; / / 关键字项关键字项InfoType otherinfo;InfoType otherinfo; / / 其它数据项其它数据项 RcdType; RcdType; / / 记录类型记录类型typedef struct typedef struct RcdType rMAXSIZE+1;RcdType rMAXSIZE+1; / r0/ r0闲置或作为判别标志的闲置或作为判别标志的“哨兵哨兵”单元单元 int length; int length; / / 顺序表长度顺序表长度 SqList SqList；/ / 顺序表类型顺序表类型Data StructureData Structure数据结构(C语言) 排序Page 72022-6-2010.2.1 10.2.1 直接插入排序直接插入排序q 基本思想基本思想v整个排序过程为整个排序过程为n-1n-1趟插入趟插入，即，即先将先将序列中第序列中第1 1个记录看成是一个个记录看成是一个有序子序列有序子序列，然后，然后从第从第2 2个记录开始个记录开始，逐个进行插入逐个进行插入，直至整个直至整个序列有序序列有序。Data StructureData Structure数据结构(C语言) 排序Page 82022-6-2049 38 65 97 76 13 2749 38 65 97 76 13 27i=2 ( 49 ) 38 65 97 76 13 27i=2 ( 49 ) 38 65 97 76 13 27i=3 ( 38 49 ) 65 97 76 13 27i=3 ( 38 49 ) 65 97 76 13 27i=4 i=4 ( 38 49 65 ) 97 76 13 27 ( 38 49 65 ) 97 76 13 27i=5 i=5 ( 38 49 65 97 ) 76 13 27 ( 38 49 65 97 ) 76 13 27i=6 i=6 ( 38 49 65 76 97 )13 27 ( 38 49 65 76 97 )13 27i=1 ( )i=1 ( )i=7 ( 13 38 49 65 76 97 ) 27i=7 ( 13 38 49 65 76 97 ) 272727979776766565494938382727 ( 13 27 38 49 65 76 97 ) ( 13 27 38 49 65 76 97 )排序结果：排序结果：383838384949656597979797767697977676131376766565494938381313) ) ) ) ) ) ) ) ) ) ) ) )监视哨监视哨r0r0 r1r1 r2r2 r3r3 r4r4 r5r5 r6r6 r7r7Data StructureData Structure数据结构(C语言) 排序Page 92022-6-20q直接插入排序的算法直接插入排序的算法1 12 23 34 45 56 67 78 8时间复杂度时间复杂度T(n)=O(nT(n)=O(n) )Data StructureData Structure数据结构(C语言) 排序Page 102022-6-20q 算法评价算法评价v时间复杂度时间复杂度 若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列( (正序正序) ) 关键字比较次数：关键字比较次数：112nni记录移动次数：记录移动次数：21(1)nin 若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列( (逆序逆序) ) 关键字比较次数：关键字比较次数：2)1)(2(2nnini记录移动次数：记录移动次数：2)1)(4()1(2nniniData StructureData Structure数据结构(C语言) 排序Page 112022-6-20 若待排序记录是若待排序记录是随机随机的，取平均值。的，取平均值。关键字比较次数：关键字比较次数：42n记录移动次数：记录移动次数：42nv空间复杂度空间复杂度S(n)=O(1)S(n)=O(1)Data StructureData Structure数据结构(C语言) 排序Page 122022-6-20q 折半插入排序折半插入排序v基本思想基本思想 用折半查找方法确定插入位置的排序。用折半查找方法确定插入位置的排序。i=1 (30) 13 70 85 39 42 6 20i=1 (30) 13 70 85 39 42 6 20i=2 i=2 1313 (13 30) 70 85 39 42 6 20 (13 30) 70 85 39 42 6 20i=7 i=7 6 6 (6 13 30 39 42 70 85 ) 20 (6 13 30 39 42 70 85 ) 20i=8 i=8 2020 (6 13 30 39 42 70 85 ) 20 (6 13 30 39 42 70 85 ) 20i ih hi=8 i=8 2020 (6 13 (6 13 2020 30 39 42 70 85 ) 30 39 42 70 85 )h hm mi im mh hm m插入位置插入位置Data StructureData Structure数据结构(C语言) 排序Page 132022-6-20void BInsertSort (SqList &L)void BInsertSort (SqList &L)/ / 对顺序表对顺序表L L作折半插入排序作折半插入排序 for ( i=2; i=L.length; +i )for ( i=2; i=L.length; +i ) L.r0 = L.ri;L.r0 = L.ri;/ / 将将L.riL.ri暂存到暂存到L.r0L.r0 low = 1; high = i-1;low = 1; high = i-1; while (low=high) while (low=high+1; -j ) L.rj+1 = L.rj; for ( j=i-1; j=high+1; -j ) L.rj+1 = L.rj; / / 记录后移记录后移L.rhigh+1 = L.r0;L.rhigh+1 = L.r0; / / 插入插入 / BInsertSort/ BInsertSort时间复杂度：时间复杂度：T(n)=O(nT(n)=O(n) )Data StructureData Structure数据结构(C语言) 排序Page 142022-6-20v算法评价算法评价时间复杂度：时间复杂度：T(n)=O(nT(n)=O(n) )空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1) 折半插入排序只能折半插入排序只能减少排序过程中关键字比减少排序过程中关键字比较的时间，并不能减少记录移动的时间较的时间，并不能减少记录移动的时间。Data StructureData Structure数据结构(C语言) 排序Page 152022-6-20q 2-2-路插入排序路插入排序v基本思想基本思想 另设一个另设一个和和L.rL.r同类型的同类型的数组数组d d，首先，首先将将L.r1L.r1赋给赋给d1d1，并将，并将d1d1看成是看成是在排好序的序列中处于在排好序的序列中处于中间位置的记录中间位置的记录，然后，然后从从L.rL.r中第中第2 2个记录起依次插入到个记录起依次插入到d1d1之前或之后的有序序列中之前或之后的有序序列中。v目的目的 对折半插入排序的改进，减少记录的移动次数。对折半插入排序的改进，减少记录的移动次数。Data StructureData Structure数据结构(C语言) 排序Page 162022-6-20初始关键字初始关键字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=1i=1(49)(49)firstfirstfinalfinali=2i=2(49) (38)(49) (38)firstfirstfinalfinali=3i=3(49 65) (38)(49 65) (38)firstfirstfinalfinali=4i=4(49 65 97) (38)(49 65 97) (38)firstfirstfinalfinalData StructureData Structure数据结构(C语言) 排序Page 172022-6-20初始关键字初始关键字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=4i=4(49 65 97) (38)(49 65 97) (38)firstfirstfinalfinali=5i=5(49 65 76 97) (38)(49 65 76 97) (38)firstfirstfinalfinali=6i=6(49 65 76 97) (13 38)(49 65 76 97) (13 38)firstfirstfinalfinali=7i=7(49 65 76 97) (13 27 38)(49 65 76 97) (13 27 38)firstfirstfinalfinalData StructureData Structure数据结构(C语言) 排序Page 182022-6-20初始关键字初始关键字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=7i=7(49 65 76 97) (13 27 38)(49 65 76 97) (13 27 38)firstfirstfinalfinali=8i=8firstfirstfinalfinal(49 49 65 76 97) (13 27 38)(49 49 65 76 97) (13 27 38) 2 2路插入排序的路插入排序的移动记录次数减少了移动记录次数减少了，约为约为n n2 2/8/8，但不能避免移动但不能避免移动。Data StructureData Structure数据结构(C语言) 排序Page 192022-6-20q 基本思想基本思想v是是对插入排序的一个改进对插入排序的一个改进，也称缩小增量排序。，也称缩小增量排序。v先将整个先将整个待排序记录序列分割成若干个子序列待排序记录序列分割成若干个子序列，分别对这些，分别对这些子序子序列进行直接插入排序列进行直接插入排序；待整个序列中的记录；待整个序列中的记录“基本有序基本有序”时，再时，再对对全体记录进行一次直接插入排序全体记录进行一次直接插入排序。q 排序过程排序过程v取一个取一个正整数正整数d1nd1n，把所有，把所有相隔相隔d1d1的记录放一组的记录放一组，组内组内进行进行直接直接插入排序插入排序；v然后然后取取d2d1d2d1，重复上述重复上述分组和排序分组和排序操作操作；v直至直至di=1di=1，即所有记录放进一个组中排序为止。，即所有记录放进一个组中排序为止。Data StructureData Structure数据结构(C语言) 排序Page 202022-6-20取取d3=1d3=1三趟分组：三趟分组：三趟排序结果：三趟排序结果：一趟排序结果：一趟排序结果：二趟排序结果：二趟排序结果：取取d1=5d1=5一趟分组：一趟分组：取取d2=3d2=3二趟分组：二趟分组：49 38 65 97 76 13 27 49 55 449 38 65 97 76 13 27 49 55 413 27 49 55 4 49 38 65 97 7613 27 49 55 4 49 38 65 97 7613 27 49 55 4 49 38 65 97 7613 27 49 55 4 49 38 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 764 13 27 38 49 49 55 65 76 974 13 27 38 49 49 55 65 76 97Data StructureData Structure数据结构(C语言) 排序Page 212022-6-20void ShellInsert ( SqList &Lvoid ShellInsert ( SqList &L，int dk)int dk)/ / 对顺序表对顺序表L L作一趟希尔插入排序。本算法是和一趟直接插入排序作一趟希尔插入排序。本算法是和一趟直接插入排序/ / 相比，作了如下修改：相比，作了如下修改：1.1.前后记录位置的增量是前后记录位置的增量是dkdk，不是，不是1 1；/ 2.r0/ 2.r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0j=0时，插入位置已找到。时，插入位置已找到。for ( i=dk+1; i=L.length; +i )for ( i=dk+1; i0<(L.r0.key,L.rj.key); j-=dk ) for(j=i-dk; j0<(L.r0.key,L.rj.key); j-=dk ) L.rj+dk = L.rj; L.rj+dk = L.rj; / / 记录后移，查找插入位置记录后移，查找插入位置 L.rj+dk = L.r0; L.rj+dk = L.r0; / / 插入插入 / if / if / ShellInsert / ShellInsertData StructureData Structure数据结构(C语言) 排序Page 222022-6-20void ShellSort (SqList &L, int dlta, int t)void ShellSort (SqList &L, int dlta, int t)/ / 按增量序列按增量序列 dlta0.t-1 dlta0.t-1 对顺序表对顺序表L L作希尔排序作希尔排序for (k=0; kt; +t) for (k=0; kr2.keyr1.keyr2.key，则交换则交换；然后比较；然后比较第二个记录与第二个记录与第三个记录第三个记录；依次类推，；依次类推，直至第直至第n-1n-1个记录和第个记录和第n n个记录个记录比较比较为止为止第一趟冒泡排序第一趟冒泡排序，结果关键字最大的记录被安置在结果关键字最大的记录被安置在最后一个记录上最后一个记录上。对前对前n-1n-1个记录进行第二趟冒泡排序个记录进行第二趟冒泡排序，结果使关键字次大的记，结果使关键字次大的记录被安置在第录被安置在第n-1n-1个记录位置个记录位置重复上述过程，重复上述过程，直到直到“在一趟排序过程中没有进行过交换记在一趟排序过程中没有进行过交换记录的操作录的操作”为止。为止。Data StructureData Structure数据结构(C语言) 排序Page 252022-6-2038 13 2738 13 27 49 49 4949第四趟后第四趟后494938 49 13 27 30 38 49 13 27 30 6565第三趟后第三趟后494938 49 65 13 27 30 38 49 65 13 27 30 7676第二趟后第二趟后494938 49 65 76 13 27 30 38 49 65 76 13 27 30 9797第一趟后第一趟后494949 38 65 97 76 13 27 4949 38 65 97 76 13 27 49初始关键字初始关键字13 27 3813 27 38 4949第五趟后第五趟后49497676979713139797272797979797131376767676272713136565272765656565131313134949494927273838272738383838494949497676494913 27 13 27 3838第六趟后第六趟后q 时间复杂度时间复杂度v最好情况（正序）最好情况（正序） 比较次数：比较次数：n-1n-1 移动次数：移动次数：0 0v最坏情况（逆序）最坏情况（逆序） 比较次数：比较次数：q 空间复杂度空间复杂度：S(n)=O(1)S(n)=O(1)(21)(211nninni)(23)(321nninni移动次数：移动次数：Data StructureData Structure数据结构(C语言) 排序Page 262022-6-20q快速排序快速排序v对起泡法的一种改进。对起泡法的一种改进。v基本思想基本思想通过通过一趟排序一趟排序，将，将待排序记录分割成独立的两部分待排序记录分割成独立的两部分，其中，其中一部一部分记录的关键字均比另一部分记录的关键字小分记录的关键字均比另一部分记录的关键字小，则可，则可分别对这分别对这两部分记录进行排序两部分记录进行排序，以达到整个序列有序。，以达到整个序列有序。Data StructureData Structure数据结构(C语言) 排序Page 272022-6-20v排序过程排序过程 对对rstrst中记录进行一趟快速排序，附设两个指针中记录进行一趟快速排序，附设两个指针i i和和j j，设枢轴记录设枢轴记录rp=rsrp=rs，x=rp.keyx=rp.key，初始时，初始时令令i=s,j=ti=s,j=t；首先，首先，从从j j所指位置向前搜索第一个关键字小于所指位置向前搜索第一个关键字小于x x的记录，并的记录，并和和rprp交换交换；再再从从i i所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于x x的记录，的记录，和和rprp交换交换；重复上述两步，重复上述两步，直至直至i=ji=j为止为止；再再分别对两个子序列进行快速排序分别对两个子序列进行快速排序，直到每个子序列只含有直到每个子序列只含有一个记录为止一个记录为止。Data StructureData Structure数据结构(C语言) 排序Page 282022-6-2049 38 65 97 76 13 27 4949 38 65 97 76 13 27 492727i i初始关键字：初始关键字：j jx x 4949j ji ii i6565j j1313i i9797j jj j494949 38 65 97 76 13 27 4949 38 65 97 76 13 27 49初始关键字：初始关键字： 完成一趟排序：完成一趟排序： 27 38 13 27 38 13 4949 76 97 65 49 76 97 65 49 一次划分后：一次划分后：( 27 38 13 ) ( 27 38 13 ) 4949 ( 76 97 65 49 ) ( 76 97 65 49 ) 分别进行快速排序：分别进行快速排序：( 13 )( 13 ) 2727 ( 38 )( 38 ) 4949 ( 49 65 ) ( 49 65 ) 76 76 ( 97 )( 97 ) ( 13 ) ( 13 ) 2727 ( 38 )( 38 ) 4949 4949 (65) (65) 76 76 ( 97 )( 97 )快速排序结束：快速排序结束： 1313 27 27 38 38 4949 4949 65 65 76 76 97 97Data StructureData Structure数据结构(C语言) 排序Page 292022-6-20int Partition ( SqList &L, int low, int high)int Partition ( SqList &L, int low, int high)/ / 交换顺序表交换顺序表L L中子表中子表rlow.highrlow.high中的记录，枢轴记录到位，并返回中的记录，枢轴记录到位，并返回/ / 其所在位置，此时，在它之前（后）的记录均不大（小）于它。其所在位置，此时，在它之前（后）的记录均不大（小）于它。L.r0 = L.rlow;L.r0 = L.rlow;/用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录pivotkey = L.rlow.key; pivotkey = L.rlow.key; / / 枢轴记录关键字枢轴记录关键字while (low high) while (low high) / / 从表的两端交替地向中间扫描从表的两端交替地向中间扫描while (low = pivotkey) -high;while (low = pivotkey) -high;L.rlow+ = L.rhigh;L.rlow+ = L.rhigh;/ / 将比枢轴记录小的记录移到低端将比枢轴记录小的记录移到低端while (low high & L.rlow.key = pivotkey)while (low high & L.rlow.key = pivotkey)+low;+low;L.rhigh = L.rlow;L.rhigh = L.rlow;/ / 将比枢轴记录大的记录移到高端将比枢轴记录大的记录移到高端 / while/ while L.rlow = L.r0; L.rlow = L.r0;/ / 枢轴记录到位枢轴记录到位return low; return low; / / 返回枢轴位置返回枢轴位置 / Partition / PartitionData StructureData Structure数据结构(C语言) 排序Page 302022-6-20void Qsort(SqList &L, int low, int high)void Qsort(SqList &L, int low, int high)/对顺序表对顺序表L L中的子序列中的子序列L.rlowhighL.rlowhigh作快速排序作快速排序if (low high) if (low high) /长度大于长度大于1 1pivotloc= pivotloc= Partition(L,low,high)Partition(L,low,high); ; /将将L.rlowhighL.rlowhigh划分划分Qsort(L,low,pivotloc-1); Qsort(L,low,pivotloc-1); /对低子表排序对低子表排序Qsort(L, pivotloc+1,high); Qsort(L, pivotloc+1,high); /对高子表排序对高子表排序 / Qsort/ Qsortvoid QuickSort(SqList &L)void QuickSort(SqList &L)/对顺序表对顺序表L L作快速排序作快速排序Qsort(L,1,L.length); Qsort(L,1,L.length); / QuickSort/ QuickSort时间复杂度时间复杂度T(n)=O(nT(n)=O(n) )Data StructureData Structure数据结构(C语言) 排序Page 312022-6-20q 算法分析算法分析v时间复杂度时间复杂度最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）T(n)=O(nlogT(n)=O(nlog2 2n)n)最坏情况（每次总是选到最小或最大元素作枢轴）最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(nT(n)=O(n) )为防止最差情况的出现，为防止最差情况的出现，一般采取一般采取“三者取中三者取中”法来确定枢轴。法来确定枢轴。即在第一个记录和最后一个记录，以及中间位置的记录中，选取即在第一个记录和最后一个记录，以及中间位置的记录中，选取值为中间的那个来作枢轴，这样就能防止最差情况的出现。值为中间的那个来作枢轴，这样就能防止最差情况的出现。v空间复杂度空间复杂度：需栈空间以实现递归：需栈空间以实现递归最坏情况：最坏情况：S(n)=O(n)S(n)=O(n)一般情况：一般情况：S(n)=O(logS(n)=O(log2 2n)n)v对随机的关键字序列，快速排序是对随机的关键字序列，快速排序是目前被认为是最好的排序方法目前被认为是最好的排序方法。Data StructureData Structure数据结构(C语言) 排序Page 322022-6-20q 基本思想基本思想v每一趟在每一趟在n-i+1n-i+1（i=1,2,n-1i=1,2,n-1）个记录中选取关键字最小的记）个记录中选取关键字最小的记录，录，并将它和第并将它和第i i个记录进行互换，从而个记录进行互换，从而使其成为有序序列中第使其成为有序序列中第i i个记录。个记录。10.4.1 10.4.1 简单选择排序简单选择排序q 排序过程排序过程v首先，通过首先，通过n-1n-1次关键字比较次关键字比较，从从n n个记录中找出关键字最小的记个记录中找出关键字最小的记录录，将它，将它与第一个记录交换与第一个记录交换；v再通过再通过n-2n-2次比较次比较，从剩余的，从剩余的n-1n-1个记录中个记录中找出关键字次小的记录找出关键字次小的记录，将它将它与第二个记录交换与第二个记录交换；v重复上述操作，重复上述操作，共进行共进行n-1n-1趟排序后，排序结束趟排序后，排序结束。Data StructureData Structure数据结构(C语言) 排序Page 332022-6-20 1313 ( 38 65 97 76 49 27 49 ) ( 38 65 97 76 49 27 49 )初始：初始： ( 49 38 65 97 76 13 27 49 )( 49 38 65 97 76 13 27 49 )i=1i=113134949i=2i=227273838i=3i=3i=4i=4i=5i=5i=6i=613 2713 27 ( 65 97 76 49 38 49 ) ( 65 97 76 49 38 49 )3838656513 27 3813 27 38 ( 97 76 49 65 49 ) ( 97 76 49 65 49 )4949979713 27 38 4913 27 38 49 ( 76 97 65 49 ) ( 76 97 65 49 )4949767613 27 38 4913 27 38 49 76 ( 97 65 ) 76 ( 97 65 )494976766565979713 27 38 4913 27 38 49 76 97 ( 97 ) 76 97 ( 97 )494976766565767676769797排序结束排序结束13 27 38 4913 27 38 49 76 97 65 ( ) 76 97 65 ( )494976767676979765657676Data StructureData Structure数据结构(C语言) 排序Page 342022-6-20void SelectSort (SqList &L)void SelectSort (SqList &L)/ / 对顺序表对顺序表L L作简单选择排序作简单选择排序for (i=1; iL.length; +i) for (i=1; iL.length; +i) / / 选择第选择第 i i 小的记录，并交换到位小的记录，并交换到位j = i;j = i;for ( k=i+1; k=L.length; k+ )for ( k=i+1; k=L.length; k+ )/ / 在在L.ri.L.lengthL.ri.L.length中选择关键字最小的记录中选择关键字最小的记录if ( LT( L.rk.key , L.rj.key ) j =k ;if ( LT( L.rk.key , L.rj.key ) j =k ;if ( i!=j ) L.rj if ( i!=j ) L.rj L.ri; L.ri; / / 与第与第 i i 个记录互换个记录互换 / for/ for / SelectSort / SelectSort时间复杂度时间复杂度T(n)=O(nT(n)=O(n) )Data StructureData Structure数据结构(C语言) 排序Page 352022-6-20q 算法评价算法评价v时间复杂度时间复杂度记录移动次数记录移动次数最好情况：最好情况：0 0最坏情况：最坏情况：3(n-1)3(n-1)比较次数：比较次数：)(21)(211nninniv空间复杂度空间复杂度：S(n)=O(1)S(n)=O(1)Data StructureData Structure数据结构(C语言) 排序Page 362022-6-20q 堆的定义堆的定义vn n个元素的序列个元素的序列(k1,k2,kn)(k1,k2,kn)，当且仅当满足下列关系时，当且仅当满足下列关系时，称之为堆。称之为堆。221iiiikkkk或或221iiiikkkk1,2,2ni v若将若将此序列此序列对应的一维数组对应的一维数组看成是一个完全二叉树看成是一个完全二叉树，则，则k ki i为二为二叉树的根结点，叉树的根结点，k k2i2i和和k k2i+12i+1分别为分别为k ki i的的“左子树根左子树根”和和“右子树右子树根根”。Data StructureData Structure数据结构(C语言) 排序Page 372022-6-20（9696，8383，2727，3838，1111，9 9）（1313，3838，2727，5050，7676，6565，4949，9797）969627279 911113838838313132727383849496565767650509797大顶堆大顶堆小顶堆小顶堆Data StructureData Structure数据结构(C语言) 排序Page 382022-6-20q 堆排序堆排序v将无序序列建成一个堆，得到关键字最小（或最大）的记录；输将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的出堆顶的最小（大）值后，使剩余的n-1n-1个元素重又建成一个堆，个元素重又建成一个堆，则可得到则可得到n n个元素的次小值；重复执行，得到一个有序序列个元素的次小值；重复执行，得到一个有序序列的过的过程。程。q 堆排序需解决的两个问题堆排序需解决的两个问题：v如何由一个如何由一个无序序列建成一个堆无序序列建成一个堆？( (初始建堆初始建堆) )v如何在输出堆顶元素之后，如何在输出堆顶元素之后，调整调整剩余元素，使之剩余元素，使之成为一个新的堆成为一个新的堆？Data StructureData Structure数据结构(C语言) 排序Page 392022-6-20q 第二个问题解决方法第二个问题解决方法筛选（以筛选（以小顶堆小顶堆为例）为例）v输出堆顶元素输出堆顶元素之后，之后，以堆中最后一个元素替代之以堆中最后一个元素替代之；v然后然后将根结点值与左、右子树的根结点值进行比较将根结点值与左、右子树的根结点值进行比较，并与其中小并与其中小者进行交换者进行交换；v重复上述操作，重复上述操作，直至叶子结点，将得到新的堆，直至叶子结点，将得到新的堆，称这个从堆顶至称这个从堆顶至叶子的调整过程为叶子的调整过程为“筛选筛选”。Data StructureData Structure数据结构(C语言) 排序Page 402022-6-201313272738384949656576765050979797972727383849496565767650501313输出：输出：131327274949383897976565767650501313输出：输出：131397974949383827276565767650501313输出：输出：13,2713,2738384949505027276565767697971313输出：输出：13,2713,2765654949505027273838767697971313输出：输出：13,27,3813,27,38Data StructureData Structure数据结构(C语言) 排序Page 412022-6-2049496565505027273838767697971313输出：输出：13,27,3813,27,3876766565505027273838494997971313输出：输出：13,27,38,4913,27,38,4950506565767627273838494997971313输出：输出：13,27,38,4913,27,38,4997976565767627273838494950501313输出：输出：13,27,38,49,5013,27,38,49,5065659797767627273838494950501313输出：输出：13,27,38,49,5013,27,38,49,5097976565767627273838494950501313输出：输出：13,27,38,49,50,6513,27,38,49,50,65Data StructureData Structure数据结构(C语言) 排序Page 422022-6-2076766565979727273838494950501313输出：输出：13,27,38,49,50,6513,27,38,49,50,6597976565767627273838494950501313输出：输出：13,27,38,49,50,65,7613,27,38,49,50,65,7697976565767627273838494950501313输出：输出：13,27,38,49,50,65,76,9713,27,38,49,50,65,76,97Data StructureData Structure数据结构(C语言) 排序Page 432022-6-20void HeapAdjust (SqList &H, int s, int m)void HeapAdjust (SqList &H, int s, int m)/ / 已知已知H.rs.mH.rs.m中记录的关键字除中记录的关键字除H.rs.keyH.rs.key之外均满足堆的定义，之外均满足堆的定义，/ / 本函数调整本函数调整H.rsH.rs的关键字，使的关键字，使H.rs.mH.rs.m成为一个大顶堆（对其中成为一个大顶堆（对其中/ / 记录的关键字而言）记录的关键字而言）rc = H.rs;rc = H.rs; / / 暂存根结点的记录暂存根结点的记录for(j=2for(j=2* *s;j=m;js;j=m;j* *=2 ) =2 ) / / 沿关键字较大的孩子结点向下筛选沿关键字较大的孩子结点向下筛选if ( jm & LT(H.rj.key,H.rj+1.key ) +j; if ( jm & LT(H.rj.key,H.rj+1.key ) +j; / j / j 为关键字较大的孩子记录的下标为关键字较大的孩子记录的下标if (!LT(rc.key, H.rj.key ) break; if (!LT(rc.key, H.rj.key ) break; / / 不需要调整，跳出循环不需要调整，跳出循环H.rs = H.rj; s = j; H.rs = H.rj; s = j; / / 将大关键字记录往上调将大关键字记录往上调/ for/ forH.rs = rc; H.rs = rc; / / 回移筛选下来的记录回移筛选下来的记录 / HeapAdjust / HeapAdjust若改为小顶堆，若改为小顶堆，该如何修改语句？该如何修改语句？jm & LT(H.rj+1.key,H.rj.key)j0; -i ) for ( i=H.length/2; i0; -i ) / / 将将 H.r1.H.length H.r1.H.length 建成大顶堆建成大顶堆HeapAdjust ( H, i, H.length );HeapAdjust ( H, i, H.length );for ( i=H.length; i1; -i ) for ( i=H.length; i1; -i ) H.r1 H.r1 H.ri; H.ri; / / 将堆顶记录和当前未经排将堆顶记录和当前未经排/ / 序的子序列序的子序列H.r1.iH.r1.i中最中最/ / 后一个记录互相交换后一个记录互相交换HeapAdjust(H, 1, i-1);HeapAdjust(H, 1, i-1);/ / 将将H.r1.i-1H.r1.i-1重新调整为重新调整为/ / 大顶堆大顶堆/for/for / HeapSort / HeapSortData StructureData Structure数据结构(C语言) 排序Page 472022-6-20q 算法评价算法评价v时间复杂度时间复杂度：最坏情况下：最坏情况下T(n)=O(nlogn)T(n)=O(nlogn)筛选算法：最多从第筛选算法：最多从第1 1层筛到最底层，为完全二叉树的深度层筛到最底层，为完全二叉树的深度 loglog2 2n n +1;+1;初始建堆：调用筛选算法初始建堆：调用筛选算法 n/2n/2 次；次；重建堆：调用筛选算法重建堆：调用筛选算法 n-1 n-1 次。次。v空间复杂度空间复杂度：S(n)=O(1)S(n)=O(1)v记录较少时，不提倡使用记录较少时，不提倡使用。v不稳定不稳定的排序方法的排序方法Data StructureData Structure数据结构(C语言) 排序Page 482022-6-20q 归并归并v将两个或两个以上的有序表组合成一个新的有序表将两个或两个以上的有序表组合成一个新的有序表。q 2-2-路归并排序路归并排序v排序过程排序过程设初始序列含有设初始序列含有n n个记录，则可看成个记录，则可看成n n个有序的子序列，每个个有序的子序列，每个子序列长度为子序列长度为1 1；两两合并两两合并，得到，得到 n/2n/2 个长度为个长度为2 2或或1 1的有序子序列；的有序子序列；再两两合并，再两两合并，如此重复，如此重复，直至得到一个长度为直至得到一个长度为n n的有序序的有序序列为止列为止。Data StructureData Structure数据结构(C语言) 排序Page 492022-6-20初始关键字：初始关键字： 49 38 65 97 76 13 2749 38 65 97 76 13 27一趟归并后：一趟归并后： 38 49 65 97 13 76 2738 49 65 97 13 76 27二趟归并后：二趟归并后： 38 49 65 97 13 27 7638 49 65 97 13 27 76三趟归并后：三趟归并后： 13 27 38 49 65 76 9713 27 38 49 65 76 97Data StructureData Structure数据结构(C语言) 排序Page 502022-6-20void Merge (RcdType SR, RcdType &TR, int i, int m, int n)void Merge (RcdType SR, RcdType &TR, int i, int m, int n)/ / 将有序的将有序的SRi.mSRi.m和和SRm+1.nSRm+1.n归并为有序的归并为有序的TRi.nTRi.nfor (j=m+1, k=i; i=m & j=n; +k) for (j=m+1, k=i; i=m & j=n; +k) / / 将将SRSR中记录按关键字从小到大地复制到中记录按关键字从小到大地复制到TRTR中中if ( LQ(SRi.key, SRj.key) TRk = SRi+;if ( LQ(SRi.key, SRj.key) TRk = SRi+;else TRk = SRj+;else TRk = SRj+; while (i=m) TRk+ = SRi+; while (i=m) TRk+ = SRi+; / / 将剩余的将剩余的 SRi.m SRi.m 复制到复制到TRTRwhile (j=n) TRk+ = SRj+; while (j=n) TRk+ = SRj+; / / 将剩余的将剩余的 SRj.n SRj.n 复制到复制到TRTR / Merge / MergeData StructureData Structure数据结构(C语言) 排序Page 512022-6-20q 算法评价算法评价v时间复杂度：时间复杂度：T(n)=O(nlog2n)T(n)=O(nlog2n)每趟两两归并需调用每趟两两归并需调用mergemerge算法算法 n/2hn/2h 次（次（h h为有序段长度）；为有序段长度）；整个归并要进行整个归并要进行 loglog2 2n n 趟。趟。v空间复杂度：空间复杂度：S(n)=O(n)S(n)=O(n)Data StructureData Structure数据结构(C语言) 排序Page 522022-6-2010.6.1 10.6.1 多关键字的排序多关键字的排序q 多关键字排序多关键字排序例例 对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序：两个关键字：花色（两个关键字：花色（ ） 面值（面值（23A23A） 并且并且“花色花色”地位高于地位高于“面值面值” 2 3 A 2 3 A 2 3 A 2 3 AData StructureData Structure数据结构(C语言) 排序Page 532022-6-20v多关键字排序方法多关键字排序方法最高位优先法最高位优先法（MSD)MSD)： 先对最高位关键字先对最高位关键字k1k1排序排序，将序列分成若干子序列将序列分成若干子序列，每，每个子序列有相同的个子序列有相同的k1k1值；值；然后然后让每个子序列让每个子序列对次关键字对次关键字k2k2（如面值）排序（如面值）排序，又分成若干更小的子序列；依次重复，又分成若干更小的子序列；依次重复，直直至就每个子序列对最低位关键字至就每个子序列对最低位关键字kdkd排序排序；最后将所有子序列；最后将所有子序列依次连接在一起成为一个有序序列。依次连接在一起成为一个有序序列。最低位优先法最低位优先法(LS