结束第 1 页结束第 2 页10.1 10.1 概概 述述1、排序定义、排序定义将一个数据元素（或记录）的任意将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫序列，重新排列成一个按关键字有序的序列叫2、排序分类、排序分类l按待排序记录所在位置按待排序记录所在位置内部排序：待排序记录存放在内存内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序l按排序依据原则按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序归并排序：归并排序：2-路归并排序路归并排序基数排序基数排序结束第 3 页l按排序所需工作量按排序所需工作量简单的排序方法：简单的排序方法：T(n)=O(n)先进的排序方法：先进的排序方法：T(n)=O(nlogn) 基数排序：基数排序：T(n)=O(d.n)排序基本操作排序基本操作l比较两个关键字大小比较两个关键字大小l将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置10.1 10.1 概概 述述结束第 4 页10.1 10.1 概概 述述3 3、稳性排序：、稳性排序： 在待排记录在待排记录序列序列中，任何两个关键字相同的记录，用某种排序方法排中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。例例 设设 49,38,65,97,76,13,27,49,38,65,97,76,13,27,4949 是待排序列是待排序列 排序后排序后: :13,27,38,49,13,27,38,49,4949,65,76,97 ,65,76,97 稳定稳定 排序后排序后: :13,27,38,13,27,38,4949,49,65,76,97,49,65,76,97不稳定不稳定稳性排序的应用：稳性排序的应用：例例 股票交易系统股票交易系统 考虑一种股票交易考虑一种股票交易( (清华紫光清华紫光) )） 1 1）顾客输入）顾客输入：股东帐号、股票股东帐号、股票代码、代码、申购价格、数量，股票交易系统申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾将用户申购请求插入申购队列队尾； 2 2）股票交易系统按如下原则交易：）股票交易系统按如下原则交易： A A）申购价高者先成交申购价高者先成交 B B）申购价相同者按申购时间先后顺序成交申购价相同者按申购时间先后顺序成交结束第 5 页10.1 10.1 概概 述述如何实现股票交易系统如何实现股票交易系统 ？申购队列：用线性表表示申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足交易原则交易前：将申购队列按申购价排序，显然为满足交易原则，要求排序方要求排序方法是稳定的法是稳定的申购队列申购队列（09,10),(06,1009,10),(06,10. .5),(033,95),(033,9. .8),(051,10)8),(051,10)排序后：排序后：(06,10.5),(09,10),(051,10),(033,9.8)(06,10.5),(09,10),(051,10),(033,9.8)4 4、 存贮方式存贮方式待排序的记录序列通常有下列三种存贮方法：待排序的记录序列通常有下列三种存贮方法：1 1）顺序表）顺序表2 2）静态链表：在排序过程，只需修改指针，不需要移动记录；静态链表：在排序过程，只需修改指针，不需要移动记录；3 3）待排记录本身有放在连续单元中，同时另建一索引表待排记录本身有放在连续单元中，同时另建一索引表用于存放各用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址地址”，在排序结束后再按地址调整记录的存贮位置，在排序结束后再按地址调整记录的存贮位置结束第 6 页10.1 10.1 概概 述述顺序表类型说明顺序表类型说明# #define MAXSIZE 20 /define MAXSIZE 20 /一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度typedeftypedef intint KeyTypeKeyType; /; /定义关键字类型为整数类型定义关键字类型为整数类型typedeftypedef structstruct KeyTypeKeyType key; / key; /关键字项关键字项InfoTypeInfoType otherinfootherinfo; /; /其它数据项其它数据项 RedTypeRedType; /; /记录类型记录类型typedeftypedef structstruct RedTypeRedType rMAXSIZE+1; /r0 rMAXSIZE+1; /r0闲置或用作哨兵单元闲置或用作哨兵单元IntInt length; / length; /顺序表长度顺序表长度 SqListSqList; /; /顺序表类型顺序表类型结束第 7 页10.2 10.2 插入排序插入排序10.2.2 直接插入排序直接插入排序 基本思想基本思想: 依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。直到全部记录插入完毕；初始时，有序子表中只有一个元素。插入排序的插入排序的关键：如何查找插入位置。直接插入排序（也称为顺序插入关键：如何查找插入位置。直接插入排序（也称为顺序插入排序）：排序）：排序过程：整个排序过程为排序过程：整个排序过程为n-1趟插入，即先将序列中第趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插个记录开始，逐个进行插入，直至整个序列有序入，直至整个序列有序 例：待排记录例：待排记录 49 38 65 97 76 13 27 49 （49）38 65 97 76 13 27 49 （38 49）65 97 76 13 27 49 （38 49 65）97 76 13 27 49 （38 49 65 97） 76 13 27 49 （38 49 65 76 97）13 27 49 （13 38 49 65 76 97）27 49 （13 27 38 49 65 76 97）49 （13 27 38 49 49 65 76 97）一趟一趟直接插入直接插入排序排序结束第 8 页10.2 10.2 插入排序插入排序void InsertSort(SqList &L) /对顺序表对顺序表L作直接插入排序。作直接插入排序。For (i=2; i=L. length; +i) if LT(L.ri.key, L.ri-1.key) /若若L.ri.key L.ri-1.key，需将需将L.ri插入有序子表，插入有序子表， L.r0=L.ri; / L.ri复制为哨兵复制为哨兵 for(j=i-1; LT(L.r(0).key, L.rj.key); -j ) /从后向前查找子表从后向前查找子表 L.rj+1=L.rj; / 若若L.ri.key high，得到插入位置，转得到插入位置，转 lowhigh，m=(low+high)/2； / 取取表表的的中中点点，并并将将表表一一分分为为二二，确确定待插入区间定待插入区间*/ 若若r0.keyrm.key，high=m-1； /插入位置在低半区插入位置在低半区 否则，否则，low=m+1； / 插入位置在高半区插入位置在高半区 转转 high+1即即 为为 待待 插插 入入 位位 置置 ， 从从 j-1到到 high+1的的 记记 录录 ， 逐逐 个个 后后 移移 ，rhigh+1=r0；放置待插入记录。放置待插入记录。结束第 12 页10.2 10.2 插入排序插入排序10.2.2 其他插入排序其他插入排序 1、折半插入排序、折半插入排序/*-折半插入排序折半插入排序-*/void binsertsort(sqlist *l) int i,j,m,low,high; for (i=2;ilength;i+) /* 循环地将循环地将ri插入到有序序列中去插入到有序序列中去 */ l-r0=l-ri; low=1;high=i-1; /* 本次插入初始化本次插入初始化 */ while (lowr0rm) high=m-1; else low=m+1; for (j=i-1;j=high+1;-j) /* 后移填空后移填空 */ l-rj+1=l-rj; l-rhigh+1= l-r0; /* 待插入元存入指定位置待插入元存入指定位置 */ /确定插入位置所进行的折半查找，关键码的比较次数至多为确定插入位置所进行的折半查找，关键码的比较次数至多为 次次。 移移动动记记录录的的次次数数和和直直接接插插入入排排序序相相同同，故时间复杂度仍为故时间复杂度仍为 O(n2)。是一个稳定的排序方法。是一个稳定的排序方法。 log2(n+1)结束第 13 页10.2 10.2 插入排序插入排序10.2.2 其他插入排序其他插入排序2、 2-路插入排序路插入排序 2路路排排序序是是在在折折半半插插入入排排序序的的基基础础上上再再改改进进，目目的的是是减减少少排排序序过过程程中中移动记录的次数。移动记录的次数。 方方法法是是：另另设设一一个个数数组组d ,首首先先将将L.r1赋赋值值给给d1,并并将将d1看看成成是是在在排排序序好好序序列列中中出出于于中中间间位位置置的的记记录录，从从L.r中中第第2个个记记录录起起依依次次插插入入到到d1之之前前或或d1之之后后的的有有序序序序列列中中。在在实实现现算算法法时时，可可以以将将d看看成成是是一一个个循循环环向向量量，并并设设两两个个指指针针first和和final分分别别指指示示排排序序过过程程中中得得到到的的有有序序序序列列的的第第一一个记录和最后一个记录在个记录和最后一个记录在d中的位置。中的位置。3、表插入排序表插入排序 直直接接插插入入排排序序、折折半半插插入入排排序序均均要要大大量量移移动动记记录录，时时间间开开销销大大。若若要不移动记录完成排序，需要改变存储结构，进行表插入排序。要不移动记录完成排序，需要改变存储结构，进行表插入排序。所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态链表来说明。用静态链表来说明。结束第 14 页10.2 10.2 插入排序插入排序10.2.2 其他插入排序其他插入排序#define SIZE 200typedef struct RedType rc； /*元素类型元素类型:记录项记录项*/ int next； /*指针项指针项*/ SLNode； /*表结点类型表结点类型*/typedef struct SLNode rSIZE； /*静态链表静态链表,0号单元为表关结点号单元为表关结点*/ int length； /*表长度表长度*/ SLinkListType； /*静态链表类型静态链表类型*/ 假假设设数数据据元元素素已已存存储储在在链链表表中中，且且0号号单单元元作作为为头头结结点点，不不移移动动记记录录而而只只是是改改变变链链指指针针域域，将将记记录录按按关关键键码码建建为为一一个个有有序序链链表表。首首先先，设设置置空空的的循循环环链链表表，即即头头结结点点指指针针域域置置0，并并在在头头结结点点数数据据域域中中存存放放比比所所有有记记录关键码都大的整数。接下来，逐个结点向链表中插入即可。录关键码都大的整数。接下来，逐个结点向链表中插入即可。结束第 15 页10.2 10.2 插入排序插入排序3、表插入排序表插入排序 假假设设数数据据元元素素已已存存储储在在链链表表中中，且且0号号单单元元作作为为头头结结点点，不不移移动动记记录录而而只只是是改改变变链链指指针针域域，将将记记录录按按关关键键码码建建为为一一个个有有序序链链表表。首首先先，设设置置空空的的循循环环链链表表，即即头头结结点点指指针针域域置置0，并并在在头头结结点点数数据据域域中中存存放放比比所所有有记记录关键码都大的整数。接下来，逐个结点向链表中插入即可。录关键码都大的整数。接下来，逐个结点向链表中插入即可。结束第 16 页10.2 10.2 插入排序插入排序3、表插入排序表插入排序 结束第 17 页10.2 10.2 插入排序插入排序3、表插入排序表插入排序 表表插插入入排排序序得得到到一一个个有有序序的的链链表表，查查找找则则只只能能进进行行顺顺序序查查找找，而而不不能能进行随机查找，如折半查找。为此，还需要对记录进行重排。进行随机查找，如折半查找。为此，还需要对记录进行重排。 重重排排记记录录方方法法：按按链链表表顺顺序序扫扫描描各各结结点点，将将第第i i个个结结点点中中的的数数据据元元素素调调整整到到数数组组的的第第i i个个分分量量数数据据域域。因因为为第第i i个个结结点点可可能能是是数数组组的的第第j j个个分分量量，数数据据元元素素调调整整仅仅需需将将两两个个数数组组分分量量中中数数据据元元素素交交换换即即可可，但但为为了了能能对对所所有数据元素进行正常调整，指针域也需处理。有数据元素进行正常调整，指针域也需处理。结束第 18 页10.2 10.2 插入排序插入排序3、表插入排序表插入排序【算法】【算法】1.1.j=l-r0.next;i=1;/j=l-r0.next;i=1;/指向第一个记录位置，从第一个记录开始调整指向第一个记录位置，从第一个记录开始调整2.2.若若i=l-lengthi=l-length时，调整结束；否则，时，调整结束；否则，a.a.若若i=ji=j，j=l-rj.nextj=l-rj.next；i+i+；转转(2) (2) /数数据据元元素素应应在在这这分分量量中中，不不用调整，处理下一个结点用调整，处理下一个结点b.b.若若jiji，l-l-ri.elemri.eleml-l-rj.elemrj.elem； / /交换数据元素交换数据元素 p=l-rj.nextp=l-rj.next； / / 保存下一个结点地址保存下一个结点地址 l-rj.next=l-i.nextl-rj.next=l-i.next；l-i.next=jl-i.next=j； / / 保持后续链表不被中断保持后续链表不被中断 j=pj=p；i+i+；转转(2) / (2) / 指向下一个处理的结点指向下一个处理的结点c. c. 若若jiji，while(ji) while(jrj.nextj=l-rj.next；/j/j分分量量中中原原记记录录已已移移走走，沿沿j j的指针域找寻原记录的位置转到的指针域找寻原记录的位置转到( (a)a) 结束第 19 页10.2 10.2 插入排序插入排序结束第 20 页10.2 10.2 插入排序插入排序结束第 21 页10.2 插入排序表插入排序位置重排算法：表插入排序位置重排算法：Void B_InsertSort(NodeType R ,int n) /将表插入算法已排序好的静态链表元素位置重排将表插入算法已排序好的静态链表元素位置重排 int I,j,p; DataType s; j=R0.next; I=1;while(In) if(I=j) j=Rj.next;I+; else if(Ij)S=RI;RI=Rj;Rj=S;p=Rj.next;/下一个待重排的元素指针下一个待重排的元素指针 RI.next=j; j=p; I+; else while(jI) j=Rj.next; 结束第 22 页10.2 10.2 插入排序插入排序4 4、希尔排序希尔排序( (缩小增量法缩小增量法shellshells sort)s sort) 希尔排序又称缩小增量排序，是希尔排序又称缩小增量排序，是1959年由年由D.L.Shell提出来的，较前述提出来的，较前述几种插入排序方法有较大的改进。几种插入排序方法有较大的改进。 直直接接插插入入排排序序算算法法简简单单，在在n值值较较小小时时，效效率率比比较较高高，在在n值值很很大大时时，若若序序列列按按关关键键码码基基本本有有序序，效效率率依依然然较较高高，其其时时间间效效率率可可提提高高到到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。希尔排序即是从这两点出发，给出插入排序的改进方法。v排序过程：先取一个正整数din，然后把排序表中的n个记录分为di个组，从第一个记录开始，把相隔di的记录放一组，组内进行直接插入排序；一趟之后，间隔di的记录有序，随着有序性的改善，减少步长di，重复上述分组和排序操作；直至di=1，使得间隔为1的记录有序，也就是整体达到了有序。步长为1时就是直接插入排序。结束第 23 页10.2 10.2 插入排序插入排序取取d3=1三趟分组：三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序三趟排序：4 13 27 38 48 49 55 65 76 97例例 初始：初始： 49 38 65 97 76 13 27 48 55 4一趟排序：一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：二趟排序：13 4 48 38 27 49 55 65 97 76取取d1=5一趟分组：一趟分组：49 38 65 97 76 13 27 48 55 4取取d2=3二趟分组：二趟分组：13 27 48 55 4 49 38 65 97 76结束第 24 页10.2 10.2 插入排序插入排序4 4、希尔排序希尔排序( (缩小增量法缩小增量法shellshells sort)s sort) void ShellInsert(sqlist *L,int dk)/*一趟增量为一趟增量为dk的插入排序，的插入排序，dk为步长因子为步长因子*/ int i,j,k;for(i=dk+1;ilength;i+)if(L-ri.key ri-dk.key) /*小于时，需位置为小于时，需位置为i的元素插入有序表的元素插入有序表*/L-r0=L-ri; /*为统一算法设置监测为统一算法设置监测*/for(j=i-dk;j0&L-r0.key rj.key;j=j-dk)L-rj+dk=L-rj; /*记录后移记录后移*/L-rj+dk=L-r0; /*插入到正确位置插入到正确位置*/结束第 25 页10.2 10.2 插入排序插入排序4 4、希尔排序希尔排序( (缩小增量法缩小增量法shellshells sort)s sort) void ShellSort(sqlist *L,int d,int t)/*按增量序列按增量序列d0，1，t-1对顺序表对顺序表R1n作希尔排序作希尔排序*/int k;for(k=0;kt;k+)ShellInsert(L,dk); /*一趟增量为一趟增量为dk的插入排序的插入排序*/ 希希尔尔排排序序时时效效分分析析很很难难，关关键键码码的的比比较较次次数数与与记记录录移移动动次次数数依依赖赖于于步步长长因因子子序序列列的的选选取取，特特定定情情况况下下可可以以准准确确估估算算出出关关键键码码的的比比较较次次数数和和记记录录的的移移动动次次数数。目目前前还还没没有有人人给给出出选选取取最最好好的的步步长长因因子子序序列列的的方方法法。步步长长因因子子序序列列可可以以有有各各种种取取法法，有有取取奇奇数数的的，也也有有取取质质数数的的，但但需需要要注注意意：步步长长因因子子中中除除1外外没没有有公公因因子子，且且最最后后一一个个步步长长因因子子必必须须为为1。希希尔尔排序方法是一个不稳定的排序方法。排序方法是一个不稳定的排序方法。结束第 26 页10.3 10.3 快速排序快速排序快快速速排排序序（交交换换排排序序）：主主要要是是通通过过两两两两比比较较待待排排记记录录的的关关键键码码，若若发发生与排序要求相逆，则交换之。生与排序要求相逆，则交换之。1、冒泡排序冒泡排序(Bubble Sort) 一趟冒泡排序的过程：设一趟冒泡排序的过程：设1ri+1.key时，时， r0=ri；ri=ri+1；ri+1=r0； 将将ri与与ri+1交换交换 i=i+1； 调整对下两个记录进行两两比较，转调整对下两个记录进行两两比较，转 冒冒泡泡排排序序方方法法：对对n n个个记记录录的的表表，第第一一趟趟冒冒泡泡得得到到一一个个关关键键码码最最大大的的记记录录rnrn，第第二二趟趟冒冒泡泡对对n-1n-1个个记记录录的的表表，再再得得到到一一个个关关键键码码最最大大的的记记录录rn-1rn-1，如此重复，直到如此重复，直到n n个记录按关键码有序的表。个记录按关键码有序的表。 、结束第 27 页10.3 10.3 快速排序快速排序【效率分析】【效率分析】 空间效率：仅用了一个辅助单元。空间效率：仅用了一个辅助单元。 时时间间效效率率：总总共共要要进进行行n-1趟趟冒冒泡泡，对对j个个记记录录的的表表进进行行一一趟趟冒冒泡泡需需要要j-1次关键码比较。次关键码比较。 记记录录移移动动的的次次数数与与比比较较次次数数相相同同数数量量级级，最最坏坏的的情情况况也也发发生生在在排排序序表表逆逆序时。冒泡排序时一个稳定的排序方法。序时。冒泡排序时一个稳定的排序方法。结束第 28 页10.3 10.3 快速排序快速排序2、快速排序、快速排序l基本思想：通过一趟排序，将待排序记录分割成独立的两部分，基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序别对这两部分记录进行排序，以达到整个序列有序l排序过程：对排序过程：对rst中记录进行一趟快速排序，附设两个指针中记录进行一趟快速排序，附设两个指针i和和j，设枢轴记录设枢轴记录rp=rs，x=rp.key初始时令初始时令i=s,j=t首先从首先从j所指位置向前搜索第一个关键字小于所指位置向前搜索第一个关键字小于x的记录，并和的记录，并和rp交换交换再从再从i所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于x的记录，的记录，和和rp交换交换重复上述两步，直至重复上述两步，直至i=j为止为止再分别对两个子序列进行快速排序，直到每个子序列只含有再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止一个记录为止结束第 29 页10.3 10.3 快速排序快速排序例例初始关键字：初始关键字： 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结束第 30 页10.3 10.3 快速排序快速排序void quicksort(sqlist *l,int left,int right ) int i,j,t; if (leftai; do while (ij & taj) j=j-1; /*从右往左找第一个小于等于从右往左找第一个小于等于t的元素的元素*/ if (iai=l-aj;i=i+1; /*将将aj的值填入左端，并设新左端的值填入左端，并设新左端*/ while (il-ai) i=i+1; /*从左往右找第一个大于从左往右找第一个大于t的元素的元素*/ if (iaj=l-ai;j=j-1; /*将将ai的值填入右端，并设新右端的值填入右端，并设新右端*/ while (i!=j); l-ai=t; /*t存入相应位置存入相应位置*/ quicksort( l,left,j-1); /*递归对左段和右段进行快速排序递归对左段和右段进行快速排序*/ quicksort( l,i+1,right); 结束第 31 页10.3 10.3 快速排序快速排序l算法评价算法评价时间复杂度时间复杂度l最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)l最坏情况（每次总是选到最小或最大元素作枢轴）最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n)空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归l最坏情况：最坏情况：S(n)=O(n)l一般情况：一般情况：S(n)=O(log2n)T(n)=O(n)结束第 32 页10.4 10.4 选择排序选择排序 选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从也即第一趟从n n个记录中选取关键码最小的记录作为第一个记录，第二个记录中选取关键码最小的记录作为第一个记录，第二趟从剩下的趟从剩下的n-1n-1个记录中选取关键码最小的记录，作为第个记录中选取关键码最小的记录，作为第2 2个记录，第个记录，第i i走趟在走趟在n-i+1n-i+1个记录中选取关键字最小的记录作为有序序列中第个记录中选取关键字最小的记录作为有序序列中第i i个记个记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。关键码有序的序列。1、简单选择排序、简单选择排序l排序过程排序过程首先通过首先通过n-1次关键字比较，从次关键字比较，从n个记录中找出关键字最小的记录，将它个记录中找出关键字最小的记录，将它与第一个记录交换与第一个记录交换再通过再通过n-2次比较，从剩余的次比较，从剩余的n-1个记录中找出关键字次小的记录，将它个记录中找出关键字次小的记录，将它与第二个记录交换与第二个记录交换重复上述操作，共进行重复上述操作，共进行n-1趟排序后，排序结束趟排序后，排序结束结束第 33 页10.4 10.4 选择排序选择排序例例初始：初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟： 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结束第 34 页10.4 10.4 选择排序选择排序l算法评价算法评价时间复杂度时间复杂度l记录移动次数记录移动次数Y最好情况：最好情况：0Y最坏情况：最坏情况：3(n-1)l比较次数：比较次数：l空间复杂度：空间复杂度：S(n)=O(1)T(n)=O(n)结束第 35 页10.4 10.4 选择排序选择排序2、堆排序、堆排序l堆的定义：堆的定义：n个元素的序列个元素的序列(k1,k2,kn)，当且仅当且仅当满足下列关系时，称之为堆当满足下列关系时，称之为堆或或(i=1,2,. n/2 )ki k2iki k2i+1ki k2iki k2i+1例例 （96，83，27，38，11，9）例例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中元素（完全二叉树的根）必为序列中n个元素的最小值或最大值个元素的最小值或最大值结束第 36 页10.4 10.4 选择排序选择排序l堆排序：将无序序列建成一个堆，得到关键字最小（或最堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到个元素重又建成一个堆，则可得到n个元素的次小值；重个元素的次小值；重复执行，得到一个有序序列，这个过程叫复执行，得到一个有序序列，这个过程叫l堆排序需解决的两个问题：堆排序需解决的两个问题：(1)如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？(2)如何在输出堆顶元素之后，调整剩余元素，使之成如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？为一个新的堆？l第二个问题解决方法第二个问题解决方法筛选筛选方法：输出堆顶元素之后，以堆中最后一个元素替代方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为过程为“筛选筛选”结束第 37 页10.4 10.4 选择排序选择排序例例13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 38结束第 38 页10.4 10.4 选择排序选择排序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 65结束第 39 页10.4 10.4 选择排序选择排序7665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 97结束第 40 页10.4 10.4 选择排序选择排序l第一个问题解决方法第一个问题解决方法方法：从无序序列的第方法：从无序序列的第 n/2 个元素（即此无序序列对应的完全二叉树的个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选最后一个非终端结点）起，至第一个元素止，进行反复筛选例例 含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097结束第 41 页l【算法算法10.10】lvoid HeapAdjust(Sqlist *h，int s，int m)l/*rsm中的记录关键码除中的记录关键码除rs外均满足堆的定义，本函数将对第外均满足堆的定义，本函数将对第s个结点为根的个结点为根的l 子子 树筛选，使其成为大顶堆树筛选，使其成为大顶堆*/lrc=h-rs；lfor(j=2*s；j=m；j=j*2) /* 沿关键码较大的子女结点向下筛选沿关键码较大的子女结点向下筛选 */lif(jrj.keyrj+1.key)lj=j+1； /* 为关键码较大的元素下标为关键码较大的元素下标*/lif(rc.key=h-rj.key) break； /* rc应插入在位置应插入在位置s上上*/lh-rs=h-rj； s=j； /* 使使s结点满足堆定义结点满足堆定义 */llh-rs=rc； /* 插入插入 */llvoid HeapSort(Sqlist *h)lfor(i=h-length/2；i0；i- -) /* 将将r1.length建成堆建成堆 */lHeapAdjust(h，i，h-length)；lfor(i=h-length；i1；i-)lh-r1h-ri； /* 堆顶与堆低元素交换堆顶与堆低元素交换 */lHeapAdjust(h，1，i-1)； /*将将r1.i-1重新调整为堆重新调整为堆*/ll结束第 42 页10.4 10.4 选择排序选择排序l堆排序算法评价堆排序算法评价时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：空间复杂度：S(n)=O(1)结束第 43 页10.5 10.5 归并排序归并排序l 归并排序归并排序归并归并将两个或两个以上的有序表组合成一个将两个或两个以上的有序表组合成一个新的有序表，叫新的有序表，叫2-路归并排序路归并排序l排序过程排序过程设初始序列含有设初始序列含有n个记录，则可看成个记录，则可看成n个有序的子个有序的子序列，每个子序列长度为序列，每个子序列长度为1两两合并，得到两两合并，得到 n/2 个长度为个长度为2或或1的有序子序列的有序子序列再两两合并，再两两合并，如此重复，直至得到一个长度为如此重复，直至得到一个长度为n的有序序列为止的有序序列为止结束第 44 页10.5 10.5 归并排序归并排序例例初始关键字：初始关键字： 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 97结束第 45 页10.5 10.5 归并排序归并排序/*-一次归并一次归并-*/void merge(sqlist *l1,sqlist *l2,int u,int m,int v) int i,j,k,t; i=u; j=m+1; k=u; /*l1u.m l1m+1.v进行归并进行归并*/ while (i=m & jaiaj ) l2-ak=l1-ai; i+; else l2-ak=l1-aj; j+; k+; if (im) for (t=j;tak+t-j=l1-at; else for (t=i;tak+t-i=l1-at; 结束第 46 页10.5 10.5 归并排序归并排序/*-/*-一趟归并一趟归并-*/-*/ void void mergepass(sqlistmergepass(sqlist *l1,sqlist *l2,int *l1,sqlist *l2,int n,intn,int lenlen) ) intint i,t; i,t; i=1; i=1; while (i=n-2*len+1) while (i=n-2*len+1) /归并长度为归并长度为lenlen的两个相邻子文件的两个相邻子文件 merge(l1,l2,i,i+len-1,i+2*len-1); merge(l1,l2,i,i+len-1,i+2*len-1); i=i+2* i=i+2*lenlen; ; / / 跳到下两个需要归并的表跳到下两个需要归并的表 if (i+len-1n) merge(l1,l2,i,i+len-1,n); if (i+len-1n) merge(l1,l2,i,i+len-1,n); else for(t=i;t=n;t+) else for(t=i;tat=l1-at;l2-at=l1-at; 尚有两个子尚有两个子文件，其中文件，其中后一个长度后一个长度小于小于lengthlength剩余一个子剩余一个子文件轮空，文件轮空，无须归并无须归并结束第 47 页结束第 48 页10.6 10.6 基数排序基数排序 基基数数排排序序是是一一种种借借助助于于多多关关键键码码排排序序的的思思想想，是是将单关键码按基数分成将单关键码按基数分成“多关键码多关键码”进行排序的方法进行排序的方法例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序： 2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（两个关键字：花色（ ） 面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”结束第 49 页l多关键字排序方法多关键字排序方法最高位优先法（最高位优先法（MSD:most significant digit first)：先对最高位关键字先对最高位关键字k1（如花色）排序，如花色）排序，将序列分成若干子序列，每个子序列有相同的将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字值；然后让每个子序列对次关键字k2（如如面值）排序，又分成若干更小的子序列；依次面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为排序；最后将所有子序列依次连接在一起成为一个有序序列一个有序序列结束第 50 页10.6 10.6 基数排序基数排序最低位优先法最低位优先法(LSD: least significant digit first)：从最低位关键字从最低位关键字kd起进行排序，然后再起进行排序，然后再对高一位的关键字排序，对高一位的关键字排序，依次重复，直至对依次重复，直至对最高位关键字最高位关键字k1排序后，便成为一个有序序列排序后，便成为一个有序序列MSD与与LSD不同特点不同特点l按按MSD排序，必须将序列逐层分割成若干子排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序序列，然后对各子序列分别排序l按按LSD排序，不必分成子序列，对每个关键排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排键字比较，而通过若干次分配与收集实现排序序结束第 51 页链式基数排序链式基数排序基数排序：借助基数排序：借助“分配分配”和和“收集收集”对单逻辑对单逻辑关键字进行排序的一种关键字进行排序的一种方法方法链式基数排序：用链表链式基数排序：用链表作存储结构的基数排序作存储结构的基数排序结束第 52 页10.6 10.6 基数排序基数排序l链式基数排序步骤链式基数排序步骤设置设置10个队列，个队列，fi和和ei分别为第分别为第i个队列的头指针和尾指针个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变记录的指针第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至值，将链表中记录分配至10个链队列中，每个队列记录的关个链队列中，每个队列记录的关键字的个位相同键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将指向下一个非空队列的队头记录，重新将10个队列链成一个个队列链成一个链表链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列位、百位进行，最后得到一个有序序列结束第 53 页10.6 10.6 基数排序基数排序例例初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：结束第 54 页10.6 10.6 基数排序基数排序505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：结束第 55 页10.6 10.6 基数排序基数排序008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：结束第 56 页10.6 10.6 基数排序基数排序l算法评价算法评价时间复杂度：时间复杂度：l分配：分配：T(n)=O(n)l收集：收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：其中：n记录数记录数 d关键字数关键字数 rd关键字取值范围关键字取值范围 空间复杂度：空间复杂度：S(n)=2rd个队列指针个队列指针+n个指针个指针域空间域空间结束第 57 页1. (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 53 74 14 26 38 86 65 27 34 (3) 14 46 53 74 26 38 86 65 27 34 (4) 14 26 46 53 74 38 86 65 27 34 (5) 14 26 38 46 53 74 86 65 27 34 (6) 14 26 38 46 53 74 86 65 27 34 (7) 14 26 38 46 53 65 74 86 27 34 (8) 14 26 27 38 46 53 65 74 86 34 (9) 14 26 27 34 38 46 53 65 74 86直接插直接插入排序入排序 结束第 58 页 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 53 14 26 38 74 65 27 34 86 (2) 46 14 26 38 53 65 27 34 74 86 (3) 14 26 38 46 53 27 34 65 74 86 (4) 14 26 38 46 27 34 53 65 74 86 (5) 14 26 38 27 34 46 53 65 74 86 (6) 14 26 27 34 38 46 53 65 74 86 (7) 14 26 27 34 38 46 53 65 74 86冒泡排冒泡排序序 2. 结束第 59 页 (0) 46 74 53 14 26 38 86 65 27 34 (1) 34 27 38 14 26 46 86 65 53 74 (2) 26 27 14 34 38 46 74 65 53 86 (3) 14 26 27 34 38 46 53 65 74 86 (4) 14 26 27 34 38 46 53 65 74 86快速排快速排序序 3. 结束第 60 页 (0) 46 74 53 14 26 38 86 65 27 34 (1) 14 74 53 46 26 38 86 65 27 34 (2) 14 26 53 46 74 38 86 65 27 34 (3) 14 26 27 46 74 38 86 65 53 34 (4) 14 26 27 34 74 38 86 65 53 46 (5) 14 26 27 34 38 74 86 65 53 46 (6) 14 26 27 34 38 46 86 65 53 74 (7) 14 26 27 34 38 46 53 65 86 74 (8) 14 26 27 34 38 46 53 65 86 74 (9) 14 26 27 34 38 46 53 65 74 86 4. 简单选简单选择排序择排序 结束第 61 页5.5.构成初始堆（即建堆）的过程：构成初始堆（即建堆）的过程： 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10 (0) 46 74 53 14 26 38 86 65 27 34 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 74 53 14 26 38 86 65 27 34 (2) 46 74 53 14 26 38 86 65 27 34 (3) 46 74 38 14 26 53 86 65 27 34 (3) 46 74 38 14 26 53 86 65 27 34 (4) 46 14 38 27 26 53 86 65 74 34 (4) 46 14 38 27 26 53 86 65 74 34 (5) 14 26 38 27 34 53 86 65 74 46 (5) 14 26 38 27 34 53 86 65 74 46 结束第 62 页进行堆排序的过程进行堆排序的过程： (0) 14 26 38 27 34 53 86 65 74 46(0) 14 26 38 27 34 53 86 65 74 46 (1) 26 27 38 46 34 53 86 65 74 14 (1) 26 27 38 46 34 53 86 65 74 14 (2) 27 34 38 46 74 53 86 65 26 14 (2) 27 34 38 46 74 53 86 65 26 14 (3) 34 46 38 65 74 53 86 27 26 14 (3) 34 46 38 65 74 53 86 27 26 14 (4) 38 46 53 65 74 86 34 27 26 14 (4) 38 46 53 65 74 86 34 27 26 14 (5) 46 65 53 86 74 38 34 27 26 14 (5) 46 65 53 86 74 38 34 27 26 14 (6) 53 65 74 86 46 38 34 27 26 14 (6) 53 65 74 86 46 38 34 27 26 14 (7) 65 86 74 53 46 38 34 27 26 14 (7) 65 86 74 53 46 38 34 27 26 14 (8) 74 86 65 53 46 38 34 27 26 14 (8) 74 86 65 53 46 38 34 27 26 14 (9) 86 74 65 53 46 38 34 27 26 14 (9) 86 74 65 53 46 38 34 27 26 14结束第 63 页 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 14 53 26 38 65 86 27 34 (2) 14 46 53 74 26 38 65 86 27 34 (3) 14 26 38 46 53 65 74 86 27 34 (3) 14 26 27 34 38 46 53 65 74 86归并排归并排序序 6.