数据结构之排序算法讲义ppt课件.ppt

,在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维持原比例。,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,数据结构,2022/11/12,2,注意带以下内容：图2-8-1图2-8-2图2-8-3图2-8-4图2-8-5,2022/11/12,3,第二章数据结构与算法,(续),2022/11/12,4,2.8 排 序2.8.1 概 述,1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。2、排序过程的组成步骤： 首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。,2022/11/12,5,假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：,MAX,0,1,2,3,4,key,info,#define MAX 20 typedef struct int key; float otherinfo; RedType;,2022/11/12,6,排序方法,插入排序,选择排序,交换排序,归并排序,直接插入排序,折半插入排序,简单选择排序,堆排序,起泡排序,快速排序,2022/11/12,7,2.8.2 插入排序 直接插入、折半插入,1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。举例：图8-2-1,2022/11/12,8,2.8.2 插入排序 直接插入、折半插入,该算法适合于n 较小的情况，时间复杂度为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 36 42 53 69 直接插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,2022/11/12,9,void 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依次比较,直到找到应插入的位置。,2022/11/12,10,2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。,折半插入排序的条件： 在有序序列中插入一个关键字。,举例，图8-2-2,2022/11/12,11,2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。,(highlow ，查找结束，插入位置为low 或high+1 ),( 4236 ),( 4253 ),2022/11/12,12,void BinsertSort(RedType L ,int n) int i,low,high,mid; for(i=2; i=high+1; j ) Lj+1=Lj; /* 记录后移*/ Lhigh+1=L0; /* 插入*/ /* for*/ /*折半插入排序*/,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。,/*折半后的位置*/,2022/11/12,13,1、简单选择排序思想：首先从1n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，适用于待排序元素较少的情况。,2.8.3 选择排序 简单选择排序、堆排序,举例：图8-2-3,2022/11/12,14,2.8.3 选择排序 简单选择排序、堆排序。 1、简单选择排序思想：首先从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,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,2022/11/12,15,简单选择排序的算法如下：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/11/12,16,2堆排序也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。 (1) 堆的示例,(a):堆顶元素取最大值,(b):堆顶元素取最小值,(2) 实现堆排序需解决两个问题： （1） 如何由一个无序序列建成一个堆？ （2） 输出堆顶元素后，如何将剩余元素调整成一个新的堆？,举例：图8-2-4,2022/11/12,17,(3) 输出堆顶元素并调整建新堆的过程(筛选),把自堆顶至叶子的调整过程称为“筛选。从一个无序序列建堆的过程就是一个反复”筛选“的过程。,2022/11/12,18,（4）由无序序列建初始堆的过程,(c): 49被筛选后的状态,(d): 56被筛选后的状态,(e): 被筛选之后建成堆,2022/11/12,19,E、筛选算法（调整建堆）typedef Sqlist HeapType; /堆采用顺序表存储表示void HeapAdjust( HeapType ,2022/11/12,20,typedef Sqlist HeapType; void HeapAdjust( HeapType ,2022/11/12,21,void HeapSort( HeapType /把H.r1.i-1重新调整为一个堆 ,F、堆排序算法,2022/11/12,22,A:,F、堆排序算法,2022/11/12,23,2022/11/12,24,2.8.4 交 换 排 序交换排序的特点在于交换。有冒泡和快速排序两种。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上； 依次类推，则完成排序。正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 适合于数据较少的情况。 排序n个记录的文件最多需要n-1趟冒泡排序。,举例：图8-2-5,2022/11/12,25,第六趟排序后,第五趟排序后,第四趟排序后,第三趟排序后,第二趟排序后,第一趟排序后,初始关键字,思想：小的浮起，大的沉底。,2022/11/12,26,冒泡排序的C程序段：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/11/12,27,2、快速排序 (对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。做法：附设两个指针low和high ，初值分别指向第一个记录和最后一个记录，设关键字为 key ，首先从 high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。时间复杂度：O(log2n),举例图8-2-6,2022/11/12,28,快速排序过程示意图：,有序序列 6 18 23 52 67,key,low,high,一次交换 18 52 6 67 23,low,high,二次交换 18 23 6 67 52,high,三次交换 18 6 23 67 52/ 完成一趟排序后分别进行快速排序,low,high,2022/11/12,29,2.8.5 归并排序,初始序列 23 52 67 6 18 10一趟归并后 23 52 6 67 10 18二趟归并后 6 23 52 67 10 18三趟归并后 6 10 18 23 52 67,归并排序示例,功能：将两个或两个以上的有序表组成一个新的有序表。思想：把具有n个记录的表看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2或为1的有序子表；再两两归并，如此重复，直到得到一个长度为n的有序表为止。,2022/11/12,30,2.8.6 内部排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。 若待排序的记录个数n较小时，可采用简单排序方法。 若n 较大时，应采用快速排序或堆排序。 若待排序的记录已基本有序，可采用起泡排序。,2022/11/12,31,作业：P77 第34题P78 第3544题,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,