第10章排序(简)详解课件

数据结构课程的内容数据结构课程的内容第十章排序第第1010章章 排序排序n 学习要点学习要点 n 理解和熟悉各种排序的基本思想和过程理解和熟悉各种排序的基本思想和过程n 掌掌握握各各种种排排序序算算法法的的时时间间复复杂杂度度的的分分析析方法和结论方法和结论n 要求能根据各种排序方法的优缺点及不要求能根据各种排序方法的优缺点及不同场合选择合适的排序方法同场合选择合适的排序方法 第十章排序n 本章内容本章内容10.1 基本概念基本概念10.2 插入排序插入排序（直接插入、折半插入、表插入排（直接插入、折半插入、表插入排序、希尔排序）序、希尔排序）10.3 快速排序快速排序（起泡排序、快速排序）（起泡排序、快速排序）10.4 选择排序选择排序（简单选择排序、树形选择排序、（简单选择排序、树形选择排序、堆排序）堆排序）10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较讨论各种内部排序方法的比较讨论第十章排序10.1 10.1 基本概念基本概念F排排序序（Sorting）:是是将将数数据据元元素素（记记录录）的的一一个个任任意意序序列，重新排列成一个按关键字有序的序列。列，重新排列成一个按关键字有序的序列。一般情况下，假设含一般情况下，假设含n n个个记录的序列为记录的序列为（R R1 1,R,R2 2,R Rn n）其相应关键字序列为其相应关键字序列为（K K1 1,K,K2 2,K Kn n）需确定一种排列，使关键字满足如下的递增的关系需确定一种排列，使关键字满足如下的递增的关系 K Ki1i1KKi2i2KKinin 则则按按此此关关系系将将记记录录序序列列重重新新排排列列为为(R(Ri1i1,R Ri2i2,R Rinin)的的操操作称之为排序。作称之为排序。第十章排序学号学号姓名姓名年龄年龄性别性别990001王晓佳王晓佳18男男990002林一鹏林一鹏19男男990003谢宁谢宁17女女990004张丽娟张丽娟18女女990005周涛周涛20男男990006李小燕李小燕16女女F关关键键字字是是指指在在一一个个记记录录中中可可以以标标识识该该数数据据项项的的值值，它它是是排序运算的重要依据。排序运算的重要依据。关关键键字字的的选选取取应应根根据据需需要要而而定定，比比如如在在学学生生档档案案表表中中，可可选选择择“学学号号”为为关关键键字字来来识识别别学学生生，也也可可选选择择“年年龄龄”为关键字对学生排序。为关键字对学生排序。9.1 9.1 基本概念基本概念第十章排序按按照照排排序序过过程程中中使使用用内内、外外存存的的不不同同，将将排排序序方方法法分分为为内部排序内部排序和和外部排序外部排序。v内部排序内部排序:如果待排序的记录放在计算机内存中进行排如果待排序的记录放在计算机内存中进行排序，整个排序过程序，整个排序过程不需要访问外存不需要访问外存便能完成，则此类排便能完成，则此类排序称为序称为。内排序分类：内排序分类：插入排序、交换排序、选择排序、归插入排序、交换排序、选择排序、归并排序和基数排序并排序和基数排序。v外部排序外部排序:排序的记录数量比较大，排序期间文件的全排序的记录数量比较大，排序期间文件的全部记录不能同时存放在计算机的内存里，排序过程中需部记录不能同时存放在计算机的内存里，排序过程中需要要不断地进行内存和外存之间的数据交换不断地进行内存和外存之间的数据交换，则此类排序，则此类排序称为称为。F排序的分类排序的分类第十章排序排序的排序的目的目的是什么？是什么？排序算法的好坏如何衡量？排序算法的好坏如何衡量？时时间间效效率率排排序序速速度度（即即排排序序所所花花费费的的全全部部比比较较次数）次数）空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小稳稳定定性性若若两两个个记记录录A A和和B B的的关关键键字字值值相相等等，但但排排序序后后A A、B B的的先先后后次次序序保保持持不不变变，则则称称这这种种排排序序算算法法是稳定的。是稳定的。便于查找！便于查找！10.1 10.1 基本概念基本概念第十章排序在在待待排排序序的的序序列列中中，关关键键字字可可以以是是记记录录的的主主关关键键字字，也可以是记录的次关键字，或是若干数据项的组合。也可以是记录的次关键字，或是若干数据项的组合。v由由主主关关键键字字的的定定义义可可知知，任任何何一一个个记记录录的的无无序序序序列列经经排序后得到的结果是排序后得到的结果是唯一唯一的。的。v若若是是次次关关键键字字，排排序序的的结结果果不不唯唯一一，因因为为等等待待排排序序的的记记录录序序列列中中可可能能存存在在两两个个或或两两个个以以上上关关键键字字相相等等的的记记录录。若若采采用用的的排排序序方方法法使使具具有有相相同同关关键键字字的的记记录录在在排排序序过过程程中中相相对对次次序序不不变变，则则称称此此排排序序方方法法是是稳稳定定的的，否则称为否则称为不稳定不稳定的。的。F排序的稳定性排序的稳定性第十章排序v例如：假定一组记录为（例如：假定一组记录为（15,67,23,15*,40），），其中关键字同为其中关键字同为15的记录有两个。如果一种排的记录有两个。如果一种排序方法使排序后的结果为（序方法使排序后的结果为（15,15*,23,40,67），则称此方法是），则称此方法是稳定的；稳定的；若一种排序方法若一种排序方法使排序后的结果可能为（使排序后的结果可能为（15*,15,23,40,67），则称此方法是，则称此方法是不稳定的。不稳定的。第十章排序排序过程主要是对记录的排序码进行排序过程主要是对记录的排序码进行比较比较和和记录记录的移动的移动过程。因此过程。因此排序的时间复杂性可以用算法执行排序的时间复杂性可以用算法执行中的数据中的数据比较次数及数据移动次数比较次数及数据移动次数来衡量。来衡量。n有序表与无序表有序表与无序表一一组组记记录录按按排排序序关关键键字字的的递递增增或或递递减减次次序序排排列列得得到到的的结结果果被被称称之之为为有有序序表表，相相应应地地，把把排排序序前前的的状状态态称称为为无序表无序表。n正序表与逆序表正序表与逆序表若有序表是按排序码升序排列的，则称为若有序表是按排序码升序排列的，则称为升序表或升序表或正序表正序表，否则称为，否则称为降序表或逆序表降序表或逆序表。F排序的时间复杂性排序的时间复杂性第十章排序#define maxsize 20/*设记录不超过设记录不超过20个个*/typedef int KeyType;/*定义关键字为整数类型定义关键字为整数类型*/typedef structKeyType key;/*关键字域关键字域*/InfoType otherinfo;/*其它数据域其它数据域*/DataType;/*记录类型记录类型*/typedef struct DataType rmaxsize+1;/*r0用作监视哨单元用作监视哨单元*/int length ;/*顺序表长度顺序表长度*/SqList;在在本本章章讨讨论论的的算算法法通通常常采采用用顺顺序序存存储储结结构构，用用一一维维数数组组来实现，且记录按照关键字递增的顺序排列。来实现，且记录按照关键字递增的顺序排列。F存储结构存储结构第十章排序按按排序过程中依据的不同原则对内排方法分类：排序过程中依据的不同原则对内排方法分类：（1）插入排序）插入排序（2）交换排序）交换排序（3）选择排序）选择排序（4）归并排序）归并排序（5）基数排序）基数排序按内排按内排过程中所需的工作量分类：过程中所需的工作量分类：（1）简单的排序方法，其时间复杂度为）简单的排序方法，其时间复杂度为O(nn)（2）先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlogn);（3）基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)排序算法的两种基本操作：排序算法的两种基本操作：（1）比较比较两个关键字的大小；两个关键字的大小；（2）将记录从一个位置）将记录从一个位置移移至另一个位置；至另一个位置；第十章排序10.210.2 插入排序插入排序插入排序的插入排序的基本思想基本思想是：是：插入排序有多种具体实现算法：插入排序有多种具体实现算法：1)直接插入排序直接插入排序 2)折半插入排序折半插入排序 3)希尔排序希尔排序 每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小，插插入到前面入到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上上，直到，直到对象全部插入为止。对象全部插入为止。边插入边排序，保证子序列中随时都是排好序的。边插入边排序，保证子序列中随时都是排好序的。第十章排序n基本思想基本思想 整整个个排排序序过过程程为为n-1n-1趟趟插插入入，即即先先将将序序列列中中第第1 1个个记记录录看看成成是是一一个个有有序序子子序序列列，然然后后从从第第2 2个个记记录录开开始始，逐逐个个进进行行插插入入，直直至至整整个个序序列有序列有序10.2.1 直接插入排序直接插入排序最简单的最简单的最简单的最简单的排序法！排序法！排序法！排序法！在已形成的在已形成的有序表中有序表中顺序查找顺序查找，并在适当，并在适当位置插入，把原来位置上的元素向后位置插入，把原来位置上的元素向后顺移顺移。新元素插入到哪里？新元素插入到哪里？第十章排序关键字序列关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。），请写出直接插入排序的中间过程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】例例1：第十章排序n基本步骤基本步骤n初始状态：初始状态：排序开始之前，整个数组被排序开始之前，整个数组被r r分为两个分为两个部分：有序部分和无序部分。有序部分存放的是已部分：有序部分和无序部分。有序部分存放的是已经排好序的记录；无序部分存放的是尚未排好的记经排好序的记录；无序部分存放的是尚未排好的记录。初始有序部分为录。初始有序部分为r1r1，无序部分为，无序部分为r2r2到到rnrn。n终止状态：终止状态：有序部分存放的是整个数组，无序部分有序部分存放的是整个数组，无序部分为空。为空。n基本操作：基本操作：每次从无序部分取出一个记录（第一个）每次从无序部分取出一个记录（第一个）将其同有序部分中的元素相比较，并按照关键字大将其同有序部分中的元素相比较，并按照关键字大小将其插入到合适位置，使有序部分始终有序。直小将其插入到合适位置，使有序部分始终有序。直至全部记录插入完毕。至全部记录插入完毕。第十章排序直接插入排序直接插入排序算法描述算法描述 初值：待记录放在无序部分的数组初值：待记录放在无序部分的数组r1.n中。中。1)在有序部分中有在有序部分中有1个元素个元素r1，无序部分元素为无序部分元素为r2.n；2)令令i=2，将，将r2作为排序元素；作为排序元素；3)把把r2放到放到r0中，中，r0即即作为暂存单元，又可作为后面循作为暂存单元，又可作为后面循环比较用的环比较用的“监视哨监视哨”；4)取辅助参数取辅助参数j=i-1，其作用是记录其作用是记录待比较元素的下标待比较元素的下标（有序部（有序部分），其位置在分），其位置在i的前面；的前面；5)将将r0的关键字与的关键字与rj的关键字相比较；的关键字相比较；6)若若r0的关键字小于的关键字小于rj的关键字，则的关键字，则rj后移一个位置，即后移一个位置，即j=j-1，然后转向然后转向5。7)若若r0的关键字大于的关键字大于rj的关键字，故的关键字，故r0应放在应放在rj的后面，的后面，即在即在j+1的位置。的位置。8)令令i=i+1，若此时若此时i n，则排序完成，否则转入则排序完成，否则转入4。第十章排序关键字序列关键字序列T=（21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。，请写出直接插入排序的具体实现过程。*表示后一个表示后一个2525i=121254925*16080 1 2 3 4 5 6暂存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：解：假设该序列已存入一维数组假设该序列已存入一维数组r7r7中，将中，将r0r0作为作为监视哨监视哨。则程序执行过程为：。则程序执行过程为：21254925*21初态：初态：164925*25211608完成!例例2：第十章排序10.2.1 直接插入排序直接插入排序n直接插入排序算法直接插入排序算法(P265)void InsertSort(SqList&S)for(i=2;i=S.length;+i)if(S.ri.keyS.ri-1.key)/否则无需到有序序列中比较否则无需到有序序列中比较S.r0=S.ri;for(j=i-1;S.r0.keylow时查找结束，时查找结束，插入的位置插入的位置为为high所指所指位置的后一位置的后一个位置个位置第十章排序讨论：讨论：若记录是链表结构，用直接插入排序行若记录是链表结构，用直接插入排序行否？折半插入排序呢？否？折半插入排序呢？答：答：直接插入不仅可行，而且还无需移动元素，直接插入不仅可行，而且还无需移动元素，时间效率更高！时间效率更高！但链表无法但链表无法“折半查找折半查找”！第十章排序10.2.3 希尔排序希尔排序(缩小增量法缩小增量法)n希尔排序方法又称为希尔排序方法又称为“缩小增量缩小增量”排序排序n基本思想基本思想先先将将整整个个待待排排序序的的记记录录序序列列分分割割为为若若干干个个子子序序列列并并分分别别进进行行直直接接插插入入排排序序，待待整整个个序序列列中中的的记记录录“基基本本有有序序”时时，再再对对全全体体记记录录进进行行一一次次直直接接插插入入排排序。序。n技巧：技巧：子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割”，而，而是将是将相隔某个增量相隔某个增量dk的记录组成一个子序列的记录组成一个子序列,让增量让增量dk逐趟缩短（例如依次取逐趟缩短（例如依次取5,3,1），直到），直到dk1为止。为止。n优点：优点：让关键字值小的元素能让关键字值小的元素能跳跃式地跳跃式地前移，而不前移，而不是一步一步的前移，且序列若基本有序时，再用直是一步一步的前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。接插入排序处理，时间效率会高很多。38例：例：关键字序列关键字序列 T=(49，38，65，97,76,13,27,49*，55,04），），请写出希尔排序的具体实现过程。请写出希尔排序的具体实现过程。0123456789104938659776132749*5504初态：初态：第第1趟趟(dk=5)第第2趟趟(dk=3)第第3趟趟(dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449*76 97 算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排的值较大，子序列中的对象较少，排序速度较快；随着排序进展，序速度较快；随着排序进展，dk 值逐渐变小，子序值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。多数对象已基本有序，所以排序速度仍然很快。riri第十章排序n排序过程：排序过程：先取一个正整数先取一个正整数d1nd1n，把所有相隔把所有相隔d1d1的记录放一组，组内进行直接插入排序；然后取的记录放一组，组内进行直接插入排序；然后取d2d1d2r2.key，则交换；然后则交换；然后比较第二个记录与第三个记录；依次类推，直至第比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第个记录和第n个记录比较为止个记录比较为止第一趟冒泡排序第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上结果关键字最大的记录被安置在最后一个记录上；n 对前对前n-1个记录进行第二趟冒泡排序，结果使关键个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第字次大的记录被安置在第n-1个记录位置个记录位置；n 重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有进在一趟排序过程中没有进行过交换记录的操作行过交换记录的操作”为止为止。排序过程排序过程第十章排序例例4938659776132730 初初始始关关键键字字3849657613273097 第第一一趟趟38496513273076 第第二二趟趟384913273065 第第三三趟趟3813273049 第第四四趟趟13273038 第第五五趟趟132730 第第六六趟趟38497697139727973097137676762730136527653065131349493049273827383038第十章排序n冒泡排序算法冒泡排序算法void BubbleSort(SqList&S)for(i=1;i=n-1;i+)/*做做n-1趟排序趟排序*/noswap=true;/*置未交换的标志置未交换的标志*/for(j=1;jS.rj+1.key)/*交换记录交换记录*/temp=S.rj+1;S.rj+1=S.rj;S.rj=temp;noswap=false;if(noswap)return;/*本趟排序未发生交换本趟排序未发生交换,终止算法终止算法*/第十章排序n起泡排序算法的性能分析起泡排序算法的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间.(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;比较和移动记录的次数与关键字的初始序列有关比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序（待排序序列关键字正序排序（最好最好）:关键字比较次数关键字比较次数:n-1 移动记录的次数移动记录的次数:0(2)待排序序列关键字逆序排序（待排序序列关键字逆序排序（最坏最坏）:关键字比较次数关键字比较次数:(n-1)+(n-2)+1=n(n-1)/2 移动记录的次数移动记录的次数:3n(n-1)/2(3)待排序序列关键字随机排序（待排序序列关键字随机排序（平均平均）:关键字比较次数关键字比较次数:(n-1)n/4 移动记录的次数移动记录的次数:3n(n-1)/4起泡排序算法的起泡排序算法的时间复杂度为时间复杂度为O(nn)第十章排序改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在起泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。交换排序交换排序交换排序交换排序减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面10.3.2 快速排序快速排序第十章排序10.3.2 快速排序快速排序从待排序列中任取一个元素从待排序列中任取一个元素 (例如取第一个例如取第一个)作为作为中心中心，所有比它小的元素一律前放，所有比它，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对大的元素一律后放，形成左右两个子表；然后再对各子表重新选择各子表重新选择中心元素中心元素并依此规则调整，直到每并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。个子表的元素只剩一个。此时便为有序序列了。基本思想：基本思想：优点：优点：因为每趟可以确定不止一个元素的位置，而因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！且呈指数增加，所以特别快！前提：前提：顺序存储结构顺序存储结构 第十章排序选择选择枢轴枢轴的方法：的方法：1.使用第一个记录的关键码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；到第一个记录的位置；4.随机选取轴值。随机选取轴值。关键问题关键问题：如何选择轴值？如何选择轴值？选取不同选取不同枢轴枢轴的后果：的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。第十章排序v排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.keyl初始时令i=s,j=tl首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换l再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换l重复上述两步，直至i=j为止，便是枢轴记录rs的最终位置。l再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止第十章排序例例初始关键字：初始关键字：49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：分别进行快速排序：(13)27 (38)49 (50 65)76 (97)快速排序结束：快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij第十章排序Low=high=3Low=high=3Low=high=3Low=high=3，本本本本趟趟趟趟停停停停止止止止，将将将将枢枢枢枢轴轴轴轴定定定定位位位位并并并并返返返返回位置信息回位置信息回位置信息回位置信息关键字序列关键字序列 T=(21，25，49，25*，16，08），），请写出快速排序算法的一趟实现过程。请写出快速排序算法的一趟实现过程。ri0123456初态初态21254925*1608第第1趟趟highhighlowlow210825164925*321r0=r0=212108251649(08，16）21 （25*，49，25 ）25252525*跑到了前面，跑到了前面，跑到了前面，跑到了前面，不稳定！不稳定！不稳定！不稳定！例：例：lowlowhighhighhighhighlowlowhighhigh例例3：以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法）为例，写出执行快速算法的的各趟各趟排序结束时，关键字序列的状态。排序结束时，关键字序列的状态。原始序列：原始序列：256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438076076，129129，256256，751751，937937，863863，742742，694694，301301，438438256256076076301301129129751751256256076076，129129，256256，438438，301301，694694，742742，694694，863863，937937751751076076，129129，256256，438438，301301，694694，742742，751751，863863，937937076076，129129，256256，301301，301301，694694，742742，751751，863863，937937438438076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第十章排序例：例：38,27,55,50,13,49,65的快速排序递归树如下：的快速排序递归树如下：38135055496527快速排序的递归执行过程可以用快速排序的递归执行过程可以用递归树递归树描述。描述。n 算法评价算法评价 从快速排序算法的递归树可知从快速排序算法的递归树可知，快速排序的趟数取决于递，快速排序的趟数取决于递归树的深度。归树的深度。如果每次划分对一个对象定位后，该对象的左侧子序列与如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。列进行排序，这是最理想的情况。第十章排序n算法评价算法评价n时间复杂度时间复杂度n最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)n最坏情况（每次总是选到最小或最大元最坏情况（每次总是选到最小或最大元素作枢轴）素作枢轴）T(n)=O(n)n平均时间复杂度为平均时间复杂度为O（nlog2n）n空间复杂度：空间复杂度：需栈空间以实现递归需栈空间以实现递归n最坏情况：最坏情况：S(n)=O(n)n一般情况：一般情况：S(n)=O(log2n)n稳定性：稳定性：快速排序是不稳定排序。快速排序是不稳定排序。目前目前同数量级同数量级O O（nlognlog2n n）中最快的内部排序方法）中最快的内部排序方法第十章排序10.4 10.4 选择排序选择排序n基本思想基本思想在待排记录中依次选择在待排记录中依次选择关键字最小关键字最小的记录的记录添加到有序序列中，添加到有序序列中，逐渐缩小范逐渐缩小范围直至全部记录选择完毕。围直至全部记录选择完毕。选择排序的主要算法有：选择排序的主要算法有：1)简单选择排序简单选择排序 2)堆堆排序排序第十章排序10.4.1简单选择排序（直接选择排序）简单选择排序（直接选择排序）n基本思想基本思想每每一一趟趟从从待待排排的的无无序序区区中中选选出出关关键键字字最最小小的的记记录录，顺顺序放在已排好序的子序列的序放在已排好序的子序列的最后最后，直至记录全部排完。，直至记录全部排完。n具体步骤具体步骤首先在无序区首先在无序区R1.n中选出关键字最小的记录，将它中选出关键字最小的记录，将它与与R1交换；交换；然后在无序区然后在无序区R2.n中选出关键字最小的记录，将它中选出关键字最小的记录，将它与与R2交换。重复此过程。交换。重复此过程。当第当第i趟排序时趟排序时R1.i-1已是有序区，从无序区已是有序区，从无序区Ri.n中选出关键字最小的记录中选出关键字最小的记录Rk，将它与将它与Ri交换，使交换，使R1.i为有序区。为有序区。可见，整个过程需要可见，整个过程需要n-1趟趟排序。排序。例例初始：初始：49 38 65 97 76 13 27 minjjjjjjminmini=11349一趟：一趟：13 38 65 97 76 49 27 i=2minminjjjjj2738二趟：二趟：13 27 65 97 76 49 38 三趟：三趟：13 27 38 97 76 49 65 四趟：四趟：13 27 38 49 76 97 65 五趟：五趟：13 27 38 49 65 97 76 六趟：六趟：13 27 38 49 65 76 97 排序结束：排序结束：13 27 38 49 65 76 97第十章排序简单选择排序的算法设计简单选择排序的算法设计:(1)(1)需进行需进行n-1n-1趟选择操作趟选择操作;(2)(2)第第i i趟选择操作为趟选择操作为:通过通过n-in-i次关键字间比较次关键字间比较,从从n-i+1n-i+1个记录中选出关键字最小的记录个记录中选出关键字最小的记录,并和并和第第i i个记录交换个记录交换;第十章排序n简单选择排序算法简单选择排序算法void SelectSort(SqList&S)/*对对r1.n进行简单选择排序进行简单选择排序*/for(i=1;iS.length;+i)/*做做n-1趟排序趟排序*/min=i;/*min记录最小元素下标记录最小元素下标*/for(j=i+1;j=S.length;j+)/*在当前无序区在当前无序区S.ri.n中选关键字最小的记录中选关键字最小的记录S.rmin*/if(S.rj.keyS.rmin.key)min=j;if(min!=i)/*交换交换Ri和和Rmin*/temp=S.ri;S.ri=S.rmin;S.rmin=temp;第十章排序简单选择排序算法分析简单选择排序算法分析q时间复杂度时间复杂度v记录移动次数记录移动次数最好情况（正序）：最好情况（正序）：0最坏情况最坏情况（逆序）（逆序）：3(n-1)平均平均:0+3(n-1)/2=3(n-1)/2v比较次数：比较次数：整整个个排排序序过过程程共共需需n-1趟趟比比较较，在在第第i趟趟中中需需比比较较n-i次次，故总比较次数为：故总比较次数为：v故直接选择排序的故直接选择排序的时间复杂度时间复杂度为为O（n2）。p空间复杂度空间复杂度O（1）p稳定性稳定性不稳定不稳定的排序方法的排序方法第十章排序10.4.2 堆排序堆排序n堆的概念堆的概念设有设有n个元素的序列个元素的序列 k1，k2，kn，当且仅当当且仅当满足下述关系之一时，称之为堆。满足下述关系之一时，称之为堆。KiK2i和和KiK2i+1 或或KiK2i和和KiK2i+1其中，其中，K1必是数列中的最大值或最小值，可分别必是数列中的最大值或最小值，可分别成为大根堆（二叉树的所有根结点值大于或等于左成为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）和右孩子的值）和小根堆小根堆（二叉树的所有根结点值小（二叉树的所有根结点值小于或等于左右孩子的值）于或等于左右孩子的值）。下图是两种堆的示例。下图是两种堆的示例。第十章排序2412473885913053859136 4724165330大根大根堆堆小根堆小根堆10.4.2 堆排序堆排序1616 9 9 8 81010 6 6 2 2 1111 1 1 5 5 4 4不是不是堆堆第十章排序n基本思想基本思想 堆堆排排序序（HeapSort）是是对对选选择择排排序序的的一一种种改改进进方方法法，属属于于树树形形排排序序法法。在在排排序序过过程程中中，将将R1.n看看成成是是一一棵棵完完全全二二叉叉树树的的顺顺序序存存储储结结构构，利利用用双双亲亲结结点点和和孩孩子子结结点点间间的的内内在在关关系系来来选选择择关关键字最小的记录。键字最小的记录。堆排序堆排序若在输出堆顶元素之后，使得剩余若在输出堆顶元素之后，使得剩余n-1个个元素的序列重又建成一个堆，则得到元素的序列重又建成一个堆，则得到n个元素中的个元素中的次小值。如此反复执行，便能得到一个有序序列，次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序这个过程称之为堆排序。10.4.2 堆排序堆排序第十章排序n排序过程（小根堆）排序过程（小根堆）以初始关键字序列，以初始关键字序列，建立堆建立堆；输出堆顶输出堆顶最小元素；最小元素；调整调整余下的元素，使其成为一个新堆；余下的元素，使其成为一个新堆；重复重复,n,n 次，得到一个有序序列。次，得到一个有序序列。n实现堆排序关键要解决实现堆排序关键要解决和和两个问题：两个问题：一、如何由一个无序序列建成一个堆一、如何由一个无序序列建成一个堆?二二、输输出出堆堆顶顶元元素素后后，如如何何调调整整余余下下的的元元素素成成为为一一个新堆个新堆?第十章排序10.4.2 堆排序堆排序问题二的解决方案：问题二的解决方案：v输出堆顶元素后，堆的重建：输出堆顶元素后，堆的重建：解决这一问题可采用解决这一问题可采用“筛选法筛选法”。筛选法的基本。筛选法的基本思想为：思想为：J设有设有n n个元素的堆，个元素的堆，输出堆顶输出堆顶元素后，剩下元素后，剩下n-1n-1个元素。个元素。J将将堆底堆底（堆中最后一个元素）（堆中最后一个元素）推向堆顶推向堆顶。J然后将然后将根结点值根结点值与左、右子树的根结点值进行比较，并与左、右子树的根结点值进行比较，并将它与其中将它与其中小者小者进行进行交换交换；J重复上述操作，直至叶子结点，将得到新的堆，称重复上述操作，直至叶子结点，将得到新的堆，称这个这个从堆顶至叶子的调整过程为从堆顶至叶子的调整过程为“筛选筛选”。第十章排序2412473885913053249147388530539124473885305330244738859153a.输出堆顶输出堆顶12，将堆低，将堆低91送入堆顶送入堆顶b.堆被破坏，根结点与右孩子交换堆被破坏，根结点与右孩子交换c.右子树不满足堆，其根与左孩子交换右子树不满足堆，其根与左孩子交换d.堆已重建成堆已重建成堆重建示例堆重建示例第十章排序初始建堆初始建堆问题一的解决方案：问题一的解决方案：vn个记录初始建堆的过程个记录初始建堆的过程：对初始序列建堆的过程，就是一个反复进行对初始序列建堆的过程，就是一个反复进行“筛选筛选”的过程。的过程。n（1）将此无序序列看成是一个完全二叉树，则）将此无序序列看成是一个完全二叉树，则最后一个非最后一个非叶子结点叶子结点是第是第|n/2|个元素。个元素。n（2）依次对第）依次对第|n/2|，|n/2|-1,|n/2|-2,1个元素进行筛选。个元素进行筛选。例例 含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）4950653827137697初始完全二初始完全二叉树叉树下面对第下面对第4、3、2、1个元素进行个元素进行筛选，使其成为一个小根堆筛选，使其成为一个小根堆第十章排序例例 含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 5050971365381327494913382765765097对对9797进进行筛选行筛选对对6565进进行筛选行筛选对对3838进进行筛选行筛选对对4949进进行筛选行筛选最后得最后得到的小到的小根堆根堆第十章排序例例:对关关键字序列字序列49,38,65,97,76,13,27,50进行堆排序行堆排序13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 38堆排序示例堆排序示例4965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 657665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 97第十章排序堆排序算法分析堆排序算法分析n算法评价算法评价n时间复杂度：时间复杂度：最坏情况下最坏情况下T(n)=O(nlog2n)n空间复杂度：空间复杂度：S(n)=O(1)n堆排序的性能堆排序的性能堆排序是堆排序是不稳定不稳定的；的；堆排序适用于堆排序适用于n 较大较大的情况的情况第十章排序10.5 10.5 归并排序法归并排序法n归并排序归并排序 所所谓谓归归并并就就是是将将两两个个或或两两个个以以上上的的有有序序表表合合并并成成一个有序表。一个有序表。n归归并并的的基基本本操操作作是是将将两两个个位位置置相相邻邻的的有有序序记记录录子子序序列列Ri.m和和Rm+1.n归归并并成成一一个个有有序序记记录录序序列列Ri.n。n基本思想基本思想将记录序列将记录序列R1.n看成是看成是n个长度为个长度为1的子序列，的子序列，然后两两归并，得到然后两两归并，得到n/2n/2个长度为个长度为2或或1的有序子的有序子序列。再两两归并，重复此过程，直至得到一个长序列。再两两归并，重复此过程，直至得到一个长度为度为n的有序序列为止。这种方法的有序序列为止。这种方法每次都将两个序列每次都将两个序列合并成一个序列合并成一个序列，故称为，故称为2路归并排序路归并排序。第十章排序例例初始关键字：初始关键字：49 38 65 97 76 13 27一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 9710.5 10.5 归并排序法归并排序法第十章排序n要解决的关键问题：要解决的关键问题：如何将两个有序表归并为一个有序表？如何将两个有序表归并为一个有序表？n其基本思想是：其基本思想是：设两个有序表设两个有序表A和和B的对象个数的对象个数(表长表长)分别为分别为 al 和和 bl，变量，变量 i 和和 j 分别是表分别是表A和表和表B的当前检测的当前检测指针。设表指针。设表C是归并后的新有序表，变量是归并后的新有序表，变量 k 是它是它的当前存放指针。的当前存放指针。第十章排序l m m+l m m+1 1 n ninitListinitListi ji jl nl nk kmergeListmergeListn当当 i 和和 j 都在两个表的表长内变化时，根据都在两个表的表长内变化时，根据Ai与与Bj的关键字的大小，依次把关键字小的对象排放的关键字的大小，依次把关键字小的对象排放到新表到新表Ck中；中；n当当 i 与与 j 中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一 个表中个表中的剩余部分照抄到新表的剩余部分照抄到新表Ck中。中。C表表A表表B表表将下面两个将下面两个已排序的顺序表合并成一个有序表。顺序已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。其中任一表都移入另一表为止。4913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 467第十章排序4913659776780ABCijk70 1 2 3 4 5 6 7 0 1 2 3 468第十章排序4913659776780ABCijk70 1 2 3 4 5 6 7 0 1 2 3 469第十章排序4913659776780ABCijk7130 1 2 3 4 5 6 7 0 1 2 3 470第十章排序4913659776780ABCijk713490 1 2 3 4 5 6 7 0 1 2 3 471第十章排序4913659776780ABCijk713490 1 2 3 4 5 6 7 0 1 2 3 472第十章排序4913659776780ABCijk71349650 1 2 3 4 5 6 7 0 1 2 3 473第十章排序4913659776780ABCijk71349650 1 2 3 4 5 6 7 0 1 2 3 474第十章排序4913659776780ABCijk7134965760 1 2 3 4 5 6 7 0 1 2 3 475第十章排序4913659776780ABCijk7134965760 1 2 3 4 5 6 7 0 1 2 3 476第十章排序4913659776780ABCijk713496576800 1 2 3 4 5 6 7 0 1 2 3 477第十章排序4913659776780ABCijk713496576800 1 2 3 4 5 6 7 0 1 2 3 478第十章排序4913659776780ABCijk71349657680至此至此 B 表的元素表的元素都已移入都已移入 C 表，表，只需将只需将 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。0 1 2 3 4 5 6 7 0 1 2 3 479第十章排序0 1 2 3 44913659776780ABCijk71349657680至此至此 B 表的元素表的元素都已移入都已移入 C 表，表，只需将只需将 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。970 1 2 3 4 5 6 7 80第十章排序n归并排序算法归并排序算法void Merge(DataType S,DataType T,int i,int m,int n)/*将有序的将有序的Si.m和和Sm+1.n归并为有序的归并为有序的Ti.n*/for(j=m+1,k=i;i=m&j=n;+k)/*将将S中记录由小到大地并入中记录由小到大地并入T */if(Si.key=Sj.key)Tk=Si+;else Tk=Sj+;while(i=m)Tk+=Si+;/*将剩余的将剩余的Si.m复制到复制到T*/while(j=n)Tk+=Sj+;/*将剩余的将剩余的Sj.n复制到复制到T */第十章排序10.5 10.5 归并排序法归并排序法n归并排序归并排序归归并并排排序序在在算算法法实实现现时时，可可先先将将待待排排序序列列Rs.t分分成成两两块块：Rs.（s+t）/2和和R（s+t）/2+1.t。分分别别对对两两个个子子序序列列进进行行归归并并排排序序，最最后后对对记记录录实实施施归归并并操操作作，使使Rs.t成为有序序列。成为有序序列。void Msort(DataType S,DataType T1,int s,int t)if(s=t)T1s=Ss;elsem=(s+t)/2;/将将Ss.t平分为平分为Ss.m和和Sm+1.tMsort(S,T2,s,m);Msort(S,T2,m+1,t);Merge(T2,T1,s,m,t);第十章排序10.5 10.5 归并排序法归并排序法n算法评价算法评价n一趟归并操作是将一趟归并操作是将r1rn中相邻的长度为中相邻的长度为h的有序序列进的有序序列进行两两归并，并把结果存放到行两两归并，并把结果存放到r11r1n中，这需要中，这需要O(n)时时间。整个归并排序需要进行间。整个归并排序需要进行 log2n 趟，因此，总的时趟，因此，总的时间代价是间代价是O(nlog2n)。n时间复杂度：时间复杂度：T(n)=O(nlog2n)n空间复杂度：空间复杂度：算法在执行时，需要占用与原始记录序算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此列同样数量的存储空间，因此S(n)=O(n)n它是一个它是一个稳定稳定的排序方法的排序方法第十章排序10.610.6基数排序基数排序多关键字的排序多关键字的排序例例:52张扑克牌的次序为张扑克牌的次序为:2 3 A 2 3 A 2 3 A 2 3 A将整付牌整理成如上次序将整付牌整理成如上次序,可有两种方法可有两种方法:(1)先先对整付牌对整付牌按按“花色花色”分成花色递增的四堆分成花色递增的四堆,然后再分别然后再分别 对每一堆对每一堆按按“面值面值”递增排序递增排序;(2)先对先对整付牌整付牌按按“面值面值”分成面值递增的十三堆分成面值递增的十三堆,然后再然后再 对整付牌对整付牌按按“花色花色”分成按四堆分成按四堆;有两个有两个关键字关键字第十章排序 2 3 A 2 5 3 7 3 8 6 A 6 10 11 9 9 12 4 8 2 3 A 2 3 A 2 3 A(1)按按花花色对色对整付整付牌排牌排序序按面按面值对值对各子各子序列序列排序排序第十章排序(2)2 2 2 2 3 3 3 3 4 4 4 4 A A A A 2 3 A 2 3 A 2 3 A 2 3 A按按面面值值对对整付整付牌排牌排序序按按花花色色对对整付整付牌排牌排序序第十章排序一般情况下，假设一般情况下，假设n个记录的待排序列个记录的待排序列R1，R2，Rn，且每个记录包含，且每个记录包含d个关键字个关键字ki1，ki2，kid 则称则称序列对关键字序列对关键字ki1，ki2，kid有序是指有序是指：对于序列中任意两个记录对于序列中任意两个记录Ri和和Rj（1ijn）都都满足下列有序关系：满足下列有序关系：其中其中k1称为称为最主位关键字最主位关键字，kd称为称为最次位关键字。最次位关键字。第十章排序（1）最高位优先法（）最高位优先法（MSD）：）：先对最高位关键字先对最高位关键字K1 进行排序，进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的将序列分成若干子序列，每个子序列中的记录都具有相同的 K1 值，然后分别就每个子序列对关键字值，然后分别就每个子序列对关键字 K2 进行排序，将子序列分进行排序，将子序列分成若干更小的子序列，依次重复，直到将所有子序列依次联接成若干更小的子序列，依次重复，直到将所有子序列依次联接在一起成为一个有序序列。在一起成为一个有序序列。（2）最低位优先法（）最低位优先法（LSD）：）：先对最低位关键字先对最低位关键字Kd 进行排序，进行排序，然后再对然后再对Kd-1 进行排序进行排序,依次重复依次重复,直到对直到对K1进行排序后，便成进行排序后，便成为一个有序序列。为一个有序序列。vMSD与与LSD不同特点不同特点 按按MSD排序，必须将序列逐层分割成若干子序列，排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序然后对各子序列分别排序 按按LSD排序，不必分成子序列，对每个关键字都是整排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序干次分配与收集实现排序实现多关键字排序的两种方法：实现多关键字排序的两种方法：(3)(3)按按LSDLSD进行排序时，不利用前几节所学的各种通过关键字比较进行排序时，不利用前几节所学的各种通过关键字比较来实现排序的方法，而是通过若于次来实现排序的方法，而是通过若于次“分配分配”和和“收集收集”来实现来实现排序。排序。例：例：对对52张扑克牌进行排序：张扑克牌进行排序：第一次分配：第一次分配：按按面值分配面值分配 3 3 3 3 4 4 4 4 A A A A第一次收集：第一次收集：初始序列：初始序列：6,3,2,A,8，2,2,2,2,3,3,3,3 A,A,A,A 2 2 2 2234A第十章排序第二次分配：第二次分配：按按花色分配花色分配 2,2,2,2,3,3,3,3 A,A,A,A 2 2 2 2 3 3 3 3 A A A A第二次收集：第二次收集：2,3,A,2,3,A,2,3,A,2,3 A排序方法排序方法平均时间平均时间最坏情况最坏情况最好情况最好情况辅助空间辅助空间稳定性稳定性直接插入直接插入排序排序O(n2)O(n2)O(n)O(1)稳定稳定折半插