数据结构之排序算法

1、1065865姓名姓名 学号学号 成绩成绩 班级班级 李红李红 9761059 95 机机97.6 ABCDEFG2022-5-22注意带以下内容：注意带以下内容：1. 图图2-8-12. 图图2-8-23. 图图2-8-34. 图图2-8-45. 图图2-8-52022-5-23第二章第二章 数据结构与算法数据结构与算法(续续) 2022-5-242.8 排排 序序2.8.1 概概 述述1、排序的功能：、排序的功能：将一个数据元素（或记录）的将一个数据元素（或记录）的任意任意序列序列，重新排成一个按关键字，重新排成一个按关键字有序有序的序列。的序列。2、排序过程的组成步骤：、排序过程的组成步

2、骤： 首先首先比较比较两个关键字的大小；两个关键字的大小； 然后将记录从一个位置然后将记录从一个位置移动移动到另一个位置。到另一个位置。2022-5-25假设待排序的记录存放在地址连续的假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式一组存储单元中，那么这种存储方式下的数据类型可描述为：下的数据类型可描述为： MAX01234keyinfo#define MAX 20 typedef struct int key; float otherinfo; RedType;2022-5-26排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序直接插入排序直接

3、插入排序折半插入排序折半插入排序简单选择排序简单选择排序堆排序堆排序起泡排序起泡排序快速排序快速排序2022-5-272.8.2 插入排序插入排序 直接插入、折半插入直接插入、折半插入1、直接插入排序、直接插入排序:基本思想：基本思想：从数组的第从数组的第2号元素开始，顺号元素开始，顺序从数组中取出元素，并将该元素插入序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。到其左端已排好序的数组的适当位置上。举例：图举例：图8-2-12022-5-282.8.2 插入排序插入排序 直接插入、折半插入直接插入、折半插入该算法适合于该算法适合于n 较较小的情况，时间复小的情况，时间复

4、杂度为杂度为O(n2).1、直接插入排序、直接插入排序:基本思想：基本思想：从数组的第从数组的第2号元素开始，顺序从数组中取出元素，号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列：待排元素序列：53 27 36 15 69 42第一次排序：第一次排序： 27 53 36 15 69 42第二次排序：第二次排序： 27 36 53 15 69 42第三次排序：第三次排序： 15 27 36 53 69 42第四次排序：第四次排序： 15 27 36 53 69 42第五次排序：第五次排序： 15 27

5、 36 42 53 69 直接插入排序示例直接插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1次次2022-5-29void insertSort(RedType L ,int n) int i ,j; for(i=2; i=n; i+) if(Li.keyLi-1.key) L0=Li; /* 作为监视哨作为监视哨*/ for( j=i-1; L0.keyLj.key; j ) Lj+1=Lj; /* 记录后移记录后移*/ Lj+1=L0; /* 插入插入 */ 插入算法如下：插入算法如下：方法方法:Ki与与Ki-1,K i-2,K1依

6、次比较依次比较,直到找到应插入的位置。直到找到应插入的位置。2022-5-2102、折半插入排序、折半插入排序 折半插入排序在寻找插入位置时，不是逐折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。待排序元素越多，改进效果越明显。折半插入排序的条件：折半插入排序的条件： 在有序序列中插入一个关键字。在有序序列中插入一个关键字。举例，图8-2-22022-5-2112、折半插入排序、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半折半插入排序在寻找插入位置时，不是逐个比较而是

7、利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有例：有6个记录，前个记录，前5 个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 4253 )2022-5-212void BinsertSort(RedType L ,int n) int i,low,high,m

8、id; for(i=2; i=n; +i) L0=Li; /* r0作为监视哨作为监视哨*/ low=1; high=i-1; While(low=high) mid=(low+high)/2; if (L0.key=high+1; j ) Lj+1=Lj; /* 记录后移记录后移*/ Lhigh+1=L0; /* 插入插入*/ /* for*/ /*折半插入排序折半插入排序*/折半插入排序减少折半插入排序减少了关键字的比较次了关键字的比较次数，但记录的移动数，但记录的移动次数不变，其时间次数不变，其时间复杂度与直接插入复杂度与直接插入排序相同。排序相同。/*折半后的位置折半后的位置*/202

9、2-5-213 1、简单选择排序、简单选择排序思想：首先从思想：首先从1n个元素中选出关键字个元素中选出关键字最小最小的记录交的记录交换到换到第一个第一个位置上。然后再从第位置上。然后再从第2 个到第个到第n个元素中个元素中选出次小的记录交换到选出次小的记录交换到第二个第二个位置上，依次类推。位置上，依次类推。时间复杂度为时间复杂度为O(n2)，适用于适用于待排序元素较少待排序元素较少的情况。的情况。2.8.3 选择排序选择排序 简单选择排序、堆排序简单选择排序、堆排序举例：图举例：图8-2-32022-5-2142.8.3 选择排序选择排序 简单选择排序、堆排序。简单选择排序、堆排序。 1、

10、简单选择排序、简单选择排序思想：首先从思想：首先从1n个元素中选个元素中选出关键字出关键字最小最小的记录交换到的记录交换到第第一个一个位置上。然后再从第位置上。然后再从第2 个个到第到第n个元素中选出次小的记个元素中选出次小的记录交换到录交换到第二个第二个位置上，依次位置上，依次类推。类推。时间复杂度为时间复杂度为O(n2)，适用于适用于待排序元素较少待排序元素较少的情况。的情况。初态初态8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 ijkijkijkijk1 3 9 8 6 互换互换ijk1 3 9 8 6 ikj1 3 9 8 6 ikj第一趟第一趟第二趟

11、第二趟1 3 9 8 6 i kj第三趟第三趟2022-5-215简单选择排序的算法如下：简单选择排序的算法如下：void SelectSort( RedType L ,int n) int i,j,k,t; for (i=1,i=n;+i） /*选择第选择第i小的元素，并交换到位小的元素，并交换到位*/ k=i； for(j=i+1;j=n;+j) if ( Lj.keyLk.key) k=j; /*Lk 中存放的是第中存放的是第I小的元素小的元素*/ if(k!=i) t=Li; /*交换交换*/ Li=Lk; Lk=t ； /*FOR*/ /* SelectSort*/2022-5-21

12、6 2 堆排序堆排序也是一种选择排序。是具有特定条件的顺序存储也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：的完全二叉树，其特定条件是：任何一个非叶子结点的关键字任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。大于等于（或小于等于）子女的关键字的值。 (1) 堆的示例堆的示例 897624331510112536497856(a):堆顶元素取最大值堆顶元素取最大值(b):堆顶元素取最小值堆顶元素取最小值(2) 实现堆排序需解决两个问题：实现堆排序需解决两个问题： （1） 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？ （2） 输出堆顶元素

13、后，如何将剩余元素调整成一个新的堆？输出堆顶元素后，如何将剩余元素调整成一个新的堆？ 举例：图举例：图8-2-42022-5-217 (3) 输出堆顶元素并调整建新堆的过程输出堆顶元素并调整建新堆的过程(筛选筛选)6525365649784111(b)65365649784111(c)251125365649784165(a)25493656657841(d)11把自堆顶至叶子的调整过程称为把自堆顶至叶子的调整过程称为“筛选筛选。从一个无序序。从一个无序序列建堆的过程就是一个反复列建堆的过程就是一个反复”筛选筛选“的过程。的过程。2022-5-218（4）由无序序列建初始堆的过程由无序序列建初

14、始堆的过程2556497811654136(a)无序序列无序序列n=8, int(n/2)=4开始开始2556493611654178(b): 78被筛选后的状态被筛选后的状态2556413611654978(c): 49被筛选后的状态被筛选后的状态2511413656654978(d): 56被筛选后的状态被筛选后的状态(e): 被筛选之后建成堆被筛选之后建成堆11254136566549782022-5-219E、筛选算法（调整建堆）、筛选算法（调整建堆）typedef Sqlist HeapType; /堆采用顺序表存储表示堆采用顺序表存储表示void HeapAdjust( HeapT

15、ype &H, int s, int m) / 已知已知H.rs.m中记录的关键字除中记录的关键字除H.rs .key外均满足堆定义，外均满足堆定义，/本函数调整本函数调整H.rs .key，使，使H.rs.m成为一个堆，其中堆顶元素为最大值成为一个堆，其中堆顶元素为最大值rc=H.rs;for(j=2*s; j=m; j*=2) /沿关键字值较大的孩子结点向下筛选沿关键字值较大的孩子结点向下筛选if( jm & H.rj.key = H.rj.key) break;H.rs=H.rj; s=j; / forH.rs=rc;3376101524js10 76 24 33 15 1 2 3 4

16、5 rc.key = 10 m = 5 s = 12022-5-220typedef Sqlist HeapType; void HeapAdjust( HeapType &H, int s, int m) rc=H.rs;for(j=2*s; j=m; j*=2) if( jm & H.rj.key = H.rj.key) break;H.rs=H.rj; s=j; / forH.rs=rc;3310761524js76 10 24 33 15j=2*j=410第一次第一次3310761524s76 33 24 10 15j=2*j=8m第二次第二次2022-5-221void HeapSo

17、rt( HeapType &H) /堆顺序表堆顺序表H进行堆排序进行堆排序 for( i=H.length/2; i0; i) HeapAdjust(H, i, H.length); / 把把H.r1.H.length成为一个堆，成为一个堆， For(i=H.length; i1; i) 把堆顶元素与最后一个记录相交换把堆顶元素与最后一个记录相交换/ rc=H.r1; H.r1=H.ri; H.ri=rc; HeapAdjust(H, 1, i-1); /把把H.r1.i-1重新调整为一个堆重新调整为一个堆 F、堆排序算法、堆排序算法2022-5-222A:2556497811654136i=

18、4(1)2556497811654136i=3(2)2556657811494136(3)(4)2556657811494136i=2(5)2578655611494136i=1F、堆排序算法、堆排序算法2022-5-223(7)2556653611494178B:(6)7856653611494125重新调整为一个堆重新调整为一个堆(8)1125364149566578最终结果最终结果2022-5-2242.8.4 交交 换换 排排 序序交换排序的特点在于交换排序的特点在于交换交换。有冒泡和快速排序两种。有冒泡和快速排序两种。 1、冒泡排序（起泡排序）、冒泡排序（起泡排序）思想：思想：小的浮

19、起，大的沉底。小的浮起，大的沉底。从左端开始比较。从左端开始比较。第一趟：第第一趟：第1个与第个与第2个比较，大则交换；第个比较，大则交换；第2个与第个与第3个比较，个比较， 大则交换，大则交换，关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第二趟：对前第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换个记录进行同样的操作，关键字次大的记录交换 到第到第n-1个个位置上；位置上； 依次类推，则完成排序。依次类推，则完成排序。正序：时间复杂度为正序：时间复杂度为O(n) 逆序：时间复杂度为逆序：时间复杂度为O(n2) 适合于数据较少的情况。适合于数据较少的

20、情况。 排序排序n个个记录的文件最多需要记录的文件最多需要n-1趟冒泡排序。趟冒泡排序。举例：图举例：图8-2-52022-5-225第第六六趟趟排排序序后后第第五五趟趟排排序序后后第第四四趟趟排排序序后后第第三三趟趟排排序序后后第第二二趟趟排排序序后后第第一一趟趟排排序序后后初初始始关关键键字字思 想 ： 小 的思 想 ： 小 的浮 起 ， 大 的浮 起 ， 大 的沉底。沉底。49364165117836653641563641654136415611783636414911564925252511494956111111252525252022-5-226冒泡排序的冒泡排序的C程序段：程序

21、段：Void bubsort(RedType L ,int n) int i,x,j=1,k=1; while (j0); k=0; for (i=1;i=n-j; i+) if (Li+1.keyLi.key) k+;x=Li;Li=Li+1;Li+1=x; j+; /*while*/ /*Bobsort*/2022-5-2272、快速排序、快速排序 (对冒泡排序的改进）对冒泡排序的改进）思想：通过一趟排序将待排序列思想：通过一趟排序将待排序列分成两部分分成两部分，使其中，使其中一一部分记录部分记录的关键字均比的关键字均比另一部分小另一部分小，再分别对这两部分，再分别对这两部分排序，以达到整

22、个序列有序。排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。关键字通常取第一个记录的值为基准值。做法：附设两个指针做法：附设两个指针low和和high ，初值分别指向，初值分别指向第一个第一个记录记录和和最后一个记录最后一个记录，设关键字为，设关键字为 key ，首先从，首先从 high所所指位置起指位置起向前向前搜索，找到第一个搜索，找到第一个小于小于基准值的记录与基基准值的记录与基准记录交换，然后从准记录交换，然后从low 所指位置起所指位置起向后向后搜索，找到第搜索，找到第一个一个大于大于基准值的记录与基准记录交换，重复这两步直基准值的记录与基准记录交换，重复这两步直至至low=high为止。为止。时间复杂度：时间复杂度：O(log2n) 举例图举例图8-2-62022-5-228快速排序过程示意图：快速排序过程示意图：有序序列有序序列 6 18 23 52 67key初始序列初始序列 23 52 6 67 18lowhigh一次交换一次交换 18 52 6