数据结构第10章排序ppt课件

1、2第10章 排序3本章目录v10.1 概述概述v10.2 插入排序插入排序 v 10.2.1 直接插入排序直接插入排序 v 10.2.2 折半插入排序折半插入排序 *10.2.3 二路插入排序二路插入排序 *10.2.4 表插入排表插入排序序 v 10.2.5 希尔排序希尔排序v10.3 交换排序交换排序 v 10.3.1 起泡排序起泡排序 v 10.3.2 快速排序快速排序v10.4 选择排序选择排序 v10.4.1 直接选择排序直接选择排序 v10.4.2 树形选择排序树形选择排序v10.4.3 堆排序堆排序v10.5 归并排序归并排序v10.6 分配排序分配排序v10.7 内部排序方法的

2、比较内部排序方法的比较v10.8 外部排序外部排序 v 10.8.1 文件管理文件管理 10.8.2 外部排序外部排序 10.8.3 多路归并排序多路归并排序 v 10.8.4 置换选择排序置换选择排序 *10.8.5 最佳归并树最佳归并树 *10.8.6 磁带排序磁带排序4主要内容v知识点知识点v1、排序的定义，排序可以看作是线性表的一种操作、排序的定义，排序可以看作是线性表的一种操作v2、排序的分类，稳定排序与不稳定排序的定义。、排序的分类，稳定排序与不稳定排序的定义。v3、插入排序直接插入、对分插入、二路插入、表插入、希尔插、插入排序直接插入、对分插入、二路插入、表插入、希尔插入排序）。

3、入排序）。v4、交换排序冒泡排序、快速排序）。、交换排序冒泡排序、快速排序）。v5、选择排序简单选择排序、树形选择排序、堆排序）。、选择排序简单选择排序、树形选择排序、堆排序）。v6、归并排序、基数排序。、归并排序、基数排序。v7、外部排序、外部排序v重点难点重点难点v1、各种排序所基于的基本思想。、各种排序所基于的基本思想。v2、排序性能的分析，是否是稳定排序。、排序性能的分析，是否是稳定排序。v3、折半插入、希尔排序。、折半插入、希尔排序。v4、快速排序。、快速排序。v5、堆排序。、堆排序。v6、败者树、置换选择排序、最佳归并树。、败者树、置换选择排序、最佳归并树。v7、对每种排序方法的学

4、习，能举一反三。、对每种排序方法的学习，能举一反三。5基本概念 v排序：排序：v 假 设 含假 设 含 n n 个 记 录 的 序 列 为个 记 录 的 序 列 为 R 1 , R 1 , R2, ,Rn R2, ,Rn ，v 其 相 应 的 关 键 字 序 列 为其 相 应 的 关 键 字 序 列 为 K 1 , K 1 , K2, ,Kn K2, ,Kn ，v 这些关键字相互之间可以进行比较，这些关键字相互之间可以进行比较，即 在 它 们 之 间 存 在 着 这 样 一 个 关 系即 在 它 们 之 间 存 在 着 这 样 一 个 关 系Ks1Ks2KsnKs1Ks2Ksn，按此固有关系将

5、，按此固有关系将n n个记录的个记录的序列重新排列为序列重新排列为 Rs1, Rs2, ,Rsn Rs1, Rs2, ,Rsn 的操作称的操作称作排序。作排序。6基本概念稳定排序稳定排序 ：若：若KiKi为关键字，为关键字，Ki =KjKi =Kjijij），且在排），且在排序前的序列中序前的序列中RiRi领先于领先于RjRj。经过排序后，。经过排序后，RiRi与与RjRj的相对的相对次序保持不变即次序保持不变即RiRi仍领先于仍领先于RjRj），则称这种排序方法），则称这种排序方法是稳定的，否则称之为不稳定的。是稳定的，否则称之为不稳定的。内部排序内部排序 ：若整个排序过程不需要访问外存便能

6、完成，：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序则称此类排序问题为内部排序 外部排序：若参加排序的记录数量很大，整个序列的排外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为序过程不可能一次在内存中完成，则称此类排序问题为外部排序外部排序 7排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int key; AnyType other; 记录其它数据域记录其它数据域 RecType;RecType Rn+1; 8基本思想：假定第一个记录有序，从第基本思想：假定第一个记录有序，从第

7、2 2个记录开个记录开始，将待排序的记录插入到有序序列中，使有序序始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。列逐渐扩大，直至所有记录都进入有序序列中。 插入排序 插入排序种类：插入排序种类： 直接插入排序直接插入排序 折半插入排序折半插入排序 二路插入排序二路插入排序 表插入排序表插入排序 希尔排序希尔排序 9直接插入排序基本思想：将记录基本思想：将记录Ri(2=i=n)Ri(2=i=n)插入到有插入到有序子序列序子序列R1.i-1R1.i-1中，使记录的有序序列中，使记录的有序序列从从R1.i-1R1.i-1变为变为R1.i R1.i 10例如初始

8、关键字序列： 51 33 62 96 87 17 28 51i=2(33) 33 51 62 96 87 17 28 51i=3(62) 33 51 62 96 87 17 28 51i=4(96) 33 51 62 96 87 17 28 51i=5(87) 33 51 62 87 96 17 28 51i=6(17) 17 33 51 62 87 96 28 51i=7(28) 17 28 33 51 62 87 96 51i=8(51) 17 28 33 51 51 62 87 9611一趟直接插入排序算法void StrOnePass(RecType R，int i)已知已知R1.i-

9、1中的记录按关键字非递减有序排列，本算法中的记录按关键字非递减有序排列，本算法 插入插入Ri,使使R1.i中的记录按关键字非递减有序排列中的记录按关键字非递减有序排列 R0=Ri; j=i-1; 将待排序记录放进监视哨将待排序记录放进监视哨 x=R0.key; 从后向前查找插入位置，将大于待排序记录向后移动从后向前查找插入位置，将大于待排序记录向后移动 while (x Rj.key) Rj+1=Rj; j-; 记录后移记录后移 Rj+1=R0; 将待排序记录放到合适位置将待排序记录放到合适位置 StrOnePass12直接插入排序算法void StrInsSort1(RecType R，in

10、t n)本算法对本算法对R1.n进行直接插入排序进行直接插入排序 for(i=2;i=n;i+) 假定第一个记录有序假定第一个记录有序 StrOnePass(R， i)；13直接插入排序性能分析w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 n2ii移动次数为 =(n+4)(n-1)/2 n2)21(ii最好情况最好情况比较次数为n-1次移动次数为2n-1次14直接插入排序的优缺点 直接插入排序算法简单，当待排序记录数量直接插入排序算法简单，当待排序记录数量n很小时，局部有序时，较为适用。很小时，局部有序时，较为适用。 当当n很大时，其效率不高。很大时，其效率不高。 若对直接插入排序

11、算法进行改进，可从减少若对直接插入排序算法进行改进，可从减少“比较和比较和“挪动次数这两方面着手。挪动次数这两方面着手。 折半存入排序、二路插入排序、表插入排序、折半存入排序、二路插入排序、表插入排序、希尔排序都是对直接插入排序的改进。希尔排序都是对直接插入排序的改进。15折半插入排序折半插入排序vvoid BinsSort(RecType R，int n) v 对对R1.n进行折半插入排序进行折半插入排序v for(i=2;i=n;i+) 假定第一个记录有序假定第一个记录有序 v R0=Ri; 将待排记录将待排记录Ri暂存到暂存到R0v low=1; high=i-1; 设置折半查找的范围设

12、置折半查找的范围 Rlow.highv while (low=high) v m=(low+high)/2; 折半折半v if(R0.keyhigh; j-) Rj+1 = Rj; 记录后移记录后移v Rhigh+1 = R0; 插入插入v forvBinsSort16折半插入排序性能分析折半插入排序性能分析v减少了比较次数，移动次数不变。v时间复杂度仍为On2）。 17 在对一组记录在对一组记录（5454，3838，9696，2323，1515，7272，6060，4545，8383） 进行直接排序时，当把第进行直接排序时，当把第7 7个记录个记录6060插入到有插入到有序表时，为寻找插入位

13、置需比较多少次序表时，为寻找插入位置需比较多少次自测题自测题 118二路插入排序二路插入排序v对折半插入排序改进，减少了移动记录的次数，对折半插入排序改进，减少了移动记录的次数，但它要借助但它要借助n个记录的辅助空间，即其空间复杂个记录的辅助空间，即其空间复杂度为度为On）。）。v基本思想：另设一数组基本思想：另设一数组d，将，将R1赋值给赋值给d1，并将并将d1看作排好序的中间记录，从第二个记看作排好序的中间记录，从第二个记录起依次将关键字小于录起依次将关键字小于d1的记录插入的记录插入d1之前之前的有序序列，将关键字大于的有序序列，将关键字大于d1的记录插入的记录插入d1之后的有序序列。之

14、后的有序序列。v借助两个变量借助两个变量first和和final来指示排序过程中有来指示排序过程中有序序列第一个记录和最后一个记录在序序列第一个记录和最后一个记录在d中的位置。中的位置。 19v初始关键字序列：初始关键字序列： 51 33 62 96 87 17 28 51 vi=1 51v firstfinalvi=2 51 33v final firstvi=3 51 62 33v final firstvi=4 51 62 96 33v final firstvi=5 51 62 87 96 33v final firstvi=6 51 62 87 96 17 33v final fir

15、st vi=7 51 62 87 96 17 28 33v final first vi=8 51 51 62 87 96 17 28 33v final first 20二路插入排序算法二路插入排序算法vvoid BiInsertSort(RecType R，int n) v二路插入排序的算法二路插入排序的算法v int dn+1; 辅助存储辅助存储v d1= R1;first=1;final=1;v for(i=2;i=d1.key) 插入后部插入后部v low=1;high=final; v while (low=high) 折半查找插入位置折半查找插入位置v m=(low+high)/

16、2;v if(Ri.key=high+1;j-) dj+1 = dj; 移动元素移动元素v dhigh+1=Ri; final+; 插入有序位置插入有序位置v 21 else if(first=1) 插入前部插入前部 first=n; dn=Ri; else low=first;high=n; while (low=high) m=(low+high)/2; if(Ri.key dm.key) high=m-1; else low=m+1; while for (j=first;j=high;j+) dj-1 = dj; 移动元素移动元素 dhigh=Ri; first-; if if /fo

17、r 22表插入排序表插入排序v静态链表静态链表v #define n 待排序记录的个数待排序记录的个数vtypedef structv int key;v AnyType other; 记录其他数据域记录其他数据域v int next;v STListType;vSTListType SLn+1;23表插入排序算法表插入排序算法vvoid ListInsSort(STListType SL,int n) v 对记录序列对记录序列SL1.n作表插入排序。作表插入排序。v SL0.key=MAXINT ;v SL0.next=1; SL1.next=0;v for(i=2; i=n; i+ ) 查

18、找插入位置查找插入位置v j=0;v for(k=SL0.next; SLk.key=SLi.key; )v j=k, k=SLk.next; v SLj.next=i; SLi.next=k; v 结点结点i插入在结点插入在结点j和结点和结点k之间之间v for v ListInsSort24表物理排序表物理排序vvoid Arrange(STListType SL， int n)v 调整静态链表调整静态链表SL中各结点的指针值，使记录按关键字有序排列中各结点的指针值，使记录按关键字有序排列v p=SL0.next; p指示第一个记录的当前位置指示第一个记录的当前位置v for(i=1; i

19、n; i+ )v SL1.i-1 记录已按关键字有序，第记录已按关键字有序，第i个记录的当前位置应不小个记录的当前位置应不小于于iv while(p=1;d=d/2) for(i=1+d;i0&R0.keyaj+1.keyaj.keyaj+1.key），），则将其交换，最终达到有序化则将其交换，最终达到有序化 31起泡排序示例初始初始关键关键字字5133629687172851第第一一趟趟3351628717285196第第四四趟趟3317 285151628796第第三三趟趟3351172851628796第第二二趟趟33335151626217172828515187879696第

20、第五五趟趟17 28335151628796第第六六趟趟17 2833515162879632void BubbleSort(RecType R ，int n) 起泡排序起泡排序 i = n; i 指示无序序列中最后一个记录的位置指示无序序列中最后一个记录的位置 while(i1) LastExchange=1; 记最后一次交换发生的位置记最后一次交换发生的位置 for(j=1;jRj+1.key) RjRj+1; 逆序时交换逆序时交换 LastExchange=j; if i=LastExchange; while 起泡排序算法33起泡排序性能分析01n移动次数比较次数最佳情况2/ ) 1(

21、32/ ) 1(11nnnnini移动次数比较次数最差情况平均时间复杂度：平均时间复杂度：O(n2)34一组关键字一组关键字19,01,26,92,87,11,43,87,2119,01,26,92,87,11,43,87,21），），进行冒泡排序，进行冒泡排序，试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 自测题自测题 3 冒泡排序示例冒泡排序示例35快速排序 基本思想：从排序序列中任选一记录作为枢轴或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一趟排序后“枢轴到位，并将序列分成两部分，再分别对这两部分排序。 由由Hoare(

22、图灵奖获得者图灵奖获得者)1962年提出，年提出，被评为被评为20世纪十大优秀算法之一世纪十大优秀算法之一 。36快速排序图示不大于不大于不小于不小于1n枢枢轴轴37快速排序示例初始关键字序列：初始关键字序列： 51 33 62 96 87 17 28 51R0=51 i(枢轴枢轴) jj向前扫描向前扫描 i j第一次交换之后：第一次交换之后： 28 33 62 96 87 17 51 i ji向后扫描向后扫描 i j第二次交换之后：第二次交换之后： 28 33 96 87 17 62 51 i jj向前扫描向前扫描 i j 第三次交换之后：第三次交换之后： 28 33 17 96 87 62

23、 51i向后扫描向后扫描 i j 第四次交换之后：第四次交换之后： 28 33 17 87 96 62 51j向前扫描向前扫描 i j 完成一趟排序：完成一趟排序： 28 33 17 51 87 96 62 51 ij 38快速排序示例初始关键字序列：初始关键字序列： 51 33 62 96 87 17 28 51一趟排序之后：一趟排序之后： 28 33 17 51 87 96 62 51分别进行快速排序：分别进行快速排序：17 28 33 完毕完毕 完毕完毕 51 62 87 96 51 62 完毕完毕 完毕完毕快速排序后的序列：快速排序后的序列： 17 28 33 51 51 62 87

24、9639快速排序算法int Partition(RecType R ，int l，int h) 交换记录子序列交换记录子序列Rl.h中的记录，使枢轴记录到位并返回其所在位中的记录，使枢轴记录到位并返回其所在位置置 int i=l; j=h; 用变量用变量i,j记录待排序记录首尾位置记录待排序记录首尾位置 R0 = Ri; 以子表的第一个记录作枢轴，将其暂存到记录以子表的第一个记录作枢轴，将其暂存到记录R0中中 x = Ri.key; 用变量用变量x存放枢轴记录的关键字存放枢轴记录的关键字 while(ij) 从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(i=x) j-; R

25、i = Rj; 将比枢轴小的记录移到低端将比枢轴小的记录移到低端 while(ij & Ri.key=x) i+; Rj = Ri; 将比枢轴大的记录移到高端将比枢轴大的记录移到高端 while Ri = R0; 枢轴记录到位枢轴记录到位 return i; 返回枢轴位置返回枢轴位置Partition 40快速排序算法void QuickSort(RecType R ，int s，int t) 对记录序列对记录序列Rs.t进行快速排序进行快速排序 if(st) k=Partition(R,s,t); QuickSort(R,s,k-1); QuickSort(R,k+1,t); if

26、QuickSort 快速排序的平均时间复杂度为快速排序的平均时间复杂度为O Onlog2nnlog2n） 最差为最差为O(n2)O(n2)41对下列一组关键字对下列一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果试写出快速排序的每一趟的排序结果 自测题自测题 4 快速排序示例快速排序示例42 设有顺序放置的设有顺序放置的n个桶，每个桶个桶，每个桶中装有一粒砾石，每粒砾石的颜色是中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排，使红、白、蓝之一。要求重新安排，使得红色砾石在前，白色砾石居中，蓝得

27、红色砾石在前，白色砾石居中，蓝色砾石居后。对每粒砾石的颜色只能色砾石居后。对每粒砾石的颜色只能察看一次，且只允许交换操作来调整察看一次，且只允许交换操作来调整砾石的位置。砾石的位置。【上海大学【上海大学 2019 二二 2(18分分)】算法举例算法举例 10.1 10.1 快速排序快速排序43红、白、兰三色排序算法红、白、兰三色排序算法vvoid QkSort(rectype r ,int n)vint i=1, j=1, k=n;v while(j=k)v if( rj=1) 当前元素是红色当前元素是红色v rirj; i+; j+; v else if( rj=2) j+; 当前元素是白色

28、当前元素是白色v else (rj=3 当前元素是兰色当前元素是兰色v rjrk; k-; vQkSort44 冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。 【吉林大学2019二.3(9分)】【北京邮电大学1992六(10分)】 算法举例算法举例 10.2 10.2 双向冒泡排序双向冒泡排序45vvoid BubbleSort2(int a,int n) v 相邻两趟向相反方向起泡的冒泡排序算法相邻两趟向相反方向起泡的冒泡排序算法vchange=1;low=0;high=n-1; 冒泡的上下界冒泡的上下界v whil

29、e(lowhigh & change)v change=0; 设不发生交换设不发生交换v for(i=low;iai+1)v aiai+1;change=1; 有交换有交换,修改标志修改标志changev high-; 修改上界修改上界v for(i=high;ilow;i-) 气泡下沉气泡下沉,小元素上浮小元素上浮(向左向左)v if(aiai-1)v aiai-1;change=1; 有交换有交换,修改标志修改标志changev low+; 修改下界修改下界v while vBubbleSort2 算法举例算法举例 10.2 10.2 双向冒泡排序的算法双向冒泡排序的算法46 对给

30、定关键字序号j(1jn)，要求在无序记录A1.n中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找。(要求用最少的时间和最少的空间) 例如：给定无序关键字7,5,1,6,2,8,9,3，当j=4时，找到的关键字应是5。【中科院研究生院2019十二(15分)】【武汉理工大学2019四.3(35/3分)】算法举例算法举例 10.3 10.3 快速排序快速排序47vint partition(RecType A,int 1,n)v int i=1,j=n;x=Ai.key;v i=1; v while(ij) v while(i=x) j-; v if(ij) Ai

31、+=Aj;v while(ij & Ai.key=x) i+;v if(ij) Aj-=Ai;v v return i;v v void Find_j(RecType A,int n,int j)v i=partition (A,1,n);v while(i!=j)v if(ij) i=quicksart(A,i+1,n); 在后半部分继续进行划在后半部分继续进行划分分v else i=quicksart(R,1,i-1); 在前半部分继续进行划在前半部分继续进行划分分v 算法举例算法举例 10.3 10.3 的算法的算法48选择排序 基本思想：依次从待排序记录序列中选择出关键基本思想

32、：依次从待排序记录序列中选择出关键字值最小或最大的记录、关键字值次之的字值最小或最大的记录、关键字值次之的记录、记录、，并分别将它们定位到序列左侧，并分别将它们定位到序列左侧或右侧的第或右侧的第1 1个位置、第个位置、第2 2个位置、个位置、，从而使待排序的记录序列成为按关键字值由小从而使待排序的记录序列成为按关键字值由小到大或由大到小排列的有序序列。到大或由大到小排列的有序序列。 选择排序种类：选择排序种类： 直接简单选择排序直接简单选择排序 树形选择排序树形选择排序 堆排序堆排序 49直接选择排序 待排记录序列的状态为：待排记录序列的状态为：有序序列有序序列R1.i-1 无序序列 Ri.n

33、有序序列中所有记录的关键字均小于无序序列中记录的关键字，第i趟直接选择排序是从无序序列Ri.n的n-i+1记录中选出关键字最小的记录加入有序序列 50直接选择排序示例初始关键字序列：初始关键字序列： 51 33 62 96 87 17 28 51 第一趟排序后：第一趟排序后： 17 33 62 96 87 51 28 51 第二趟排序后：第二趟排序后： 17 28 62 96 87 51 33 51 第三趟排序后：第三趟排序后： 17 28 33 96 87 51 62 51第四趟排序后：第四趟排序后： 17 28 33 51 87 96 62 51第五趟排序后：第五趟排序后： 17 28 3

34、3 51 51 96 62 87第六趟排序后：第六趟排序后： 17 28 33 51 51 62 96 87第七趟排序后：第七趟排序后： 17 28 33 51 51 62 87 9651直接选择排序算法void SelectSort(RecType R，int n) 对记录序列对记录序列R1.n作直接选择排序。作直接选择排序。 for(i=1; in; i+) 选择第选择第i小的记录，并交换到位小的记录，并交换到位 k=i; 假定第假定第i个元素的关键字最小个元素的关键字最小 for(j=i+1;j=n;j+) 找最小元素的下标找最小元素的下标 If(Rj.keyRk.key) k=j; i

35、f(i!=k) RiRk; 与第与第i个记录交换个记录交换 forSelectSort 直接选择排序的平均时间复杂度为On2） 记录移动次数记录移动次数最好情况：最好情况：0 0 最坏情况：最坏情况：3(n-1)3(n-1)比较次数比较次数( (与初始状态无关与初始状态无关):):)(21)(211nninni52 基本思想：对基本思想：对n个待排序记录的关键字进行两两比较，从中个待排序记录的关键字进行两两比较，从中选出选出 n/2 个较小者再两两比较，直到选出关键字最小的记录为个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。止，此为一趟排序。 一趟选出的关键字最小的记录称为一

36、趟选出的关键字最小的记录称为“冠军冠军”，而，而“亚军亚军是从与是从与“冠军比较失败的记录中找出。冠军比较失败的记录中找出。 输出输出“冠军后，将冠军叶子结点关键字改为最大，冠军后，将冠军叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。循环直到输出全部有序序列。 树形选择排序(锦标赛排序 ) 53 对关键字序列对关键字序列72,73,71,23,94,16,05,68进行树形选择排序进行树形选择排序 树形选择排序(锦标赛排序 ) 0523057223160572737123941605

37、6854 “亚军是从与亚军是从与“冠军比较失败的记录中找出冠军比较失败的记录中找出的的树形选择排序(锦标赛排序 ) 1623167123166872737123941668亚军55 n个记录的锦标赛排序，每选择一个记录需个记录的锦标赛排序，每选择一个记录需 log2n 次比较，时间复杂度为次比较，时间复杂度为O(nlog2n)。 缺点：需要较多的辅助存储空间；缺点：需要较多的辅助存储空间； 与与“最大值进行多次多余的比较。最大值进行多次多余的比较。 对树形排序的改进是堆排序对树形排序的改进是堆排序 树形选择排序性能分析 56堆的定义：堆是满足下列性质的序列堆的定义：堆是满足下列性质的序列K1,

38、K2, , KnK1,K2, , Kn： 堆排序 12ii2iiKKKK或12ii2iiKKKK（i =1,2, n/2） 若上述序列是堆，则若上述序列是堆，则K1K1必是序列中的最小值或最大必是序列中的最小值或最大值，分别称作小顶堆或大顶堆值，分别称作小顶堆或大顶堆 （小堆或大堆，小根堆或大根堆）。（小堆或大堆，小根堆或大根堆）。若将此序列看成是一棵完全二叉树，则堆或是空树或是满若将此序列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，任何一足下列特性的完全二叉树：其左、右子树分别是堆，任何一个结点的值不大于个结点的值不大于(或不小于或不小于)左左/右子

39、女结点若存在的值右子女结点若存在的值 57堆排序示例 28 51 33 62 87 96 17 51 51 87 33 28 51 62 96 17 96，51，87，33，28，62，51，17 是大顶堆 例如：17，28，51，33，62，96，87，51 是小顶堆58堆排序基本思想：先建一个堆，即先选得一个基本思想：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前最后一个记录交换，之后将序列中前n-1n-1个个记录重新调整为一个堆调堆的过程称为记录重新调整为一个堆调堆的过程称为“挑选挑选”），再将堆顶记录和第

40、），再将堆顶记录和第n-1n-1个记录个记录交换，如此反复直至排序结束。交换，如此反复直至排序结束。 堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？使之成为一个新的堆？59第二个问题解决方法第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至比较，并

41、与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆叶子结点，将得到新的堆第一个问题解决方法第一个问题解决方法方法：把整个数组方法：把整个数组R1到到Rn调整为一个大根堆，调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整即把完全二叉树中以每一个结点为根的子树都调整为堆。需要将以序号为为堆。需要将以序号为n/2 ， n/21 ， ，1的结点作为根的子树调整为堆的结点作为根的子树调整为堆用筛选法调整堆用筛选法调整堆60调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景61调整堆示例5151876228963317(d

42、)28与87交换后调成的新堆3351516287962817(c)调整后的新堆62建堆示例初始关键字序列：初始关键字序列：5151，3333，6262，9696，8787，1717，2828，5151为例，为例，其初始建大顶堆过程其初始建大顶堆过程 3362968728175151(a)4.8是堆，不调整3362968728175151(b)3.8是堆，不调整63建堆示例3362968728175151(c)2.8不是堆，进行筛选不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选不是堆，进行筛选8762515128179633(e)建成的大顶堆建成的大顶堆64堆排序筛

43、选算法void Sift(RecType R，int i，int m) 假设假设Ri+1.m中各元素满足堆的定义，本算法调整中各元素满足堆的定义，本算法调整Ri使序列使序列 Ri.m中各元素满足堆的性质中各元素满足堆的性质 R0=Ri; 暂存暂存 for(j=2*i; j=m; j*=2) if(jm & Rj.keyRj+l.key) j+; 沿大者右方向筛沿大者右方向筛选选 if(R0.key0;i-) 把把R1.n建成大顶堆建成大顶堆 Sift(R,i,n); for(i=n;i1;i-) 输出并调堆输出并调堆 R1Ri; Sift(R,1,i-1); 将将R1.i-1重新调整为

44、大顶堆重新调整为大顶堆 forHeapSort 堆排序的时间复杂度为堆排序的时间复杂度为O Onlog2nnlog2n） 66时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn) 建初始堆时间：调用建初始堆时间：调用SIFT 过程过程n/2 次，每次以次，每次以Ri为根的子树调整为堆。具有为根的子树调整为堆。具有n个结点的完全二叉个结点的完全二叉树深度是树深度是h= logn +1 , 第第i层结点个数至多为层结点个数至多为 2 i-1。SIFT对深度为对深度为k的完全二叉树进行比较的关键字的完全二叉树进行比较的关键字次数至多为次数至多为2(k-1)，因此比较总次数不超过，因

45、此比较总次数不超过C1(n) 2 i-1*2(h-1) =2 h-1+2 h-2*2+2 h-3 *3+ +2*(h-1)=2*2 (log 2n)+1 =4n重新建堆时间：排序过程中重新建堆比较总次数不重新建堆时间：排序过程中重新建堆比较总次数不超过超过C2(n)=2*(log n-1 + log n-2+ log 2 )=1;i=i/2)v if(R0.keyRi.key) v Rj=Ri; j=i; v else break;v Rj=R0;v siftv(2)void HeapBuilder(RecType R,int n)v for(i=2;i=n;i+) sift (R,i); 7

46、1归并排序 基本思想：将具有基本思想：将具有n n个待排序记录的序列看个待排序记录的序列看成是成是n n个长度为个长度为1 1的有序序列，进行两两归并，的有序序列，进行两两归并，得到得到n/2n/2 个长度为个长度为2 2的有序序列，再进行两两的有序序列，再进行两两归并，得到归并，得到n/4n/4 个长度为个长度为4 4的有序序列，如此的有序序列，如此重复，直至得到一个长度为重复，直至得到一个长度为n n的有序序列为止的有序序列为止 72归并排序示例二趟归并排序后：二趟归并排序后： 33 51 62 96 17 28 87 初始关键字序列：初始关键字序列： 51 33 62 96 87 17

47、28 一趟归并排序后：一趟归并排序后： 33 51 62 96 17 87 28 三趟归并排序后：三趟归并排序后： 17 28 33 51 62 87 96 73一趟归并排序算法void Merge(RecType R,RecType R1,int i,int l,int h) 将有序的将有序的Ri. l和和Rl+1.h归并为有序的归并为有序的R1i.h for(j=l+1,k=i; i=l&j=h;k+) R中记录由小到大地并入中记录由小到大地并入R1 if(Ri.key=Rj.key) R1k=Ri+; else R1k=Rj+; if(i=l) R1k.h=Ri. l; 将剩余的

48、将剩余的Ri. l复制到复制到R1 if(j=h) R1k.h=Rj.h; 将剩余的将剩余的Rj.h复制到复制到R1Merge74归并排序算法vvoid Msort(RecType R ,RecType R1 ,int s,int t)v 将将Rs.t进行进行2-路归并排序为路归并排序为R1s.tv if(s=t) R1s=Rs;v elsev m=(s+t)/2; 将将Rs.t平分为平分为Rs.m和和Rm+1.tv Msort(R,R2,s,m); 递归地将递归地将Rs.m归并为有序的归并为有序的R2s.mv Msort(R,R2,m+1,t); 递归地递归地Rm+1.t归并为有序的归并为有

49、序的R2m+1.tv Merge(R2,R1,s,m,t);将将R2s.m和和R2m+1.t归并到归并到R1s.tv ifvMSort75归并排序算法vvoid MergeSort(RecType R,int n)v 对记录序列对记录序列R1.n作作2-路归并排序。路归并排序。v MSort(R,R,1,n);vMergeSortv归并排序的设计复杂度为归并排序的设计复杂度为O(nlogn)76自测题自测题 v 10. 若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是vA. 起泡排序 vB. 插入排序 vC. 选择排序

50、vD. 二路归并排序v【2009年全国硕士研究生入学计算机学科专业基础综合试题】77分配排序 基本思想：利用关键字的结构，通过基本思想：利用关键字的结构，通过“分分配和配和“搜集的办法来实现排序搜集的办法来实现排序 分配排序可分为桶排序和基数排序两类 78桶排序桶排序桶排序Bucket SortBucket Sort也称箱排序也称箱排序Bin SortBin Sort），），其基本思想是：设置若干个桶，依次扫描待排序其基本思想是：设置若干个桶，依次扫描待排序记录记录R1.nR1.n，把关键字等于，把关键字等于k k的记录全部都装到的记录全部都装到第第k k个桶里分配），然后，按序号依次将各非空

51、个桶里分配），然后，按序号依次将各非空的桶首尾连接起来搜集）。的桶首尾连接起来搜集）。 79基数排序基数排序 基数排序就是一种借助“多关键字排序的思想来实现“单关键字排序的算法 假设假设n个记录待排序序列个记录待排序序列 R1, R2, ，Rn，每个记录，每个记录Ri中含中含有有d个关键字个关键字(Ki0, Ki1, ,Kid-1),则称上述记录序列对关键字则称上述记录序列对关键字(Ki0, Ki1, ,Kid-1)有序是指：对于序列中任意两个记录有序是指：对于序列中任意两个记录Ri和和Rj(1ijn)都满足下列都满足下列(词典词典)有序关系：有序关系： (Ki0, Ki1, ,Kid-1)

52、(Kj0, Kj1, ,Kjd-1)其中其中K0被称为被称为“最主位关键字，最主位关键字，Kd-1被称为被称为 “最次位关键字。最次位关键字。80v最高位优先最高位优先MSD法：先对法：先对K0进行排序，并按进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别的不同值将记录序列分成若干子序列之后，分别对对K1进行排序，进行排序，依次类推，直至最后对最次，依次类推，直至最后对最次位关键字排序完成为止。位关键字排序完成为止。v最低位优先最低位优先LSD法：先对法：先对Kd-1进行排序，然后对进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字进行排序，依次类推，直至对最主位关键字

53、K0排序完成为止。排序过程中不需要根据排序完成为止。排序过程中不需要根据“前一前一个关键字的排序结果，将记录序列分割成若干个关键字的排序结果，将记录序列分割成若干个个(“前一个关键字不同的前一个关键字不同的)子序列。子序列。 实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法: :81基数排序示例p369367167239237138230139第一次分配得到：第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：第一次收集得到：p23036716723713836923913982基数排序示例

54、第二次分配得到：第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：第二次收集得到：p23023713823913936716736983基数排序示例第三次分配得到：第三次分配得到：B1.f138139167B1.eB2.f230237239B2.eB3.f367369B3.e第三次收集之后便得到记录的有序序列：第三次收集之后便得到记录的有序序列：p138139167230237239367369 84基数排序的类型定义v#define n 待排序记录的个数待排序记录的个数vtypedef structv int keyd; 关键字由

55、关键字由d个分量组成个分量组成v int next; 静态链域静态链域v AnyType other; 记录其他数据域记录其他数据域v SLRecType;vSLRecType Rn+1; R1.n存放存放n个待排序记录个待排序记录vtypedef structv int f,e; 队列的头、尾指针队列的头、尾指针v SLQueue;vSLQueue Bm 用队列表示桶，共用队列表示桶，共m个个85基数排序的算法vint RadixSort(SLRecType R, int n)v 对对R1.n进行基数排序，返回收集用的链头指针进行基数排序，返回收集用的链头指针v for(i=1;i=0;j-

56、) 进行进行d趟排序趟排序v for(i=0;im;i+) 初始化桶初始化桶v Bi.f=-1; Bi.e=-1; forv while(p!=-1) 一趟分配，按关键字的第一趟分配，按关键字的第j个分量进行分配个分量进行分配v k=Rp.keyj; k为桶的序号为桶的序号v if(Bk.f=-1) Bk.f=p; Bk为空桶，将为空桶，将Rp链到桶头链到桶头v else RBk.e.next=p; 将将Rp链到桶尾链到桶尾v Bk.e=p; 修改桶的尾指针修改桶的尾指针v p=Rp.next; 扫描下一个记录扫描下一个记录v whilev接下页接下页v 86基数排序的算法续）v接上页接上页v

57、 i=0; /一趟收集一趟收集v while(Bi.f=-1) i+; 找第一个非空的桶找第一个非空的桶v t=Bi.e; p=Bi.f p为收集链表的头指针为收集链表的头指针,t为尾指为尾指针针v while(im-1)v i+; 取下一个桶取下一个桶v if(Bi.f!=-1) v Rt.next=Bi.f; t=Bi.e; 连接非空桶连接非空桶 v whilev Rt.next=-1; 本趟收集完毕，将链表的终端结点本趟收集完毕，将链表的终端结点指针置空指针置空v forv return p;vRadixSort87基数排序的性能分析v基数排序的时间复杂度是基数排序的时间复杂度是O (

58、d*(rd+n) )。v当当n较小、较小、d较大时，基数排序并不合适。较大时，基数排序并不合适。v只有当只有当n较大、较大、d较小时，特别是记录的信息量较小时，特别是记录的信息量较大时，基数排序最为有效。较大时，基数排序最为有效。v基数排序存储空间复杂度为基数排序存储空间复杂度为Ord）。）。v基数排序是稳定的。基数排序是稳定的。 88自测题自测题 6 已知已知8个记录，其关个记录，其关键字分别为键字分别为 (179，208，306，093，859，984，271，033) 试用基数排序法实施排序，试用基数排序法实施排序，描述其排序过程描述其排序过程 89排序方法排序方法平均时间平均时间最坏情

59、况最坏情况辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序O（n2）O（n2）O（1）稳定稳定起泡排序起泡排序O（n2）O（n2）O（1）稳定稳定直接选择排序直接选择排序O（n2）O（n2）O（1）不稳定不稳定希尔排序希尔排序O（n1.3）O（n1.3）O（1）不稳定不稳定快速排序快速排序O（nlog2n）O（n2）O（log2n）不稳定不稳定堆排序堆排序O（nlog2n）O（nlog2n）O（1）不稳定不稳定2-路归并排序路归并排序O（nlog2n）O（nlog2n）O（n）稳定稳定基数排序基数排序O ( d*(rd+n) )O ( d*(rd+n) )O (rd )稳定稳定内部排序方法

60、的比较 90内部排序小结v（1若若n较小如较小如n50），可采用直接插入排序或直），可采用直接插入排序或直接选择排序。接选择排序。v（2若待排序记录的初始状态已是按关键字基本有序，若待排序记录的初始状态已是按关键字基本有序，则选用直接插入排序或起泡排序为宜。则选用直接插入排序或起泡排序为宜。v（3当当n较大，若关键字有明显结构特征如字符串、较大，若关键字有明显结构特征如字符串、整数等），且关键字位数较少易于分解，采用时间性能整数等），且关键字位数较少易于分解，采用时间性能是线性的基数排序较好。若关键字无明显结构特征或取是线性的基数排序较好。若关键字无明显结构特征或取值范围属于某个无穷集合例如实数型关键字时，应值范围属于某个无穷集合例如